Java集合框架
Java的集合框架大致分为两个部分：
- Collection：主要有List、Set、Queue组成。
- Map：主要是HashMap，代表是键值对的集合。
List
List的特点是存取有序，可以存放重复元素，可以使用下标对元素进行操作。
1. ArrayList
-
ArrayList是由数组实现的，支持随机存储，也支持通过下标进行读写；
-
ArrayList默认容量是10，如果容量不够，ArrayList会自动扩容，扩容方法如下：
private static final int DEFAULT_CAPACITY = 10; //Default initial capacity. private int newCapacity(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //新容量=(旧容量+旧容量/2) if (newCapacity - minCapacity <= 0) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) return Math.max(DEFAULT_CAPACITY, minCapacity); if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return minCapacity; } return (newCapacity - MAX_ARRAY_SIZE <= 0) ? newCapacity : hugeCapacity(minCapacity); }
2. LinkedList
-
LinkedList是由双向链表实现的，它不支持随机存储，只能从某一端开始遍历，直到找到合适的元素进行操作；
private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } -
LinkedList在任意位置插入或者删除元素都很方便，因为只需要改变该节点的前驱结点和后继结点的连接即可；
-
但是LinkedList的查找却相比ArrayList查找则比较慢，原因是不支持下标索引，只能从头到尾遍历或者从尾到头遍历；
-
由于LinkedList的每个结点都在存储元素的基础上还存储了一个前驱后和后继指针，这会比ArrayList占用更多的空间。
3. Vector
- Vector向量和ArrayList比较相似，但是在操作向量中元素的时候，它会加上锁synchronized，这就导致了向量中的元素在操作的时候效率会比较低；
4. Stack
- Stack栈和Vector向量相似，也是在操作元素的时候加上了锁synchronized，因此在执行操作的时候效率会比较低。
Set
Set集合的特点是存取无序，不能存放重复元素，也不允许使用下标对元素进行操作。需要注意的是，在Java中Set其实是一个接口。Set集合的底层都是由Map实现的。原因是Map的健不允许被重复。
1. HashSet
-
HashSet由HashMap实现，只不过值是由一个固定的Object对象来代替：
private transient HashMap<E,Object> map;
2. TreeSet
-
TreeSet是由TreeMap实现的，只不过值是由一个固定的Object对象来代替：
TreeSet(NavigableMap<E,Object> m) { this.m = m; }
Queue
Queue队列遵循先进先出的原则（FIFO），插入元素时是在队列尾部插入，访问元素时是返回队列首部。
1. ArrayDeque
ArrayDeque是基于数组实现的双端队列，为了满足可以同时在数组两端插入或删除元素的需求，数组必须是循环的，也就是说数组的任何一点都可以被看作是起点或者终点。
2. LinkedList
LinkedList 一般都归在 List 下，只不过，它也实现了 Deque 接口，可以作为队列来使用。等于说，LinkedList 同时实现了 Stack、Queue、PriorityQueue 的所有功能。
3. PriorityQueue
PriorityQueue 是一种优先级队列，它的出队顺序与元素的优先级有关，执行 remove 或者 poll 方法，返回的总是优先级最高的元素。
Map
Map中保存的是键值对，键要求保持唯一性，但值可以重复。
1. HashMap
HashMap实现了Map接口，根据健的哈希值来存取数据，HashMap具有很快的访问速度。在JDK8中引入了红黑树：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
一旦HashMap中的哈希健发生了冲突，就把相同键位的地方改成链表，如果链表的长度大于8，则改用红黑树。
2. TreeMap
HashMap是无序的，所以在遍历的时候元素的顺序也是不可预测的。TreeMap是有序的，它在内部会对键进行排序，所在在遍历的时候可以得到预期的顺序。
注意，为了保证顺序，TreeMap的键必须要实现Comparable接口或者Comparator接口。
标签：Node,hash,HashMap,框架,元素,key,集合,Java,null From： https://www.cnblogs.com/xiaomitu/p/17132293.html