MENU

HashMap详解

2020-05-15 • Code

数据结构

JDK1.7 HashMap 底层使用数组和单向链表,JDK1.8 增加了红黑树,在链表长度超过 8 时就将链表变成红黑树,长度小于 6 时又会切换为链表。

▲HashMap 数据结构
  • 数组

    数据查询快,通过索引定位数据,时间复杂度为 O(1) ,插入删除慢 时间复杂度为 O(n)。

    transient Node<K,V>[] table;
    
  • 链表

    分单向和双向链表 数据插入删除很快,查询慢。

static class Node<K,V> implements Map.Entry<K,V> {
 final int hash;
 final K key;
 V value;
 Node<K,V> next;
}
  • 红黑树

    一种特殊的二叉树, 插入效率比平衡二叉树高,查询效率比普通二叉树高,所以选择性能相对折中的红黑树。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
 TreeNode<K,V> parent;  // red-black tree links
 TreeNode<K,V> left;
 TreeNode<K,V> right;
 TreeNode<K,V> prev;    // needed to unlink next upon deletion
 boolean red;
}

使用场景

数据分组、统计、缓存。

关键参数

// 哈希桶数组  用来保存键值对,使用的时候才初始化,使用过程中会动态扩容
//但长度必须是 2	的 n 次幂,可通过构造方法修改
transient Node<K,V>[] table;

//哈希桶数组默认的长度 2^4=16
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 //哈希桶数组最大的长度 2^30
 static final int MAXIMUM_CAPACITY = 1 << 30;

 //负载因子 默认0.75 用来计算数组扩容临界值 不建议修改
 /**
 *当我们调低负载因子时,HashMap 所能容纳的键值对数量变少。
 *扩容时,重新将键值对存储新的桶数组里,键的键之间产生的碰撞会下降,链表长度变短。
 *此时,HashMap 的增删改查等操作的效率将会变高,这里是典型的拿空间换时间。
*相反,如果增加负载因子(负载因子可以大于1),HashMap 所能容纳的键值对数量变多,空间利用率高,但碰撞率也高。
*这意味着链表长度变长,效率也随之降低,这种情况是拿时间换空间。
*/
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 //The next size value at which to resize (capacity * load factor).
 //扩容临界值 当数组内保存的键值对数量大于该值时将会对数组扩容
 int threshold;

// 链表转成树的阈值,当桶中链表长度大于8时转成红黑树
//经过计算,在hash函数设计合理的情况下,发生hash碰撞8次的几率为百万分之6
static final int TREEIFY_THRESHOLD = 8;

//进行resize操作时,若桶中数量少于6则从树转成链表
//如果hash碰撞次数在8附近徘徊,会一直发生链表和红黑树的转化
static final int UNTREEIFY_THRESHOLD = 6;

/**
* 当需要将解决 hash 冲突的链表转变为红黑树时,需要判断下此时数组容量,
 若是由于数组容量太小(小于 MIN_TREEIFY_CAPACITY )导致的 hash 冲突太多,
 *则不进行链表转变为红黑树操作,转为利用 resize() 函数对 hashMap 扩容
 */
static final int MIN_TREEIFY_CAPACITY = 64;

//存放具体健值对的集合
transient Set<Map.Entry<K,V>> entrySet;

//实际存储的键值对数量
transient int size;

//每次更改map结构的计数器
transient int modCount;

工作原理

HashMap 底层是由数组和单向链表实现,数组中的每个元素都是链表,由 Node 内部类(实现 Map.Entry 接口)实现,HashMap 通过 put & get 方法存储和获取数据。

put 方法

▲put 方法流程

具体执行步骤

  1. 判断键值对数组 table[i] 是否为空或为 null(new HashMap(); 完成后,如果没有put操作,是不会分配存储空间的),否则执行 resize() 进行扩容;

  2. 根据键值 key 计算 hash 值得到插入的数组索引 i,如果 table[i]==null,直接新建节点添加;

  3. 当 table[i]不为空,判断 table[i] 的首个元素是否和传入的 key 一样,如果相同直接覆盖 value;

  4. 判断 table[i] 是否为 treeNode,即 table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对;

  5. 遍历 table[i],判断链表长度是否大于 8,大于 8 的话把链表转换为红黑树 (同时需要满足数组长度大于 64 ),在红黑树中执行插入操作,否则进行链表的插入操作(JDK 1.7 之前使用头插法一般认为后插入的Entry被查找的可能性更大,JDK 1.8 使用尾插法);

  6. 遍历过程中若发现 key 已经存在直接覆盖 value 即可;

  7. 插入成功后,判断实际存在的键值对数量 size 是否大于扩容临界值 threshold,如果大于则进行扩容操作;

