java集合框架总结(List、Set、Map)

时间:2022-01-24 16:16:56

java集合框架总结(List、Set、Map)

从上面的集合框架图可以看到,Java集合框架主要包括两种类型的容器,一种是集合(Collection),存储一个元素集合,另一种是图(Map),存储键/值对映射。Collection接口又有3种子类型,List、Set和Queue。Set的集合里不允许对象有重复的值,List允许有重复,Map不允许key重复。常用的集合框架有ArrayList、LinkedList、Vector、HashSet、HashMap、Hashtable。

List

  • ArrayList

    • 底层是动态数组

    • 默认无参构造函数会初始化大小为10,向集合中添加元素至集合满的时候,会生成一个大小为原来1.5倍的新集合,然后将集合中元素拷贝到新集合。

    • 线程不安全。

  • Vector

    • 底层是动态数组

    • 默认无参构造函数会初始化大小为10,向集合中添加元素至集合满的时候,会默认生成一个大小为原来2倍的新集合(vector支持自定义增加系数),然后将集合中元素拷贝到新集合。

    • 线程安全。

  • LinkedList

    • 底层是双向链表

    • 不需要考虑大小。

    • 线程不安全。

使用:若需要对集合频繁的查找,则使用ArrayList或Vector,若需要考虑线程安全,则选择Vector;若需要频繁的插入或删除,则使用LinkedList。

Set

  • ArrayList

    • 底层是HashMap。(区别是没有key-value对)

    • 默认无参构造函数会初始化大小为16,向集合中添加元素至集合大小的0.75倍时,会生成一个大小为原来2倍的新集合,然后重新计算元素的地址,将集合中元素插入到新集合。

    • 线程不安全。

Map

  • HashMap

    • 底层是数组+链表+红黑树。JDK8中,链表长度不小于8时,将链表转化为红黑树。

    • 默认无参构造函数会初始化大小为16,向集合中添加元素至集合大小的0.75倍时,会生成一个大小为原来2倍的新集合,然后重新计算元素的地址,将集合中元素插入到新集合,届时效率很低。

    • 线程不安全。

  • Hashtable

    • 底层是数组+链表。(拉链法)

    • 默认无参构造函数会初始化大小为11,向集合中添加元素至集合大小的0.75时,会生成一个大小为原来(2倍+1)的新集合,然后重新计算元素的地址,将集合中元素插入到新集合,届时效率很低。

    • 线程安全。

    • key和value都不允许为null(HashSet允许一个null,HashMap允许一个key为null)。

  • LinkedHashMap

    • 底层是HashMap+双向循环链表

    • 线程不安全。

  • ConcurrentHashMap

      通过分析Hashtable可知,synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。
      并发度可以理解为程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数,实际上就是ConcurrentHashMap中的分段锁个数,即Segment[]的数组长度。ConcurrentHashMap默认的并发度为16,但用户也可以在构造函数中设置并发度。当用户设置并发度时,ConcurrentHashMap 会使用大于等于该值的最小2幂指数作为实际并发度(假如用户设置并发度为17,实际并发度则为32)。运行时通过将key的高n位(n = 32 – segmentShift)和并发度减1(segmentMask)做位与运算定位到所在的Segment。segmentShift与segmentMask都是在构造过程中根据concurrency level被相应的计算出来。
      如果并发度设置的过小,会带来严重的锁竞争问题;如果并发度设置的过大,原本位于同一个Segment内的访问会扩散到不同的Segment中,CPU cache命中率会下降,从而引起程序性能下降。
      ConcurrentHashMap和Hashtable主要区别就是围绕着锁的粒度以及如何锁,可以简单理解成把一个大的HashTable分解成多个,形成了锁分离。
      ConcurrentHashMap的弱一致性主要是为了提升效率,是一致性与效率之间的一种权衡。要成为强一致性,就得到处使用锁,甚至是全局锁,这就与Hashtable和同步的HashMap一样了。

JDK7与JDK8中HashMap的实现
https://my.oschina.net/hosee/blog/618953

ConcurrentHashMap总结
https://my.oschina.net/hosee/blog/675884

ConcurrentHashMap能完全替代HashTable吗? 
https://my.oschina.net/hosee/blog/675423

ConcurrentHashMap原理分析
https://my.oschina.net/hosee/blog/639352

LinkedHashmap源码剖析
http://blog.csdn.net/ns_code/article/details/37867985