Java教程

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的比较的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!