Java基础-集合类-HashMap
参考文献
理论
HashMap最早是在JDK1.2中出现,直到JDK1.7一直没太大变化,但是到了JDK1.8突然进行了一个很大的改动.其中一个显著的改动就是:
之前JDK1.7的存储结构是数组+链表
到了JDK1.8变成了数组+链表+红黑树.
另外,HashMap是非线程安全的,也就是说多线程同时对HashMap中的某个元素进行增删改操作时,是不能保证数据的一致性的.
在JDK1.7中,首先是把元素放在一个个数组里面,后来存放的数据元素越来越多,于是就出现了链表,对数组中的每个元素,都可以有一条链表来存储元素.这就是有名的"拉链式"存储方法
后来存储的元素越来越多,链表也越来越长,查找一个元素的时候效率不仅没有提高(链表不适合查找,适合增删),反而下降了不少,于是在JDK1.8中对这条链表进行了改进–使用红黑树. 将链表结构编程红黑树,原来JDK1.7的优点是增删效率提高,在JDK1.8中不仅增删的效率提高了,查找的效率也提升了.
核心是基于哈希值的桶和链表
- 一般用数组实现桶
- 发生哈希碰撞时,用链表来链接发生碰撞的元素
- O(1)的平均查找、插入、删除时间
- 致命缺点是哈希值的碰撞(collision)
- 哈希碰撞:元素通过哈希函数计算后,被映射到同一个桶中.例如上图中的桶1, 5中的元素就发生了哈希碰撞
- 链表变成红黑树的条件:只有链表的长度不小于8,而且数组的长度不小于64的时候才会将链表转化为红黑树.
为什么选择红黑树?
- 红黑树是一个自平衡的二叉查找树,也就是说红黑树的查找效率是非常高的,查找效率会从链表的O(n)降低为O(logn);
- 引入红黑树就是为了查找数据快O(log n),解决链表查询深度的问题
- 但是为了保持“平衡”是需要付出代价的,但是该代价所损耗的资源要比遍历线性链表要少,所以当桶中元素大于8并且桶的个数大于64的时候,会使用红黑树,如果链表长度很短的话,根本不需要引入红黑树,引入反而会慢
红黑树性质
- 每个节点非红即黑
- 根节点(root)是黑的
- 不能有两个红色的节点连在一起(黑色可以)
- 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的
- 如果一个节点是红的,那么它的两儿子都是黑的
- 对于任意节点而言,其到叶子点树NULL指针的每条路径都包含相同数目的黑节点
- 每条路径都包含相同的黑节点
为什么不一下子把整个链表转变为红黑树?
- 构造红黑树要比构造链表复杂,在链表的节点不多的时候,从整体的性能上看,数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高;
- HashMap频繁的扩容,会造成底部红黑树不断的进行拆分和重组,这是非常耗时的,因此,也就是链表长度比较长的时候转变为红黑树才会效率显著;
- 链表变为红黑树的条件:元素个数大于8同时桶的个数大于64
- 当某个桶中的元素个数大于8时,会调用treeifyBin()方法,但并不一定就会变为红黑树
- 当哈希表中桶的个数大于64时,才会真正进行让其转化为红黑树
HashMap初始容量
-
initialCapacity初始容量
官方要求我们要输入一个2的N次幂的值,比如说2、4、8、16等等这些,但是我们忽然一个不小心,输入了一个20怎么办?没关系,虚拟机会根据你输入的值,找一个离20最近的2的N次幂的值,比如说16离他最近,就取16为初始容量.
HashMap负载因子
-
loadFactor负载因子
负载因子,默认值是0.75.负载因子表示一个散列表的空间的使用程度,有这样一个公式:initailCapacity*loadFactor=HashMap的容量. 所以负载因子越大则散列表的装填程度越高,也就是能容纳更多的元素,元素多了,链表大了,所以此时索引效率就会降低.反之,负载因子越小则链表中的数据量就越稀疏,此时会对空间造成烂费,但是此时索引效率高.
泊淞分布
当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为加载因子,每个碰撞位置的链表长度超过8个是几乎不可能的.当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为加载因子,每个碰撞位置的链表长度超过8个是几乎不可能的.
属性
1 | /** |
构造方法
1 | /** |
1 | /** |
存储元素(put)
1 | public class Main { |
第一步:调用put方法传入键值对
1 | /** |
第二步:使用hash算法计算hash值
1 | /** |
h = key.hashCode()
表示获取 key 的哈希值,然后将它右移 16 位,也就是h >>> 16
;- 右移16位的目的是:是为了让高位参与到新的哈希值的计算中,从而减小哈希冲突的概率.
- 因为在 HashMap 中,哈希值相同的 key 会放在同一个桶中,如果哈希冲突太多,桶中的链表就会过长,影响了 HashMap 的性能.
- 通过将哈希值的高位与低位进行异或操作,可以保证高位的信息参与到新的哈希值的计算中,从而减小哈希冲突的概率,提高 HashMap 的性能.这也是一种均衡哈希算法的实现方式.
1 | /** |
- HashMap 在创建对象时,并不会立即创建 table 数组,而是在第一次添加元素时进行延迟初始化.这样做的目的是为了节省内存空间,避免在创建对象时就分配大量的内存空间,浪费内存资源.
1 | final void treeifyBin(Node<K,V>[] tab, int hash) { |
扩容(resize)
-
扩容是为了避免哈希冲突过多,导致链表长度过长,从而影响了 HashMap 的查询和操作效率.
-
主要操作:
-
第一步: 先计算扩容后新
table
数组的大小newCap
和扩容后新的扩容阈值newThr
-
第一种情况:
oldCap > 0
老数组容量oldCap
(扩容前的数值大小)大于0- 继而判断老数组容量是否大于等于最大容量阈值,若超过了则将扩容阈值设置为int的最大值,返回老数组.
- 若不满足上面的条件,即老数组容量小于最大容量阈值,则将新的数组容量设置为老数组的2倍
- 若新数组容量小于最大容量阈值且老数组容量大于等于默认初始化容量(
DEFAULT_INITIAL_CAPACITY
,值为16),则将新扩容阈值设置为老扩容阈值的2倍.
- 若新数组容量小于最大容量阈值且老数组容量大于等于默认初始化容量(
-
第二种情况:
oldCap == 0 && oldThr > 0
-
以下三种情况满足上面的条件
1
2
3// 1. new HashMap(initCap,loadFactor)
// 2. new HashMap(initCap)
// 3. new HashMap(map),且这个map有数据 -
这种情况则将老扩容阈值
oldThr
,即threshold
的值赋值给newCap
-
-
第三中情况:
oldCap == 0 && oldThr == 0
-
以下情况满足上面的条件
1
2// 调用无参的构造函数oldCap,oldThr都未进行赋值
// 1. new HashMap(); -
这种情况将默认初始化容量(
DEFAULT_INITIAL_CAPACITY
,值为16)赋值给新数组容量newCap
,继而再根据负载因子计算新的扩容阈值,计算公式为(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)
-
-
-
第二步:
- 将计算完毕后的
newThr
赋值给属性变量threshold
, - 开辟新数组内存,将新数组
newTab
赋值给属性变量table
- 若老数组不为空,则将老数组的元素转移到新数组上.
- 遍历老数组,获取老数组上节点,判断当前节点是什么结构?
- 若当前节点是单个节点,则根据当前节点的
hash
值计算出当前节点应该在新数组上的位置,最后插入当前节点; - 若当前节点是红黑树,则对红黑树进行拆分;
- 若当前节点是链表,则采用两个链表(高低位链表)来重新组织节点,根据
(e.hash & oldCap) == 0
来判断将节点加入高位链表还是低位链表- 若满足条件,则将节点加入到低位链表中
- 若不满足条件,即
(e.hash & oldCap) == 1
,则将节点加入到高位链表中 - 最后将高低位链表装载到新数组上,装载规则为:
- 低位链表依然装载到原来的槽位上,即若链表在老数组下标为
j
的位置上,低位链表就在新数组下标j
上 - 高位链表则需要在原来的槽位上进行偏移老数组的长度,即若链表在老数组下标为
j
的位置上,高位链表就在新数组下标j+oldCap
上
- 低位链表依然装载到原来的槽位上,即若链表在老数组下标为
- 若当前节点是单个节点,则根据当前节点的
- 遍历老数组,获取老数组上节点,判断当前节点是什么结构?
- 最终返回处理完毕的新数组
- 将计算完毕后的
-
HashMap扩容就是先计算,新的hash表容量和新的容量阀值,然后初始化新的hash表,将旧的键值对重新映射到新的hash表里面.若在就的hash表里面涉及到红黑树,那么在映射到新的hash表中还涉及红黑树的拆分.
1 | /** |
移除元素(remove)
1 | /** |
1 | /** |
获取元素(get)
1 | /** |
1 | /** |
快速失败(fail—fast)
-
HashMap 遍历使用的是一种快速失败机制,它是 Java 非安全集合中的一种普遍机制,这种机制可以让集合在遍历时,如果有线程对集合进行了修改、删除、增加操作,会触发并发修改异常。
-
它的实现机制是在遍历前保存一份 modCount ,在每次获取下一个要遍历的元素时会对比当前的 modCount 和保存的 modCount 是否相等。
-
快速失败也可以看作是一种安全机制,这样在多线程操作不安全的集合时,由于快速失败的机制,会抛出异常。
LinkedHashMap,HashMap,TreeMap的区别
(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的. HashMap最多只允许一条记录的键为null,允许多条记录的值为null.HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致.如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 /**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁.Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40 /**
* Maps the specified <code>key</code> to the specified
* <code>value</code> in this hashtable. Neither the key nor the
* value can be <code>null</code>. <p>
*
* The value can be retrieved by calling the <code>get</code> method
* with a key that is equal to the original key.
*
* @param key the hashtable key
* @param value the value
* @return the previous value of the specified key in this hashtable,
* or <code>null</code> if it did not have one
* @exception NullPointerException if the key or value is
* <code>null</code>
* @see Object#equals(Object)
* @see #get(Object)
*/
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序.
(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的.如果使用排序的映射,建议使用TreeMap.在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常.
实现方式:
- LinkedHashMap是继承于HashMap,是基于HashMap和双向链表来实现的;
- TreeMap基于SortedMap实现,
元素顺序性:
- HashMap无序;LinkedHashMap有序,TreeMap有序(主要用于Map的排序,能够把它保存的记录根据键排序.默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator 遍历TreeMap时,得到的记录是排过序的)
线程安全性:
- LinkedHashMap,HashMap,TreeMap都是线程不安全的;