public V put(K key, V value) {
 // 调用hash(key)方法来计算hash 
 return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
 Node<K,V>[] tab; 
 Node<K,V> p; 
 int n, i;//n为数组长度,i为要存储健值对的数组索引
 //1、判断数组table是否为空或为null
 if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
 //2、计算并判断table[i]==null
 if ((p = tab[i = (n - 1) & hash]) == null)//等价于对 length 取余。
    tab[i] = newNode(hash, key, value, null);//为null直接新建数据
 else {
    Node<K,V> e; K k;
    //3、判断table[i]已存在数据的key和hash和要当前要保存的key和hash是否相等
    if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    else if (p instanceof TreeNode)//4、判断table[i] 是否为treeNode
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 放入红黑树中
    else {//5、遍历链表,并统计长度,是否大于8
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) { // 到达链表的尾部
                    p.next = newNode(hash, key, value, null);  //在尾部插入新结点
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 长度大于8,转红黑树结构
                            treeifyBin(tab, hash);
                    break;
            }
             //6、 判断链表中结点的key值与插入的元素的key值是否相等
            if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
            p = e;
        }
    }
     //判断要插入的键值对是否存,在 第 3 、6步判断的
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)// onlyIfAbsent 表示是否仅在 oldValue 为 null 的情况下更新键值对的值
                e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
 }
 ++modCount;
 if (++size > threshold)//7、判断size是否大于扩容临界值
 		resize();
 afterNodeInsertion(evict);
 return null;
}

get 方法

