关注互联网应用及运维技术的个人博客

HASHMAP源码解析

key、value 被 put 之后,会怎样进行存储

JDK1.7:数组+链表,JDK1.8:数组+链表+红黑树

存储流程简述

1、创建一个数组:Node[] table=new Node[16]

2、计算 key,value 组成Node对象到底存储在数组中的哪一个位置

这里有个细节,就是如果计算俩个位置都相同,那么就会存放到对应位置的列表中,也就是 Node 的 next

得到一个整数, key.hashCode(),控制这个数在0-15之间,也就是 key.hashCode() & 16=0-15

3、上面的内容,只是为了简要理解,在hashMap中做了优化,并不是直接取模那么简单

假设将 key.hashCode() 的结果转换为二进制

0000 0000 0010 0011 0001 1011 1111 1111  ## 假设 hashCode 的值为 2300927
0000 0000 0000 0000 0000 0000 0000 1111  ## 假设大小为 16,16-1=15,15的二进制是 1111
                                   1111  ## 得到的结果为 15

4、假如 ,key1、key2 参与计算的几位相同,比如得到的结果都是 15,那么就冲突了,此时会往下,顺延成链表的方式

5、为了使 hashCode() 的内容尽可能的不同,避免更多的链表形成,此时又将 key.hashCode,结果分为高低位

0000 0000 0100 0110
       ^
0001 1011 1111 1111

6、此时 第三步 中的计算需要更改

key.hashCode() ^ key.hashCode() >>> 16

7、为什么大小必须要是 2 的幂数

HashMap 存储数据时要避免位置碰撞且数据分配均匀,于是采用位移运算的算法计算存储链表的位置

假设HashMap 的长度不为2的幂次方则有可能产生碰撞

3&(9-1)=0  2&(9-1)=0 ## 产生了hash碰撞
3&(8-1)=3  2&(8-1)=2 ## 不同位置

源码解析

首先会从 put() 进入

  1. 当桶数组 table 为空时,通过扩容的方式初始化 table
  2. 查找要插入的键值对是否已经存在,存在的话根据条件判断是否用新值替换旧值
  3. 如果不存在,则将键值对链入链表中,并根据链表长度决定是否将链表转为红黑树
  4. 判断键值对数量是否大于阈值,大于的话则进行扩容操作
 public V put(K key, V value) {
     // 首先会计算 hash 值 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
     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; 
    if ((tab = table) == null || (n = tab.length) == 0) // 判断数组是否为空
        n = (tab = resize()).length; // 进行初始化,并且通过 n 保存数组大小
    // 根据 hash 值判断要存在哪一个位置
    // 判断 要保存的位置是否有元素
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 保存到计算好的位置当中
    // 有元素,不能直接保存到数组
    // 如果 key 的内容相同,则会直接覆盖
    // 如果 key 的内容不同,以链表的方式或者红黑树的方式存储
    else {
        Node<K,V> e; K k; 
        // 如果 hash 相同,并且 key 相同,使用一个 临时变量 e 进行保存
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 链表
        else {
            // 循环遍历当前链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { // 不断的查看 next 是否为空
                     // 创建一个新的节点并赋值到当前节点的下一个节点
                    p.next = newNode(hash, key, value, null);
                    // static final int TREEIFY_THRESHOLD = 8
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash); // 链表长度超过了阈值,转为红黑树
                    break;// 退出循环
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 不为空说明已经设置了节点,则会使用 新的值,替换老的值并且返回
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 当数组数量超过了阈值,触发扩容
    // throshold= (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)=0.75*16=12
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

resize

  1. 计算新桶数组的容量 newCap 和新阈值 newThr
  2. 根据计算出的 newCap 创建新的桶数组,桶数组 table 也是在这里进行初始化的
  3. 将键值对节点重新映射到新的桶数组里。如果节点是 TreeNode 类型,则需要拆分红黑树
  4. 如果是普通节点,则节点按原顺序进行分组
final Node<K,V>[] resize() {
 Node<K,V>[] oldTab = table; // 复制旧的数组
 int oldCap = (oldTab == null) ? 0 : oldTab.length;// 第一次进入会返回0,因为还没有创建数组
 int oldThr = threshold; // 保存旧的阈值
 int newCap, newThr = 0;
 if (oldCap > 0) {
     if (oldCap >= MAXIMUM_CAPACITY) { // 最大值,不再进行扩容
         threshold = Integer.MAX_VALUE;
         return oldTab;
     }
     // oldCap << 1 会增加一倍
     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
              oldCap >= DEFAULT_INITIAL_CAPACITY)
         newThr = oldThr << 1; // 修改扩容的标准,从最开始默认的12变成24
 }
 else if (oldThr > 0) // 初始容量设置为阈值
     newCap = oldThr;
 else {               // 第一次进入时会执行这里
     newCap = DEFAULT_INITIAL_CAPACITY; // 取得默认大小 16 
     newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 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;
 // 重新散列,将老数组中的Node对象移动到新的数组当中
 // 遍历数组下标不为空的节点,随后根据三种情况进行处理
 //       只有一个元素
 //       是一个链表
 //       是一个红黑树   
 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) // 只有一个元素
                 newTab[e.hash & (newCap - 1)] = e;// 直接移动到新的数组当中
             else if (e instanceof TreeNode)// 红黑树
                 // 打散,移动
                 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
             else { // 链表
                 // 这里的存储,分为俩个,链表一会存在于原索引,链表二存于原索引加上原hash桶长度的偏移量
                 Node<K,V> loHead = null, loTail = null;
                 Node<K,V> hiHead = null, hiTail = null;
                 Node<K,V> next;
                 do {
                     next = e.next;
                     // 这里不需要变化
                     if ((e.hash & oldCap) == 0) {
                         if (loTail == null)
                             loHead = e;
                         else
                             loTail.next = e;
                         loTail = e;
                     }
                     // 索引修改为 原索引+原hash桶长度
                     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; // 返回新的数组
 }

从 get() 进入

public V get(Object key) {
    Node<K,V> e; 
    // 首先使用 key 计算 hash 值,并且将 key 传递,如果不为空,则直接返回 value
    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) { 
            // first 是 TreeNode 类型,调用红黑树查找方法
            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;
}

为什么不是直接构建红黑树

当链表长度小于8时,空间复杂度和时间复杂度小于 红黑数

为什么扩容需要是2倍

must be a power of two,必须是2的N次幂

移动数据时,下标如何分配

复制移动数据的时候,比如当前下标2,要么还是2,要么是2+16=18

0000 0000 0010 0011 0001 1011 1111 1111  ## 假设 hashCode 的值为 2300927
0000 0000 0000 0000 0000 0000 0000 1111  ## 假设大小为 16
0000 0000 0000 0000 0000 0000 0001 1111  ## 假设大小为 32
____________________________数据迁移____________________________
old  0000 0000 0010 0011 0001 1011 1111 1111 
     0000 0000 0000 0000 0000 0000 0000 0010
     0000 0000 0000 0000 0000 0000 0000 0010  ## index = 2

new  0000 0000 0010 0011 0001 1011 1111 1111
     0000 0000 0000 0000 0000 0000 0001 0010
     0000 0000 0000 0000 0000 0000 0001 0010  ## index = 18

为什么迁移的时候有高低位俩条链

hashCode 倒数5位为0的,保留在原来的位置
hashCode 倒数5位为1的,原先下标 + 原hash桶长度的偏移量

赞(0)
未经允许不得转载:飞天狒狒 » HASHMAP源码解析

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址