这是我参与8月更文挑战的第13天,活动详情查看:8月更文挑战
1、Map
-
HashMap:
- JDK 1.8 之前
HashMap
由数组+链表
组成的,数组是HashMap
的主体,链表则是主要为了解决哈希冲突而存在的(“拉链法”解决冲突); - JDK 1.8 之后在解决哈希冲突时有了较大的变化,当链表长度大于等于阈值 (默认 8)时,将链表转化成红黑树(将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树),以减少搜索时间
- JDK 1.8 之前
-
LinkedHashMap:
LinkedHashMap
继承自HashMap
,所以它的底层仍然是基于拉链式散列结构,即由数组和链表或红黑树组成的。另外LinkedHashMap
在上面基础上,增加了一条双向链表,使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作,实现了访问顺序相关逻辑; -
HashTable(线程安全):
- 数组+链表组成,数组是
HashTable
主体,链表则是主要为了解决哈希冲突而存在的; - 不能存储
null
的键或值,否则报错NullPointException
; - JDK 1.0 开始,比
HashMap
(JDK 1.2) 早; - 其子类
Properties
使用更广泛
- 数组+链表组成,数组是
-
TreeMap:红黑树(自平衡的排序二叉树)
-
ConcurrentHashMap:线程安全的
HashMap
,底层结构与HashMap
一样,但HashMap
不是它的父类。
1.1 HashMap 和 Hashtable的区别
-
线程安全:
HashMap
是非线程安全的,Hashtable
是线程安全的,因为Hashtable
内部的方法基本都经过synchronized
修饰;(如果想要保证线程安全可以使用ConcurrentHashMap
) -
效率:因为线程安全问题,
HashMap
比Hashtable
效率更高一些。另外,Hashtable基本被淘汰了,使用更多的是它的子类:Properties ; -
对null的支持:
Hashmap
可以存储null
的 key 和 value,但null
作为键只能有一个,并存放在数组的固定位置(数组下标为0);Hashtable
不允许有null
的键和值,否则抛出异常NullPointerException
; -
初始容量和扩容大小:
- 创建不指定容量初始值:
HashMap
默认初始容量为16,之后每次扩容为原来的 2 倍;Hashtable
默认初始容量为11,之后每次扩容为原来的 2n+1; - 创建指定容量初始值:如果指定容量不为 2 的幂,
HashMap
则不会使用指定容量,HashMap
会扩容为2的幂次方(tableSizeFor()
方法),也就是说HashMap
的容量大小总是 2 的幂,这是重点下面会解释;Hashtable
直接使用指定大小初始值。
- 创建不指定容量初始值:
-
底层数据结构:JDK 1.8以后的
HashMap
在特定情况下,链表会转化成红黑树;Hashtable
结构仍是 数组+链表。
2、HashMap 底层源码分析
参考链接:(非常推荐观看此视频学习,评论区也都是大神)
Question
-
HashMap
的扩容与插入元素的顺序关系?- JDK 1.7 先扩容在插入;JDK 1.8 先插入再扩容
-
HashMap
往链表里插入节点的方式- JDK 1.7 之前是头插法,只需要将新节点的next指向原来的头部元素就行了,查重需要另写一个方法;
- JDK 1.8 之后是尾插法,尾插法需要遍历整个链表。在 JDK 1.8 中引入红黑树后,需要判断单链表的节点个数(超过8个转红黑树),需要遍历单链表,读取节点个数,故使用尾插法,还可以判断是否有重复节点,而不像 JDK 1.7 有另外的方法。
2.1 JDK 1.7
-
Q1:为什么
HashMap
扩容大小是2的指数倍?indexFor(int hash,int length)
通过 hash 值和 数组容量,计算存入HashMap
位置的数组下标: hash & (length - 1),一般来说,我们要计算存入数组中的下标位置,使用的是与
数组长度-1
进行取余。而现在换成&运算
可以大大提高计算效率。如:如:当容量为 16时,计算 hash & 15
假设 hash = 0101 0101
hash & 15
二进制长度都该为 32 位,这里缩写一下,举例子
=> 0101 0101
& 0000 1111
结果为 0101 = 5,该元素在容器位置的数组下标是 5;
1、提高计算效率:这个算法,以
length=16
为例子:可以控制结果在容器容量的范围内,因为容器中数组的最大下标为length - 1
的二进制,而容器大小必须限制为 2 的指数幂,这就可以
使得二进制的高位都为0,低位都为1,再与 hashCode 进行& 运算
,hash
的二进制高28位就没有意义了,&0就是0,所以最终的结果还是以hash
的二进制低4位与length - 1
的低位计算为准,取值范围在 [0,length-1].因为往哈希表里存入数据,就是对其的容量取余,而当使用容量为2的指数倍这个机制,就可以用&运算
代替取余运算,提高计算效率;为什么
HashMap
扩容大小是2的指数倍?这既是成因也是结果,算法的巧妙2、便于动态扩容后的重新计算哈希位置时能均匀分布元素:Q5(在 JDK 1.8 才被发现并使用)
-
Q2:
HashMap
存值时,计算hash值:得到了 key 的hashCode,为什么还要进行右移运算、异或运算获得 hash 值?如
Q1
得出的结论,在计算存放位置的数组下标时,结果只与hash
低位有关,hash
的高位是没有参与感的,这会导致计算的数组下标重复率太高(hash冲突变多),单个节点生成的链表过程长,在get
获取值时需遍历过长的链表,效率降低。使用右移运算、异或运算,使
hash
高位也参与到数组下标的计算中,使元素可以更均匀的分布在数组中,而不至于某个链表过长。如:hash=> 0011 1101 0101 (简写简写)
右移 >>> 4 => 0000 0011 1101
异或 ^ 0011 1101 0101
提高HashMap散列性
以上举例并没有用到
HashMap
真正的右移、异或运算方法,意思就是这么个意思。 -
Q3:
HashMap
的size()
方法直接返回
size
属性,因为在每次put
新元素时,size
都会 +1;并不是在调用
size()
方法时,遍历整个数组的每个节点下的链表长度。 -
Q4:
HashMap
在put
添加元素时,会进行一个覆盖的判断,当hash
相等,并且key值相等时(这里的判断包括==
,和equals()
判断),为什么先进行hash
判断?一个关于 hashCode 的规定:(hash也是通过 hashCode 计算来的嘛)
- 两个对象相等,hashcode一定相等
- 两个对象不等,hashcode不一定不等
- hashcode相等,两个对象不一定相等
- hashcode不等,两个对象一定不等
并且,
equals()
一般是要有用户重写的,里面逻辑较为复杂,再根据以上几条规范,先判断hash
,效率更高很多。 -
Q5:
HashMap
扩容之后原来元素在数组中的位置可能不变,也可能发生变化计算数组下标的方法:hash & (length - 1),是与数组长度有关的,借用
Q1
的例子如:当容量为 16时,计算 hash & 15
假设 hash = 0101 0101
hash & 15
二进制长度都该为 32 位,这里缩写一下,举例子
=> 0101 0101
& 0000 1111
结果为 0101 = 5,该元素在容器位置的数组下标是 5;
现在容器扩容至 32
如:当容量为 32 时,计算 hash & 31
假设 hash = 0101 0101
hash & 31
二进制长度都该为 32 位,这里缩写一下,举例子
=> 0101 0101 (其实这里第 5 位进制决定它的下标会不会改变:为0时,下标和之前一样;为1时,下标改为之前的下标+之前的容量)
& 0001 1111
结果为 1 0101 = 21,该元素在容器位置的数组下标是 21;
这时可以看到 21= 5 + 16,5是没扩容前的下标,16是扩容前的容量。
元素的位置改不改变,取决于
length-1
二进制最左边为1的位置,在那个位置上hash
二进制是否为1。为0时,下标和之前一样;为1时,下标改为之前的下标+之前的容量(这是比较通俗的一种理解) -
Q6:
HashMap
的key
值为null
的元素,存放在数组的一个固定的位置,下标为0
2.2 JDK 1.8
实现方法与 JDK 1.7 大同小异
-
Q1:为什么引入红黑树而不是其他数据结构,比如
完全平衡二叉树
既要保证
put
效率,也要保证get
效率。红黑树,对于元素的查找、插入、删除,都比较不错,这是一个比较这种考虑
-
Q2:较 JDK 1.7 ,JDK 1.8计算hash的方法,做了一些改动,简化了算法,但性质没有变,仍是为了提高HashMap散列性
-
Q3:链表转红黑树的条件?红黑树转链表的条件
当链表长度 >= 8,并且数组长度 >= 64,才会转化成红黑树;
如果链表长度 >= 8,数组长度 < 64 ,则会进行扩容,不会转换为红黑树。因为数组的长度较小,应该尽量避开红黑树。因为红黑树需要进行左旋,右旋,变色操作来保持平衡,所以当数组长度小于64,使用数组加链表比使用红黑树查询速度要更快、效率要更高。
当红黑树元素个数 <= 6时,并且是在扩容方法resize()执行时,判断红黑树长度<=UNTREEIFY_THRESHOLD(6),转化成链表;
2.3 总结
HashMap
的重要属性:(JDK 1.8)
// 默认初始容量 16 - 必须是2的幂
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转变为红黑树的阈值,当前节点元素个数 > 8 是链表变为红黑树
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转变为链表的阈值,当前节点元素个数 < 6
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
/** 存储元素的数组,长度总是2的幂次倍
*包括属性:
int hash; // key 的hash值
K key; // 要存入的key
V value; // 要存入的值
Node<K,V> next; // 指向下一个元素
*/
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 容器中元素的个数
transient int size;
// 加载因子
final float loadFactor;
// 临界值, = table.length * loadFactor.大于这个值,会进行扩容
int threshold;
复制代码
2.4 HashMap
调用put
方法,执行的过程:(JDK 1.8)
以空构造函数为例
-
HashMap
为空,调用resize()
初始化容器,resize()
方法中还包含了容器的扩容机制; -
(table.length - 1) & hash [(hash=key.hashCode()) ^ (hash >>> 16)]计算该元素插入到数组的下标,并判断这个位置是否为空:
-
如果为空,直接插入元素;
table[i] = newNode(hash,key,value,null); 复制代码
-
如果不为空,继续判断:
-
if
该元素与当前位置元素的 hash、key是否相等(这里的判断包括==
,和equals()
判断),相等则替换掉原来的值,并return原来的值; -
else if
这个位置的元素所属的类是不是TreeNode
(树结构),如果是则按照树结构的方式进行操作; -
else
该元素作为一个新元素,遍历当前节点链表的所有元素- 查看是否有重复元素:有,则跳出遍历,不用再添加了;
- 尾插到链表最后端,并判断:链表是否需要转化成红黑树(链表长度 >= 8 ,数组长度 >= 64;如果数组长度 < 64 则还是会进行数组扩容,因为扩容一可以增加容量,二是扩容会对链表元素的位置重新计算,重新分配位置,可以减端链表的长度。链表长度 >= 8 ,数组长度 >= 64就真的转红黑树了,因为再扩容的话内存占用就比较大了)
-
-
3、ConcurrentHashMap
线程安全的
HashMap
,但它不是继承HashMap
-
数据结构
JDK 1.7
:底层采用分段的的数组+链表实现;JKD 1.8
:与HashMap
结构一样,数组+链表/红黑树
-
线程安全
JDK 1.7
:ConcurrentHashMap
采用分段锁技术,将整个 Hash桶 进行了分段segment
,也就是将这个大数组分成了几个小的片段segment
,而且每个小的片段segment
上面都有锁存在,那么在插入元素时就需要先找到应该插入到哪一个片段segment
,获取segment
锁,然后再在这个片段上面进行插入;ConcurrentHashMap
让锁的粒度更精细一些,并发性能更好;JDK 1.8
:使用 synchronized 和 CAS 来操作。(JDK1.6 以后 对synchronized
锁做了很多优化) 整个看起来就像是优化过且线程安全的HashMap
,虽然在 JDK1.8 中还能看到Segment
的数据结构,但是已经简化了属性,只是为了兼容旧版本;
ConcurrentHahsMap 与 Hahtable的区别
1. 数据结构:
ConcurrentHashMap
:JDK 1.7
采用分段的的数组+链表实现;JDK 1.8
采用 数组+链表/红黑树;Hashtable
:数组+链表,数组为主体,链表主要为了解决哈希冲突存在。
2. 实现线程安全的方式(重要):
-
ConcurrentHashMap
:JDK1.7
的时候,ConcurrentHashMap
(分段锁) 对整个桶数组进行了分割分段(Segment
),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率;ConcurrentHashMap
让锁的粒度更精细一些,并发性能更好;JDK1.8
的时候已经摒弃了Segment
的概念,而是直接用Node
数组+链表+红黑树的数据结构来实现,并发控制使用synchronized
和CAS
来操作。(JDK1.6 以后 对synchronized
锁做了很多优化) 整个看起来就像是优化过且线程安全的HashMap
,虽然在 JDK1.8 中还能看到Segment
的数据结构,但是已经简化了属性,只是为了兼容旧版本。
-
Hashtable
(同一把锁):使用synchronized
来保证线程安全,随着数组越来越大,效率也越低下。当一个线程访问同步方法,其他线程也访问同步方式时,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。
近期评论