HashMap源码剖析

作者: linzeliang
  1. HashMap继承结构

image-20210924204750139

  1. HashMap底层数据结构

在1.7及其之前,HashMap底层是使用 数组 + 链表实现的,在1.8及其之后,使用了 数组 + 链表/红黑树 实现。

来看下1.7的储存结构图:

image-20210924200421961

其中链表使用内部类Node来实现的:

image-20210924205026504

数组+链表(散列表) 其实就是用于解决哈希冲突使用的一个拉链法方法。在数据结构中,们处理hash冲突常使用的方法有:开发定址法、再哈希法、链地址法、建立公共溢出区。而HashMap中处理hash冲突的方法就是链地址法。

但是这样子的话,如果使用了很久,HashMap存储的元素越来越多,那么链表就会变的很长,那么性能就会下降很多(因为链表不适合查找元素,每次查找元素都要从头开始遍历)。

于是在1.8的时候进行了改进,使用到了红黑树(红黑树是一个自平衡的二叉查找树,查找效率是非常高,时间复杂度仅为O(logN))。

image-20210924203138870

在HashMap中,链表转化成红黑树的条件是当链表长度大于8数组(桶)的个数要大雨等于64个时,才可以将链表转化成红黑树,它们在源码中的定义如下:

static final int MIN_TREEIFY_CAPACITY = 64; // 转化成红黑树的最小的桶容量
static final int TREEIFY_THRESHOLD = 8; // 桶上的元素的数量

treeifyBin中的片段:

// 意思是只要桶的个数小于64个,那么即使桶中的元素个数超过了8个,那么就进行resize扩容,而不是转化成红黑树
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)  
    resize();

putVal中的片段:

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);
    // -1 for 1st 可以理解为元素下表从-1开始的,所以可以看作binCount >= 9
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
        treeifyBin(tab, hash);
    break;
}
  1. HashMap的属性
