HashMap

Hory
Java Collection
Page content

简介

HashMap 继承 AbstractMap 抽象类，实现Map接口、Cloneable接口、Serializable接口。称为“链表的数组”，一个数组中，每个元素存储的是一个链表的头结点。

它是数组加链表组成的数据结构，数组中每个地方都存了Key-Value这样的实例，在Java7叫Entry，Java8中叫Node。每一个节点都会保存自身的hash、key、value、以及下个节点，Node的源码如下：

1static class Node<K,V> implements Map.Entry<K,V> {
2    final int hash;
3    final K key;
4    V value;
5    Node<K,V> next;
6  	...
7}

哈希

常见的求哈希值的函数：

  1. 直接定址法

  • 取关键字的某个线性函数为散列地址

  • Hash(Key) = A * Key + B

  • 适合查找比较小且连续的情况

  1. 除留余数法
  • 设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数，按照哈希函数：Hash( key ) = key % p ( p <= m) ，将关键码转换成哈希地址。

  1. 平方取中法

  2. 折叠法

  3. 随机数法

  4. 数学分析法

那么这些元素是按照什么样的规则存储到数组中呢？为什么数组长度设置为$2^n$？

一般情况是通过 hash(key)%len 获得，也就是元素的key的哈希值对数组长度取模得到。

哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。

Hash 值的范围值 -2147483648 到 2147483647，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的，用之前还要先做对数组的长度取模运算。这个数组下标的计算方法是“ hash & (n - 1)”（n代表数组长度）。

本来模质数可以减少碰撞的几率（至于为什么模质数可以减少碰撞的几率，有个数学推导，比较复杂，感兴趣的话可以了解一下），但是取余(%)操作中如果除数是2的幂次则等价于与其除数减一的与(&)操作

  • 也就是说 hash%length == hash&(length-1) 的前提是：length 是 2 的 n 次方

  • 且采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是2的幂次方。

  • length = $2^n$ ，则length-1 = $2^n$ -1，都是11111结尾的，只有1&1才等于1，所以碰撞几率小。

为啥我们重写equals方法的时候需要重写hashCode方法呢？能用HashMap给我举个例子么？

因为在Java中，所有的对象都是继承于Object类。Object类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。

在未重写equals方法时，继承了object的equals方法是比较两个对象的内存地址，显然new的2个对象内存地址肯定不一样

  • 对于值对象，==比较的是两个对象的值
  • 对于引用对象，==比较的是两个对象的地址

HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了。

get的时候，根据key去hash然后计算出index，那么如何找到index相同时（同一个链表中）的两个不同的值呢？

equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

初始化

1DEFAULT_INITIAL_CAPACITY = 16; 
2MAXIMUM_CAPACITY = 1 << 30;    // 最大容量：2的30次方：1073741824
3DEFAULT_LOAD_FACTOR = 0.75f;

其中传参构造方法：

1public HashMap(int initialCapacity, float loadFactor){ 
2  //···
3  int capacity = 1;
4  while (capacity < initialCapacity)  
5          capacity <<= 1;
6  //···
7}
  • 该代码的意思是，实际的开辟的空间要大于传入的第一个参数的值。

为什么默认初始化长度是16

在JDK1.8的 236 行有1«4就是16，为啥用位运算呢？直接写16不好么？

1static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

扩容机制

JDK1.7 使用数组+链表；JDK1.8使用数组+链表+红黑树。

链表长度大于8转为红黑树，红黑树的节点数小于6转化为链表。

装载因子

loadFactor装载因子：用来衡量 HashMap 满的程度。

  • loadFactor = size/capacity
  • threshold = capacity * loadFactor

当元素个数达到threshold就会触发扩容（resize）

装载因子非常重要，应严格限制在 0.7~0.8 以下，默认的装载因子为0.75， 是对空间和时间效率的一个平衡选择。超过 0.8 ，查表时的CPU缓存按照指数曲线上升。

如果内存空间很多而又对时间效率要求很高，可以降低 loadFactor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，这个值可以大于1。

装载因子调小，这样比较容易触发扩容机制，扩容机制触发，占用更多的内存空间，但是可以减少桶内部的链表化和树形化，从而增加查找效率，也就是以空间换时间。

扩容分为两步：

  1. 扩容：创建一个新的Entry空数组，长度是原数组的2倍。
  2. ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

为什么是重哈希而不是直接复制过去？

