HashMap源码剖析

2021年9月25日 11点热度 0条评论 来源: linzeliang

1. HashMap继承结构

2. HashMap底层数据结构

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

来看下1.7的储存结构图:

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

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

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

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

在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;
}

3. HashMap的属性

// 默认的初始容量,左移位4位相当于:1*2*2*2*2=16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大的容量:2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认装载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当一个元素被添加到至少有8个节点的桶中,桶中的链表将会被转化成红黑树,即转化成红黑树条件是大于8个
static final int TREEIFY_THRESHOLD = 8;
// 红黑树退化成链表的条件:小于等于6时退化
static final int UNTREEIFY_THRESHOLD = 6;
// 转化成红黑树的最小的桶的数量
static final int MIN_TREEIFY_CAPACITY = 64;

成员属性有如下:

4. 构造方法

一共有4个构造方法:

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

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;
}

5. 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,如果大于那么就扩容

6. 扩容

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({"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)
                    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. 最后就是将旧的数据复制到新数组里面,有两种情况:

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

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

7. 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

8. 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来删除元素的

9. HashMap的一些特性

  • 允许key和value为null
  • 除了允许为努力了和同步,其他的和HashTable一样
  • 不保证有序
  • 初始容量太高或者太低对便利都不太好
  • 当哈希表容量超过初始容量*装载因子时,哈希表会进行再散裂,桶数量*2
  • 不同步,想要同步可以使用Collections工具类实现Map m = Collections.synchronizedMap(new HashMap(...));
  • 装载因子默认是0.75,设置高虽然会减少空间,但是遍历的开销会增加。因此在设置初始容量时,应该考虑好装载因子和容量的大小,如果设置的好,就不用再散裂了
    原文作者:linzeliang
    原文地址: https://www.cnblogs.com/linzeliang1222/p/15332926.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。