JAVA 基础笔记(一)HashMap 实现原理与源码解析
九涅·烧包包儿 / / / 阅读量
> Author: shaobaobaoer
> Mail: shaobaobaoer@126.com
> WebSite: shaobaobaoer.cn
>  Time: Sunday, 26. July 2020 11:52AM

HashMap 继承关系

Map 是 Key-Value 对映射的抽象接口,该映射不包括重复的键,即一个键对应一个值。

HashMap 是基于哈希表的 Map 接口的实现,以 Key-Value 的形式存在,即存储的对象是 Entry (同时包含了 Key 和 Value) 。

在HashMap中,其会根据hash算法来计算key-value的存储位置并进行快速存取。特别地,HashMap最多只允许一条 Entry 的键为Null(多条会覆盖),但允许多条Entry的值为Null。此外,HashMap 是 Map 的一个非同步的实现。

TIM图片20200726103023.png-15.6kB
必须指出的是,虽然容器号称存储的是 Java 对象,但实际上并不会真正将 Java 对象放入容器中,只是在容器中保留这些对象的引用。也就是说,Java 容器实际上包含的是引用变量,而这些引用变量指向了我们要实际保存的 Java 对象。(justloveyou_)

HashMap 构造函数

HashMap 一共提供了四个构造函数,其中 默认无参的构造函数 和 参数为Map的构造函数 为 Java Collection Framework 规范的推荐实现,其余两个构造函数则是 HashMap 专门提供的。

1. public HashMap()

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

装填因子为0.75,其他数值都是默认的

2. HashMap(int initialCapacity, float loadFactor)

public HashMap(int initialCapacity, float loadFactor) {
        //初始容量不能小于 0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY) // 不大于2**30
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 装填因子不能小于0
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); //  HashMap 的容量必须是2的幂次方,超过 initialCapacity 的最小 2^n 
}
    