因为长度扩大以后，Hash的规则也随之改变。

  • Hash的公式：index = HashCode(Key)%Length = HashCode(Key) & (Length - 1)

JDK1.8中扩容机制改进

总结有以下几点：

  1. 扩容机制：1.7传参自定义newcap；JDK1.8使用的是2次幂扩展
  2. JDK1.7扩容后需要重哈希；JDK1.8不需要重哈希
  3. JDK1.7采用头插；JDK1.7采用尾插
  4. JDK1.8中hashCode()函数的改进，通过hashCode()的高16位异或低16位来实现，优化后可以减少碰撞率

上面讲的是JDK1.8之前的版本，如果扩容前capasity = $2^n$ ，扩容后capasity = $2^{n+1}$，扩容涉及到rehash、复制数据等操作，所以非常耗能。

相比于JDK1.7，JDK1.8使用的是2次幂的扩展（指长度扩为原来2倍），所以，元素的位置要么是在原位置，要么是在原位置再移动 $2^n$ 的位置。

  • resize() 1.7传参自定义newcap，1.8自动扩容2倍

JDK1.8在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。（JDK1.8HashMap扩容优化）

这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。

1// 该语句判断是否落在“原索引”，还是落在“原索引+oldCap”
2if ((e.hash & oldCap) == 0){} //原索引
3else{} //原索引+oldCap

此外，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（采用头插法），但JDK1.8不会倒置（采用尾插法）。

  • 采用头插法，高并发容易引起循环链表，所以采用尾插法。

JDK1.8中hash()改进

在 JDK1.8 中还有个高位参与运算，hashCode() 得到的是一个32位 int 类型的值，通过hashCode()的高16位 异或 低16位（将高16位渗透到低16位中）实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

  • key.hashCode()是固定的，JDK1.8的hash()是优化后的key.hashCode()，而JDK1.7的hash()是直接用的 key.hashCode()。
  • 优化过程(原文) ：key.hashCode() ^ (h »> 16)
  • 加工后，key.hashCode() 的低16位有更好的性能，减少碰撞率
1static final int hash(Object key) {
2   int h;
3   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
4}     
5i = (table.length - 1) & hash;  //这一步是在后面添加元素putVal()方法中进行位置的确定

插入元素

Java8之前是头插法，因为写这个代码的作者认为后来的值被查找的可能性更大一点，可以提升查找的效率。Java8之后，都是采用尾插法。

为什么改用尾插法？

并发情况下，HashMap在扩容时使用头插法可能出现循环链表，后果就是调用get()方法时可能陷入死循环。

为什么采用头插法会出现循环链表？

https://blog.csdn.net/littlehaes/article/details/105241194

JDK1.7的rsize()内部会调用transfer()，JDK1.8的rsize()内部没有了transfer()方法，而是直接将transfer()写在了rsize()内部。

 1void transfer(Entry[] newTable){
 2    Entry[] src=table;
 3    int newCapacity=newTable.length;
 4    for(int j=0;j<src.length;j++){
 5        Entry<K, V> e=src[j];
 6        if(e!=null){
 7            src[j]=null;
 8            do{
 9                Entry<K, V> next=e.next; //保存下一次循环的Entry
10                //在新的table 中求得适合插入的位置
11                int i=indexFor(e.hash, newCapacity);
12                e.next=newTable[i];//  如果I位置原来没有值，则直接插入；有值，采用链头插入法
13                newTable[i]=e;
14
15                //轮替，下一次循环
16                e=next;
17            }while(e!=null);
18        }
19    }
20}
  • 并发HashMap的put操作引起死循环
  • 因为多线程会导致HashMap的Entry链表形成环形数据结构，查找时会陷入死循环。
  • 扩容后，内部调用transfer方法（把旧表中的元素添加到新表中），这就是HashMap并发时，会引起死循环的根本原因所在。

JDK1.8在同样的并发场景下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系。

那是不是意味着Java8就可以把HashMap用在多线程中呢？

即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。

碰撞

处理碰撞的两种方法：

  1. 开放地址法

  2. 链地址法

遍历元素

四种方法：

  1. 分别获取 key 集合和 value 集合；
  2. 获取 key 集合，然后遍历key集合，根据key分别得到相应value；
  3. 得到 Entry 集合，然后遍历 Entry；
  4. 迭代。

基本上使用方法3性能是最好的，且在遍历的过程（方法3）中我们可以对集合中的元素进行删除；方法2效率很低，不推荐使用；方法4效率也挺好。