本文共 2022 字,大约阅读时间需要 6 分钟。
推荐阅读:
Map接口有三个比较重要的实现类,分别是HashMap、TreeMap和HashTable。在实际使用中,我们还经常使用LinkedHashMap、ConcurrentHashMap。Map | 有序性 | 线程安全性 | 备注 |
---|---|---|---|
HashMap | 无序 | 不安全 | |
TreeMap | 有序 | 不安全 | 根据键排序,可自定义Comparator |
Hashtable | 无序 | 安全(锁全表) | 不允许null |
LinkedHashMap | 有序 | 不安全 | 根据插入/访问顺序排序,有序的HashMap |
ConcurrentHashMap | 无序 | 安全(锁一个桶) | 线程安全的HashMap |
HashTable
底层数组+链表实现,无论key还是value都不能为null,线程安全,实现线程安全的方式是在修改数据时锁住整个HashTable,效率低,ConcurrentHashMap做了相关优化
初始size为11,扩容:newsize = olesize*2+1 计算index的方法:index = (hash & 0x7FFFFFFF) % tab.lengthHashMap
底层数组+链表实现,可以存储null键和null值,线程不安全
初始size为16,扩容:newsize = oldsize*2,size一定为2的n次幂 扩容针对整个Map,每次扩容时,原来数组中的元素依次重新计算存放位置,并重新插入 插入元素后才判断该不该扩容,有可能无效扩容(插入后如果扩容,如果没有再次插入,就会产生无效扩容) 当Map中元素总数超过Entry数组的75%,触发扩容操作,为了减少链表长度,元素分配更均匀 计算index方法:index = hash & (tab.length – 1)HashMap基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。
值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。
Map map = Collections.synchronizedMap(new HashMap());//同步的hashmap
ConcurrentHashMap
底层采用分段的数组+链表实现,线程安全
通过把整个Map分为N个Segment,可以提供相同的线程安全,但是效率提升N倍,默认提升16倍。(读操作不加锁,由于HashEntry的value变量是 volatile的,也能保证读取到最新的值。) Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占,ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术 有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁 扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容ConcurrentHashMap的锁分段技术:
假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术。首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。ConcurrentHashMap不允许Key或者Value的值为NULL
1.HashMap支持null Key和null Value;Hashtable不允许。
这是因为HashMap对null进行了特殊处理,将null的hashCode值定为了0,从而将其存放在哈希表的第0个bucket。2.HashMap是非线程安全,HashMap实现线程安全方法为Map map = Collections.synchronziedMap(new HashMap());
Hashtable是线程安全3.HashMap默认长度是16,扩容是原先的2倍;
Hashtable默认长度是11,扩容是原先的2n+14.HashMap继承AbstractMap;
Hashtable继承了Dictionary转载地址:http://esnii.baihongyu.com/