// 默认的初始容量,左移位4位相当于:1*2*2*2*2=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
```java
// 最大的容量:2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
```java
// 默认装载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
```java
// 当一个元素被添加到至少有8个节点的桶中,桶中的链表将会被转化成红黑树,即转化成红黑树条件是大于8个
static final int TREEIFY_THRESHOLD = 8;
```java
// 红黑树退化成链表的条件:小于等于6时退化
static final int UNTREEIFY_THRESHOLD = 6;
```java
// 转化成红黑树的最小的桶的数量
static final int MIN_TREEIFY_CAPACITY = 64;

成员属性有如下:

image-20210924204641256

  1. 构造方法

一共有4个构造方法:

image-20210924213501347

其中,核心的构造方法是:

public HashMap(int initialCapacity, float loadFactor) {
    // 保证初始容量大于等于0,否则抛出异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    // 保证初始容量不大于最大容量,超过了就讲初始容量设置为最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // 保证装载因子大于0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    // 初始化装载因子为0.75
    // 当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为加载因子,每个碰撞位置的链表长度超过8个是几乎不可能的。当桶中元素到达8个的时候,概率已经变得非常小,也就是说用0.75作为加载因子,每个碰撞位置的链表长度超过8个是几乎不可能的。
    this.loadFactor = loadFactor;
    // threshold这个成员变量是阈值,决定了是否要将散列表再散列,它的值应该是:capacity * load factor
    // 但是这里的threshold并不是真正的初始化阈值,正在的初始化阈值时在resize的时候进行初始化(而此时的threshold并不是没有用,而是待会在初始化容量时候要用的初始值)
    this.threshold = tableSizeFor(initialCapacity);
}

在初始化阈值容量的时候,调用了tableSizeFor方法:

// 这个方法返回大于输入数字的最近的2的整数次幂的数
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
  1. put方法

put方法其实是调用了putVal方法的,调用方法的同时把计算好的key的哈希值传入,putVal方法:

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<K,V>[] tab;
    Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        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) {
                    p.next = newNode(hash, key, value, null);
                    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;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put的过程如下

Node<K,V>[] tab; // tab表示的是哈希数组
Node<K,V> p; // p表示的是数组的第一个节点
Node<K,V> e; // e表示该key是否已经存在,为null表示不存在
  1. put方法接收传入key与value:put(K key, V value)

  2. 计算出key的哈希值,这里计算的哈希值方法是key的hashcode与hashcode的高16位进行异或运算得到的结果

    static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
  3. 将计算得到的哈希值、key、value传给putVal方法

  4. 在putVal方法中,先判断哈希数组是否为空,如果为空的话就resize初始化tab,创建新的数组

    // 判断tab是否为空
    if ((tab = table) == null || (n = tab.length) == 0)
       n = (tab = resize()).length;
    
  5. 如果存在哈希表,则计算key对应的索引位置:p = tab[i = (n - 1) & hash,使用length-1hash进行逻辑与运算(因为在做&运算的时候,仅仅是后4位有效 ,那么如果key的哈希值低位变化不大,高位变化大 ,那么在计算的时候发生哈希冲突的可能性也增大许多,所以上面在计算哈希的时候将hash与hash的高16为进行异或运算得到结果作为哈希值,增加了随机性),如果改索引位置还没有节点,那么就直接插入到该位置即可!

    if ((p = tab[i = (n - 1) & hash]) == null)
       tab[i] = newNode(hash, key, value, null);
    
  6. 如果该桶上有元素的话,就根据该桶的结构是红黑树还是链表进行插入,然后返回结果赋值给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) {
               p.next = newNode(hash, key, value, null);
               // 判断是否要转化成红黑树结构
               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;
       }
    }
    
  7. 如果e是为null,就说明该key不存在,直接插入,如果不为null,说明key已经存在,直接将覆盖原来的value,并返回

  8. 插入成功之后,还要判断一下实际存在的键值对的数量size是否大于阈值threshold,如果大于那么就扩容

  9. 扩容

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        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()
    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)
                    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;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            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. 先判断原来的容量是否大于0

  2. 如果大于0的话且大于等于最大容量,就将阈值设置为Integer.MAX_VALUE,然后啥也不干

    如果大于0的话且小于于最大容量就将旧的容量扩容为原来的两倍,同时也将旧的阈值扩大为原来的两倍

    if (oldCap > 0) {
       if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
       }
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // double threshold
    }
    
  3. 如果初始容量未制定或者小于等于0(就是HashMap构造方法的那种情况,只初始化了threshold阈值),那么就将阈值作为初始化容量(此时阈值是2的整数次幂,HashMap的容量要为2的整数次幂)

    else if (oldThr > 0) // initial capacity was placed in threshold
       newCap = oldThr;
    
  4. 剩下的情况就是初始容量没有设定,阈值也没有设定,那么容量就用默认的DEFAULT_INITIAL_CAPACITY,阈值则为:(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)

    else {               // zero initial threshold signifies using defaults
       newCap = DEFAULT_INITIAL_CAPACITY;
       newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
  5. 如果新容量的阈值为设定,那么就设定下:

    if (newThr == 0) {
         float ft = (float)newCap * loadFactor;
         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                         (int)ft : Integer.MAX_VALUE);
    }
    
  6. 刷新当前容量的阈值

    threshold = newThr;
    
  7. 最后就是将旧的数据复制到新数组里面,有两种情况:

  8. 扩容后,若hash值新增参与运算的位=0,那么元素在扩容后的位置=原始位置

  9. 扩容后,若hash值新增参与运算的位=1,那么元素在扩容后的位置=原始位置+扩容后的旧位置

    扩容后长度为原hash表的2倍,于是把hash表分为两半,分为低位和高位,如果能把原链表的键值对, 一半放在低位,一半放在高位,而且是通过e.hash & oldCap == 0来判断。因此有50%的概率放在新hash表低位,50%的概率放在新hash表高位。

  10. get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

get方法的实现就是计算key的hash值,然后通过getNode获取对应的value

  1. remove方法
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

remove方法也是通过计算key的hash,调用removeNode来删除元素的

  1. HashMap的一些特性

  2. 允许key和value为null

  3. 除了允许为努力了和同步,其他的和HashTable一样

  4. 不保证有序

  5. 初始容量太高或者太低对便利都不太好

  6. 当哈希表容量超过初始容量*装载因子时,哈希表会进行再散裂,桶数量*2

  7. 不同步,想要同步可以使用Collections工具类实现Map m = Collections.synchronizedMap(new HashMap(...));

  8. 装载因子默认是0.75,设置高虽然会减少空间,但是遍历的开销会增加。因此在设置初始容量时,应该考虑好装载因子和容量的大小,如果设置的好,就不用再散裂了

    原文创作:linzeliang

    原文链接:https://www.cnblogs.com/linzeliang1222/p/15332926.html

更多推荐

更多
  • Dubbo源码解读与实战-41加餐:一键通关服务发布全流程 41 加餐:一键联 Dubbo 中的这些核心实现,分析 Dubbo**服务发布** 和**服务引用**的全流程,帮助你将之前课时介绍的独立知识点联系起来,形成一个完整整体。 本课时我们就先来重点关注 Provider 节点发布服务的过
  • Dubbo源码解读与实战-42加餐:服务引用流程全解析 42 加餐:已经分析了服务发布的核心流程。那么在本课时,我们就接着深入分析**服务引用的核心流程**。 Dubbo 支持两种方式引用远程的服务: **服务直连的方式** ,仅适合在**调试服务**的时候使用; **基于注册中心引用服
  • Dubbo源码解读与实战-36负载均衡:公平公正物尽其用的负载均衡策略,这里都有(下) 36 负载均衡:公平公正物尽其用的负载均衡策stractLoadBalance 抽象类的内容,还详细介绍了 ConsistentHashLoadBalance 以及 RandomLoadBalance 这两个实现类的核心原理和大致实现。
  • Dubbo源码解读与实战-47配置中心设计与实现:集中化配置and本地化配置,我都要(上) 47 配置中心设计与实现:集中化配置 and 本地化*,在服务自省架构中也依赖配置中心完成 Service ID 与 Service Name 的映射。配置中心在 Dubbo 中主要承担两个职责: 外部化配置; 服务治理,负责服务治
  • Dubbo源码解读与实战-02Dubbo的配置总线:抓住URL,就理解了半个Dubbo 02 Dubbo 的配置总线:抓住 URL,就理解置总线:抓住 URL,就理解了半个 Dubbo 。 在互联网领域,每个信息资源都有统一的且在网上唯一的地址,该地址就叫 URL(Uniform Resource Locator,统一资
  • Dubbo源码解读与实战-08代理模式与常见实现 08 代理模式与常见实现te 等常用的开源框架,都使用到了动态代理机制。当然,Dubbo 中也使用到了动态代理,在后面开发简易版 RPC 框架的时候,我们还会参考 Dubbo 使用动态代理机制来屏蔽底层的网络传输以及服务发现的相关实现。
  • Dubbo源码解读与实战-48配置中心设计与实现:集中化配置and本地化配置,我都要(下) 48 配置中心设计与实现:集中化配置 and 本地化接口以及 DynamicConfiguration 接口的实现,**其中 DynamicConfiguration 接口实现是动态配置中心的基础**。那 Dubbo 中的动态配置中心是
  • Dubbo源码解读与实战-30Filter接口,扩展Dubbo框架的常用手段指北 30 Filter 接口,扩展 DubborWrapper 的具体实现,这里简单回顾一下。在 buildInvokerChain() 方法中,ProtocolFilterWrapper 会加载 Dubbo 以及应用程序提供的 Filte
  • Dubbo源码解读与实战-31加餐:深潜Directory实现,探秘服务目录玄机 31 加餐:深潜 Directory 实现主题是:深潜 Directory 实现,探秘服务目录玄机。 在生产环境中,为了保证服务的可靠性、吞吐量以及容错能力,我们通常会在多个服务器上运行相同的服务端程序,然后以**集群**的形式对外提
  • Dubbo源码解读与实战-10Netty入门,用它做网络编程都说好(下) 10 Netty 入门,用它做网 的设计。在本课时,我们就深入到 Netty 内部,介绍一下 Netty 框架核心组件的功能,并概述它们的实现原理,进一步帮助你了解 Netty 的内核。 这里我们依旧采用之前的思路来介绍 Netty
  • 近期文章

    更多
    文章目录

      推荐作者

      更多