[数据结构与算法]java面试准备7-集合

ArrayList

• 底层为Object数组
• 不指定初始大小,默认为10
• 按照1.5倍进行扩容,源码如下:

oldCapacity + (oldCapacity >> 1)

LinkedList

• 底层为双向链表
• 双向链表连接的是一个一个的Node

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;
    }
}

HashSet

• 底层为HashMap

LinkedHashSet

• 底层为LinkedHashMap
• 扩容同HashSet

TreeSet

• 使用无参构造创建TreeSet时，仍然是无序的
• 底层为TreeMap

HashMap

• 底层为Node数组+单向链表+红黑树
• 第一次添加时,将数组扩容到16,临界值为16负载因子,即160.75=12
• 如果数组大于临界值之后,就会扩容到16*2=32,循环往复
• 当某一个链表达到8个节点且Node数组大于等于64,将链表转成红黑树
• 当某一个链表达到8个节点但Node数组小于64,不会马上将链表转成红黑树,而是先对数组进行扩容

LinkedHashMap

• 底层为数组+双向链表
• 维护了插入顺序

TreeMap

• 底层为红黑树
• 使用无参构造创建TreeMap时，仍然是无序的

ConcurrentHashMap

• 调用无参构造，默认初始大小为16
• 调用有参构造，指定大小，默认大小大于指定大小且为2的幂次方
• jdk7的ConcurrentHashMap底层结构是Segment数组，可以在初始化的时候指定Segment数组的长度，并且不可变。而Segment继承了ReentrantLock，它存储数据的实现与HashMap很像。也就是说jdk7的ConcurrentHashMap可以看成是由线程安全的HashMap组成的一个map数组，数组的长度决定了支持的最大的并发量。
• jdk8的ConcurrentHashMap的底层结构与HashMap又一样了，底层是一个Node的数组，而通过对Node数组以CAS加自旋方式实现扩容和对Node数组的每个元素的synchronized保证ConcurrentHashMap整体的线程安全

jdk7与jdk8实现比较

• 首先是支持的最大并发度：jdk7是在初始化的时候指定并且不可变，默认16最大32，而jdk8是针对数组中每个元素进行同步，所以数组越大支持的并发也越大。
• 线程安全实现方式：jdk7是采用Segment继承ReentrantLockt通过锁来实现，而jdk8是通过CAS+synchronized来实现。
• hash冲突解决方式：jdk7采用的是链表，而jdk8采用的是链表+红黑树的方式，在hash冲突严重的情况下jdk8的查找效率会更高。