常用集合框架源码分析和对比

底层使用 char[ ]

初始容量16，初始化时带参，会构造一个参数.length+16的数组

append( null )，会变成null字符串

append先判断容量是否足够，不够进行数组复制扩容

StringBuilder

其他一致，不同在于方法用了synchronized关键字加锁

StringBuffer

StringBuild+StringBuffer

线程不安全

继承AbstractMap

index = hash & (table.length-1)  hash是基于hashCode再次计算得到的，目的是达到更加的散列

HashMap对象的key、value值均可为null

默认初始容量16，最大容量2^30，默认负载因子0.75树化节点个数8，解树化节点个数6可进行树化的 最小表容量64。应至少为4 * TREEIFY_THRESHOLD。即：数组长度大于64且链表长度大于等于8时转换成红黑树，链表长度小于6个时，解红黑树为链表

put原理如果table数组长度为0，扩容（扩容时，容量和下一次扩容阈值都扩大两倍，然后将原table重新插入新table）然后计算key的hash，拿到数组下标，如果此下标无节点，直接新建节点插入如果此下标已经有节点了，则遍历此下标的链表，采用hashCode+==+equals比较key是否相等，key相等则替换否则采用尾插法将当前节点插入到链表尾部，如果插入后当前链表长度大于等于8，链表转化为红黑树如果插入后table达到扩容阈值，则进行扩容

HashMap

线程安全，方法加synchronized，修改数据锁整个hahstable

初始容量11，扩容 2*oldSize+1 

计算index的方法：index = (hashCode & (2^32)-1) % tab.length

继承Dictionary

Hashtable对象的key、value值均不可为null

HashTable判断key相等少了==判断

Hashtable

线程安全1.7 底层使用数组+segment+分段锁1.8 底层使用数组+链表+红黑树

key，value都不能为null

1.7底层使用数组+Segment+分段锁 通过Segment继承ReentrantLock实现锁优点：锁分段提高了并发能力，理论上多少个Segment就可以提高多少倍并发缺点：锁分段导致每次定位一个元素，需要先hash计算Segment，再次hash计算链表中的位置，hash过程较长同时，Segment里面的数组+链表结构在数据量很大的时候会由于链表过长，查询效率低 O(n)

1.8底层使用数组+链表+红黑树 通过使用CAS+Synchronized保证线程安全与1.7比较，优点：从1.7的对Segment加锁调整为对数组元素（Node）加锁，定位元素和hashMap一致，只需一次hash由链表变成了链表+红黑树，时间复杂度降低到了O(logn)

ConcurrentHashMap

有序map

TreeMap

HashMap，Hashtable，ConcurrentHashMap，TreeMap

线程不安全，有序可重复，底层数组

迭代器  Iterator

1.5倍扩容 默认容量10，但初始化未指定容量时底层数组为空，不预分配空间

ArrayList

线程不安全，有序可重复，底层链表

LinkedList

线程安全 使用Synchronized保证

迭代器Enumeration enumeration = objects.elements();Iterator<Object> iterator = objects.iterator();

扩容：默认2倍扩容，可指定每次扩容的大小

Vector

线程不安全，无序不可重复，底层HashMap

HashSet

线程不安全，有序不可重复，底层TreeMap

TreeSet

ArrayList，LinkedList，Vector，HashSet，TreeSet

常用集合框架解析