▲ get 方法流程
public V get(Object key) {
		Node<K,V> e;
		return (e = getNode(hash(key), key)) == null ? null : e.value;
}
 final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; 
    Node<K,V> first, e; 
    int n;
		K k;
    // 定位键值对所在桶的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 判断桶中第一项(数组元素)相等
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 桶中不止一个结点
        if ((e = first.next) != null) {
            // 是否是红黑树,是的话调用getTreeNode方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 不是红黑树的话,在链表中遍历查找    
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

hash计算

计算方法

通过 hashCode() 的高 16 位与其低 16 位进行异或实现的:(h = k.hashCode()) ^ (h >>> 16)。 保证了对象的 hashCode 的 32 位值只要有一位发生改变,hash() 返回值就会改变,使得 hash 更分散,减少碰撞可能性,这是高频操作位运算更高效

▲hash 计算
//获取hash值方法 也叫扰动函数
static final int hash(Object key) {
		int h;
   // 通过这种方式,让高位数据与低位数据进行异或,以此加大低位数据的随机性。
		return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

索引计算

把上一步计算获取的 hash 值 与数组长度 - 1 进行按位与运算,即可计算出数组索引。

由于数组长度是 2 的 n 次方,所以数组长度 -1的二进制位全为1,这种情况下,index 的结果等同于 hashCode 后几位的值。所以只要输入的 hashCode 本身分布均匀 index 也是均匀的。

//获取数组下标方法 jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
static int indexFor(int h, int length) {
     return h & (length-1);
}

hash 碰撞

指 key 不同,但 hashcode 相同,此时计算的数组索引也是相同的。

equals 与 hashCode

  1. 如果两个对象相等(即用 equals比 较返回 true ),那么它们的 hashCode 相同。

  2. 如果两个对象的 hashCode 相同,它们并不一定相等(即用 equals 比较返回false )。

  3. 如果两个对象的 hashCode 不相同,那它们一定不相等,即用 equals 比较返回false )。

  4. HashMap 存取数据过程中需要用到 hashCode 和 equals 方法来比较 key 是否相等,所以重写对象的 equals 方法时,要重写 hashCode 方法

动态扩容

初始容量

可通过构造方法指定初始容量

// 找到大于或等于 cap 的最小2的整数次幂的数,确保构造HashMap时传入的初始数组容量是 2 的 n 次方,比如10,则返回16。
static final int tableSizeFor(int cap) {
    int n = cap - 1;//让cap-1再赋值给n的目的是使得找到的目标值大于或等于原值
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;//int最大就2^32所以移动1、2、4、8、16位
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

▲容量计算

扩容机制

在 HashMap 中,数组的长度均是2的幂,阈值大小为桶数组长度与负载因子的乘积。当 HashMap 中的键值对数量超过阈值时,进行扩容。

HashMap 按当前桶数组长度的2倍进行扩容,阈值也变为原来的2倍(如果计算过程中,阈值溢出归零,则按阈值公式重新计算)。扩容之后,要重新计算键值对的位置,并把它们移动到合适的位置上去。

键值对在新数组中的位置只有两种,原下标位置或原下标+旧数组的大小。n 为table 的长度,图(a)表示扩容前的 key1 和 key2 两种key确定索引位置的示例,图(b)表示扩容后 key1 和 key2 两种 key 确定索引位置的示例,其中 hash1 是 key1对应的哈希与高位运算结果。

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:

因此,在扩充HashMap的时候,不需要像 JDK1.7 的实现那样重新计算 hash,只需要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了,是 0 的话索引没变,是 1 的话索引变成“原索引+ oldCap ”,可以看看下图为 16 扩充为 32 的resize示意图:

这个设计非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的 1 bit 是 0 还是 1 可以认为是随机的,因此 resize 的过程,均匀的把之前的冲突的节点分散到新的 bucket 了。这一块就是 JDK1.8 新增的优化点。有一点注意区别,JDK1.7中 rehash 的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。

▲扩容流程
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;// 扩容前的node数组
    int oldCap = (oldTab == null) ? 0 : oldTab.length;//旧的容量
    int oldThr = threshold;//旧的阈值
    int newCap, newThr = 0;//新的容量、阈值初始化为0
    // 如果数组桶的容量大与0
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {//如果旧容量已经超过最大容量,让阈值也等于最大容量,以后不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果扩容后小于最大值 而且 旧数组桶大于初始容量16, 阈值左移1(扩大2倍)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果数组桶容量<=0 且 旧阈值 >0
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;  // 新容量=旧阈值
    // 如果数组桶容量<=0 且 旧阈值 <=0
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY; // 新容量=默认容量  
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);// 新阈值= 负载因子*默认容量
    }
    // 如果新阈值为0 重新计算阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
    }  
    threshold = newThr;  // 更新阈值
    @SuppressWarnings({"rawtypes","unchecked"})
        // 创建新数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 覆盖数组桶    
    table = newTab;
		//如果老的数组有数据,也就是是扩容而不是初始化,才执行下面的代码,否则初始化的到这里就可以结束了
    // 如果旧数组桶不是空,则遍历桶数组,并将键值对映射到新的桶数组中
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)//无 hash 冲突直接转移
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果是红黑树
                else if (e instanceof TreeNode)
                    // 重新映射时,需要对红黑树进行拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // 如果不是红黑树,则按链表处理
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                   	//从这条链表上第一个元素开始轮询,如果当前元素新增的bit是0,则放在当前这条链表上,如果是1,则放在"j+oldcap"这个位置上,生成“低位”和“高位”两个链表
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;//元素是不断的加到尾部的,不会像1.7里面一样会倒序
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 将分组后的链表映射到新桶中
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

优化内容

  1. 数组+链表改成了数组+链表或红黑树; 链表的插入方式从头插法改成了尾插法,简单说就是插入时,如果数组位置上已经有元素,1.7 将新元素放到数组中,原始节点作为新节点的后继节点,1.8 遍历链表,将元素放置到链表的最后。

  2. 扩容的时候 1.7 需要对原数组中的元素进行重新 hash 定位在新数组的位置,1.8 采用更简单的判断逻辑,位置不变或索引+旧容量大小。

  3. 在插入时,1.7 先判断是否需要扩容,再插入,1.8 先进行插入,插入完成再判断是否需要扩容。

参考资料

最后编辑于: 2020-05-16 00:21:39
文章列表 文章二维码
QR Code for this page
Tipping QR Code