首页 > 试题广场 >

介绍HashMap的数据结构、扩容机制，HashMap与Ha

[问答题]

介绍HashMap的数据结构、扩容机制，HashMap与Hashtable的区别，是否是线程安全的，并介绍ConcurrentHashMap的实现机制。

牛客568491799号

HashMap的数据结构：数组+链表+红黑树，当链表的值大于8的时候，就会转成红黑树存储。

HashMap默认初始容量16，加载因子0.75，当存储容量大于16*0.75的时候，扩容两倍，并将原数据复制到新的数组上。

HashMap是线程不安全的，性能高，用迭代器遍历索引从小到大，初始容量16，扩容是容量*2，HashTable线程安全，性能低，用迭代器遍历索引从大到小，初始容量11，扩容是容量*2 +1；

ConCurrentHashMap是线程安全的，通过进行数据的分段加锁，避免了锁的竞争。

发表于 2021-01-22 10:06:17 回复(0)

牛客365227200号

HashMap

1）数据结构：数组+链表（红黑树），数组用于存储内容，链表（红黑树）用于解决hash冲突。如果链表长度大于阈值8，但是当前数组长度小于树化阈值64，则进行数组扩容操作；如果数组长度大于树化阈值64，则进行链表树化操作，将单向链表转化为红黑树结构。

2）扩容机制：如果不指定容量，则初始容量默认为16。如果指定容量，则初始容量设置为大于指定容量的最小2的幂数。当当前容量大于容量*负载因子（默认为0.75）时进行扩容操作，扩容为原容量的2倍。

HashMap与HashTable的区别
1）数据结构区别：HashMap为数组+链表（红黑树），HashTable为数组+链表，HashTable没有树化操作。

2）扩容机制区别：未指定容量情况下，HashMap容量默认16，每次扩容为2n（n：原容量）。HashTable容量默认为11，每次扩容为2n+1（n：原容量）。指定容量情况下，HashMap将保证容量为2的幂数，HashTable将直接使用指定容量。

3）数据插入方式的区别：当发生hash冲突时，HashMap使用尾插法插入链表，HashTable使用头插法插入链表。

4）线程安全区别：HashMap是非线程安全的，HashTable因为使用synchronized修饰方法，所以HashTable是线程安全的。

ConcurrentHashMap的实现机制

1）ConcurrentHashMap通过synchronized关键字和CAS操作实现线程安全，若插入的槽没有数据，使用CAS操作执行插入操作，若插入的槽有数据，通过synchronized锁住链表的头节点，从而实现效率与线程安全的平衡。

发表于 2021-03-03 16:28:14 回复(0)

提交观点

问题信息

阅文集团 2021 Java工程师

来自：2023届阅文Java...

上传者：小小

难度：

2条回答 48收藏 2071浏览

扫一扫，把题目装进口袋