static final int tableSizeFor(int cap) {
    int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

3. public HashMap(int initialCapacity)

public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

该方法将直接调用2

4. public HashMap(Map<? extends K, ? extends V> m)

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

装载默认的装填因子,随后初始化table

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
        if (table == null) { // pre-size
        // 在构造函数4的时候,table一定是null的,因此这么搞
        // 构造一个与指定 Map 具有相同映射的 HashMap,其 初始容量不小于 16 (具体依赖于指定Map的大小),负载因子是 0.75
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        } else {
            // Because of linked-list bucket constraints, we cannot
            // expand all at once, but can reduce total resize
            // effort by repeated doubling now vs later
            while (s > threshold && table.length < MAXIMUM_CAPACITY)
                resize();
        }
        // 之后将Map里的东西重新塞进去。putVal函数会涉及到很细节的东西,下文细说
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

HashMap 数据结构

我们知道,在Java中最常用的两种结构是 数组 和 链表,几乎所有的数据结构都可以利用这两种来组合实现,HashMap 就是这种应用的一个典型。

实际上,HashMap 就是一个 链表数组,采用拉链法构建链表,如下所示:

20170317181650025.png-12.8kB

后来JDK1.8之后,在table数组拉链法的基础上,当链表长度大于8之后,链表将自动转化为红黑树。利用红黑树快速增删改查的特点提高HashMap的性能。JDK1.8之后,HashMap table数组的样子如下所示:

8db4a3bdfb238da1a1c4431d2b6e075c_b.png-68.7kB

其中,table数组的重要性不言而喻,其是通过Node类实现的(JDK<1.8为Entry类,实际上它们都实现了Map.Entry接口)

transient Node<K,V>[] table;

Node为HashMap的内部类,实现了 Map.Entry 接口,其包含了键key、值value、下一个节点next,以及hash值四个属性。是哈希表所存储的元素的具体形式。

HashMap的快速存取

在HashMap中,我们最常用的两个操作就是:put(Key,Value) 和 get(Key)。我们都知道,HashMap中的Key是唯一的,那它是如何保证唯一性的呢?

确定哈希桶数组(table数组)索引位置。

定位Hash元素是增删改的基础,我们当然希望这个HashMap里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个,不用遍历链表,大大优化了查询的效率。

来看看hash的实现方式

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// 该方法仅存在与jdk1.7中
static int indexFor(int h, int length) {  
    return h & (length-1); 
}

// 在jdk1.8后,该部分代码被挪了出来,写到了取桶索引的地方。
i = (n - 1) & hash(Object)

归纳来说,Hash算法为三步

  • 取key的hashCode值
  • 取高位字节码,与字节码异或
  • 取模

在JDK1.8的实现中,通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在数组table的length比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中.

保存元素与put方法

之前讲到了putVal方法,这是HashMap的非常重要的函数,它定义了插入HashMap元素的方法。网上找到了一张图,可以很形象得说明这个过程

此处输入图片的描述
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // 创建一个 Node
    // 
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // (1) 如果table 为空则创建一个table,大小在resize()方法中有规定
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // (2) 计算 index (链的位置)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null); // 如果没有哈希冲突,非常棒棒,直接插入
    else {
        Node<K,V> e; K k;
        // (3) 判断节点key是否存在
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; // 如果正好节点的key与待插入节点的key相同,则直接覆盖掉key
        // (4) 判断该链是否为红黑树链
        else if (p instanceof TreeNode)
            // 如果是,则用红黑树的方法将带插入节点插入链中
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
        // (5) 否则该链为链表
            for (int binCount = 0; ; ++binCount) {
            // 存在哈希冲突,没有关系,创建一个新的节点e,其为p.next
                if ((e = p.next) == null) {
                // 将新节点插入链表
                    p.next = newNode(hash, key, value, null);
                // 如果链表长度大于8,则转化为红黑树处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                 // 如果正好节点的key与待插入节点的key相同,则直接覆盖掉key
                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;
    // (6) 扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

扩容机制与resize()

这里参考了https://blog.csdn.net/weixin_43664418/article/details/102164483 老哥的文章。

扩容(resize)就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组。

≤JDK1.7

JDK1.8版本往上引入红黑树后,resize变得较为复杂。先来看一下JDK1.7的resize方法(其中的Entry类就是>1.8的Node类)

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;

    // 若 oldCapacity 已达到最大值,直接将 threshold 设为 Integer.MAX_VALUE
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        threshold = Integer.MAX_VALUE;
        return;             // 直接返回
    }

    // 否则,创建一个更大的数组
    Entry[] newTable = new Entry[newCapacity];

    //将每条Entry重新哈希到新的数组中
    transfer(newTable);

    table = newTable;
    threshold = (int)(newCapacity * loadFactor);  // 重新设定 threshold
}

void transfer(Entry[] newTable) {
    // 将原数组 table 赋给数组 src
    Entry[] src = table;
    int newCapacity = newTable.length;

    // 将数组 src 中的每条链重新添加到 newTable 中
    for (int j = 0; j < src.length; j++) {
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;   // src 回收

            // 将每条链的每个元素依次添加到 newTable 中相应的桶中
            do {
                Entry<K,V> next = e.next;
                // e.hash指的是 hash(key.hashCode())的返回值;
                // 计算在newTable中的位置,注意原来在同一条子链上的元素可能被分配到不同的子链
                int i = indexFor(e.hash, newCapacity); // indexFor 见确定索引位置的方法中
                // int i= e.hash & (newCapacity-1); 实际对应如下这条语句
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

仔细观察将每条链的每个元素依次添加到 newTable 中相应的桶中的操作,不难发现这是一个头插法重建链表的操作。相信这对于学过数据结构的你来讲不难看懂。

很有意思的是,由于newCapacity变得比原来大了。这就会导致有些链会被分解开。这并不要紧,因为现在的获取桶位置的方法已经从e.hash & (oldCapacity-1)=>e.hash & (newCapacity-1)了。

具体流程可以看下面的图片

此处输入图片的描述

≥JDK1.8

在JDK1.8中,现在使用了是2次幂的扩展(也就是长度扩为原来2倍),所以,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。

看下图可以明白这句话的意思

设n为table的长度

  • 图(a)表示扩容前的key1和key2两种key确定索引位置的示例
  • 图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希与高位运算结果。
此处输入图片的描述

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色)。因此在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看看原来的hash值新增的那个bit是1还是0就好了,是0的话索引没变,是1的话索引变成“原索引+oldCapacity”。这个Mask就是指最高位了。

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

此处输入图片的描述
 final Node<K,V>[] resize() {
     Node<K,V>[] oldTab = table;
     int oldCap = (oldTab == null) ? : oldTab.length; 
     int oldThr = threshold;
     int newCap, newThr = 0;
     if (oldCap > 0) {
         // 超过最大值就不再扩充了
         if (oldCap >= MAXIMUM_CAPACITY) {
             threshold = Integer.MAX_VALUE;
           return oldTab;
       }
       // 没超过最大值,就扩充为原来的2倍
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // 扩展为两倍
   }
   else if (oldThr > 0) // 如果原本的阈值大于0,则保留
       newCap = oldThr;
   else {               // 如果原本的阈值等于0(也就是构造函数中调用)则使用默认参数
       newCap = DEFAULT_INITIAL_CAPACITY;
       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
   }
   // 计算新的resize上限
   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) {
       // 把每个bucket都移动到新的buckets中
       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;
                       // 原索引 
                       // 判断高位结果和低位结果的方法是与原oldCapicity做&,为零就是低位
                       if ((e.hash & oldCap) == 0) {
                           if (loTail == null)
                               loHead = e;
                           else
                               loTail.next = e;
                           loTail = e;
                       }
                       // 原索引+oldCapacity
                       else {
                           if (hiTail == null)
                               hiHead = e;
                           else
                               hiTail.next = e;
                           hiTail = e;
                       }
                   } while ((e = next) != null);
                   // 原索引放到 table 里
                   if (loTail != null) {
                       loTail.next = null;
                       newTab[j] = loHead;
                   }
                   // 原索引+oldCap放到 table 里
                   if (hiTail != null) {
                       hiTail.next = null;
                       newTab[j + oldCap] = hiHead;
                   }
               }
           }
       }
   }
   return newTab; // 返回table
}

获取元素与get方法

获取元素采用的是.get方法,其中涉及到的一个内部函数getNode,讲解在代码中

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) {
        // 如果table数组不为空,长度大于0,且锁定到桶首节点后,该节点非空
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k)))) // 正好key相等,发挥
            return first;
        if ((e = first.next) != null) { // 若key不相等,则查找下一个元素
            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;
}
支付宝捐赠
请使用支付宝扫一扫进行捐赠
微信捐赠
请使用微信扫一扫进行赞赏
有 0 篇文章