jdk1.8集合包总结

1、ArrayList
基于数组实现, 默认大小是10
扩容机制（1.5倍）：newCapacity = oldCapacity + (oldCapacity >> 1);
元素拷贝：elementData = Arrays.copyOf;
优点：get元素快，直接通过 array[index]获取元素
缺点：频繁插入元素导致数组扩容、删除某个元素等导致拷贝数组元素效率降低
2、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;
      }
}
优点：add元素快
缺点：get元素慢（要么从head开始遍历，要么从tail开始遍历）：
Node<E> node(int index) {
      // assert isElementIndex(index);

      if (index < (size >> 1)) {
         Node<E> x = first;
         for (int i = 0; i < index; i++)
            x = x.next;
         return x;
      } else {
         Node<E> x = last;
         for (int i = size - 1; i > index; i--)
            x = x.prev;
         return x;
      }
}
3、Stack extends Vector
基于数组实现, 默认大小是10
扩容机制（2倍）：int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
push():按数组正序存放元素；
例如：
push(1);
push(2);
push(3);
数组{3,2,1}

pop():弹出数组倒序元素

4、HashMap
基于数组+链表+红黑树(jdk1.8开始,1.7以前基于散列表（数组+链表）)
默认数组大小：1 << 4;

hash寻址：(n - 1) & hash 效率大于 hash%数组.length

降低hash冲突：(h = key.hashCode()) ^ (h >>> 16)
将key 的hash值的高16位和低16位进行一下异或运算的结果作为寻址算法的新的hash值,保证同时将高16位和低16位的特征同时纳入寻址运算。

hash冲突机制：当链表元素>=8 就会转成红黑树
TREEIFY_THRESHOLD==8
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);

扩容机制：2倍扩容元素重新寻址（rehash）
      if (++size > threshold)
         resize();

         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                  oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;

5、LinkedHashMap extends HashMap

通过链表方式来维护元素顺序。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
      LinkedHashMap.Entry<K,V> p =
         new LinkedHashMap.Entry<K,V>(hash, key, value, e);
      linkNodeLast(p);
      return p;
}

      private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
      LinkedHashMap.Entry<K,V> last = tail;
      tail = p;
      if (last == null)
         head = p;
      else {
         p.before = last;
         last.after = p;
      }
}

6、TreeMap 基于红黑树
7、Set 基于 Map
添加元素：
PRESENT==null；
public boolean add(E e) {
      return map.put(e, PRESENT)==null;
}

HashSet extends HashMap：
public HashSet() {
      map = new HashMap<>();
}

LinkedHashSet extends HashSet ：
public LinkedHashSet() {
      super(16, .75f, true);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

TreeSet ：
public TreeSet() {
      this(new TreeMap<E,Object>());
}

图文精华

jdk1.8集合包总结

推荐 /2