Java基础五：HashMap、ConcurrentHashMap和HashTablele的比较

本文主要是介绍Java基础五：HashMap、ConcurrentHashMap和HashTablele的比较，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1、HashMap、ConcurrentHashMap和HashTablele的比较

（1）线程是否安全：HashMap是⾮线程安全的，ConcurrentHashMap和HashTable是线程安全的。因为ConcurrentHashMap和HashTable内部的⽅法都加锁了。 Jdk1.7 ConcurrentHashMap使用的是分段锁（Segment，每⼀把锁只锁容器其中⼀部分数据，多线程访问容器⾥不同数据段的数据，就不会存在锁竞争，提⾼并发访问率）；到了JDK1.8 的时候已经摒弃了Segment的概念，⽽是直接⽤ Node数组+链表+红⿊树的数据结构来实现，并发控制使⽤synchronized和CAS来操作。Hashtable (同⼀把锁) :使⽤ synchronized来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤ get，竞争会越来越激烈效率越低。
（2）效率： 因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable基本被淘汰，不要在代码中使⽤它；ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。
（3）对Null key和Null value的⽀持： HashMap可以存储null的key和value，但null作为key只能有⼀个，null作为value可以有多个；ConcurrentHashMap和HashTable不允许有 null 键和 null 值，否则会抛出NullPointerException 。
（4）初始容量⼤⼩和每次扩充容量⼤⼩的不同：①创建时如果不指定容量初始值，Hashtable默认的初始⼤⼩为 11，之后每次扩充，容量变为原来的 2n+1。HashMap默认的初始化⼤⼩为 16。之后每次扩充，容量变为原来的2倍。②创建时如果给定了容量初始值，那么Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap会将其扩充为 2 的幂次⽅⼤⼩（ HashMap 中的 tableSizeFor()⽅法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤ 2 的幂作为哈希表的⼤⼩,后⾯会介绍到为什么是2的幂次⽅。
（5）底层数据结构：JDK1.7 HashMap和ConcurrentHashMap都是使用数组+链表实现，JDK1.8以后为数组+链表/红⿊⼆叉树（解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为 8）将链表转换成红⿊树前会判断，如果当前数组的⻓度⼩于 64，那么会选择先进⾏数组扩容，⽽不是转换为红⿊树时，将链表转化为红⿊树，以减少搜索时间。）Hashtable使用的是组+链表实现。

2、2021.2.10:字节面试：HashMap中存放一个对象，时间复杂度是多少？

答：加入一个数据的复杂度：O(1)、O(n)和O(logn)都有可能
过程如下：
第一步，获得hashcode（key），时间复杂度O(1)；
第二步，找到对应的位置，判断是否有元素，如果该位置没有元素，直接new一个entry插入数据，时间复杂度O(1)；如果该位置有元素，位置上的元素小于8个，则在链表末端插入一个元素，put一个数据的复杂度为O(1)+ O(n)= O(n)；如果该位置有元素且位置上元素大于8个，则在红黑树上面插入一个元素，复杂度为O(1)+ O(logn)= O(logn)。

3、HashMap的长度为什么是2的幂次方？

答：为了能让 HashMap 存取⾼效，尽量较少碰撞，也就是要尽量把数据分配均匀。Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“(n - 1)&hash”。（n代表数组⻓度）。重点来了：“取余(%)操作中如果除数是2的幂次则等价于与其除数减⼀的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是2的 n 次⽅）。” 并且 采⽤⼆进制位操作 &，相对于%能够提⾼运算效率，这就解释了 HashMap 的⻓度为什么是2的幂次⽅。

解释：hash%length==hash&(length-1)等式的成立，前提length为2的n次方。

为了解释方便，数值取的比较小，hash=35，length=8;
左边 hash%length=35%8=3---------3的二进制为（0011）
右边 hash&(length-1)=35&(7)=(00100011)&(00000111)=（00000011）=3
此时，左边=右边，采用而兼职位操作&，相当于%能提高运算效率。

部分内容来自网络，侵删。

这篇关于Java基础五：HashMap、ConcurrentHashMap和HashTablele的比较的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！