首页 > 资讯 > 后端开发 > Python >Java源码解析之HashMap的put、resize方法详解

143

分享到

Java源码解析之HashMap的put、resize方法详解

2024-04-02 19:04:59 143人浏览独家记忆

Python 官方文档：入门教程 => 点击学习

摘要

目录一、HashMap 简介二、源码分析2.1 继承和实现2.2 属性2.3 节点类型node内部类2.4 红黑树的节点三、构造方法3.1 构造器13.2 构造器23.3 构造器33

一、HashMap 简介

HashMap 底层采用哈希表结构数组加链表加红黑树实现，允许储存null键和null值

数组优点：通过数组下标可以快速实现对数组元素的访问，效率高

链表优点：插入或删除数据不需要移动元素，只需要修改节点引用效率高

二、源码分析

2.1 继承和实现


public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;

继承AbstractMap<K,V>

实现了map接口 cloneable接口和可序列化接口

2.2 属性


//hashmap默认容量为 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap默认容量 16
//最大容量为2的30   1073741824
static final int MAXIMUM_CAPACITY = 1 << 30;  //
//默认加载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//链表转为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//红黑树转为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//链表转为红黑树时数组容量必须大于64
static final int MIN_TREEIFY_CAPACITY = 64;
//
transient Node<K,V>[] table;

transient Set<Map.Entry<K,V>> entrySet;

transient int size;
//用于快速失败机制 在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），直接抛出ConcurrentModificationException异常
transient int modCount;
//扩容阈值，计算方法为数组容量*填充因子
int threshold;
//加载因子 填充因子
final float loadFactor;

loadFactor决定数组何时进行扩容，而且为什么是0.75f

它也叫扩容因子比如数组长度为32，所以数组扩容阈值为32*0.75=24当数组中数据个数为24时数组进行扩容，

数组容量在创建的时候就确定，扩容时重新创建一个指定容量的数组，然后讲旧数组的值复制到新数组中，扩容过程非常耗时，所以0.75时基于容量和性能之间平衡的结果。

如果加载因子过大，也就是扩容阈值会变大，扩容门槛高，这样容量的占用率就会降低，但哈希碰撞的几率就会增加，效率下降
如果加载因子过小，扩容阈值变小，扩容门槛低，容量占用变大但哈希碰撞几率下降

此外用于存储数据的table字段使用transient修饰，通过transient修饰的字段在序列化的时候将被排除在外，那么HashMap在序列化后进行反序列化时，是如何恢复数据的呢？HashMap通过自定义的readObject/writeObject方法自定义序列化和反序列化操作。这样做主要是出于以下两点考虑：

1.table一般不会存满，即容量大于实际键值对个数，序列化table未使用的部分不仅浪费时间也浪费空间；

2.key对应的类型如果没有重写hashCode方法，那么它将调用Object的hashCode方法，该方法为native方法，在不同JVM下实现可能不同；换句话说，同一个键值对在不同的JVM环境下，在table中存储的位置可能不同，那么在反序列化table操作时可能会出错。

所以在HashXXX类中（如HashTable，HashSet，LinkedHashMap等等），我们可以看到，这些类用于存储数据的字段都用transient修饰，并且都自定义了readObject/writeObject方法。readObject/writeObject方法

2.3 节点类型Node内部类


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

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K geTKEy()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

Node包含四个字段


final int hash;
    final K key;
    V value;
    Node<K,V> next;//包含链表下一个节点

HashMap通过hash方法计算key的哈希值，然后通过（n-1）&hash得到key在数组中存放的下标，当两个key相同时，会以链地址法处理哈希碰撞

在链表中查找数据必须从第一个元素开始，时间复杂度为O n 所以当链表长度越来越长时HashMap的查询效率就会越来越低

所以为了解决这个问题JDK1.8实现了数组+链表+红黑树来解决当链表长度超过8个时并且数组长度大于64时进行树化，转化后查询时间复杂度为O(logN).

2.4 红黑树的节点


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;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

包含左右孩子节点和双亲结点，和前驱节点，还有节点是否时红或者黑

三、构造方法

3.1 构造器1


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

最常用的构造器。默认的填充因子 0.75f 这里的填充因子后面会讲到。

3.2 构造器2


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

给定容量构造器

3.3 构造器3


public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)// 如果小于0，抛出异常
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)//大于最大值
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))//若填充因子小于0或者判断非法
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

  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;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

给定容量和填充因子。

这里的tableSizeFor会将传进的容量值进行**大于等于最近**二次幂处理。跟循环数组的处理方式差不多

3.4 构造器4


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

四、put


public V put(K key, V value) {
    //底层是调用putval
    return putVal(hash(key), key, value, false, true);
}

  //这里调用了hashmap提供的hash方法，32为都参与了运算所以降低了hash碰撞的几率，这里还跟数组容量有关
//下面再讨论
  static final int hash(Object key) {
        int h;
      //这里就可以看到hashmap
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

通过hash函数可以看到当key为null时，key为0，所以HashMap 是允许储存空值的。而后面的公式通过hashcode的高16位异或低1位得到的hash值，主要从性能、哈希碰撞角度考虑，减少系统开销，不会因为高位没有参与下标计算而引起的碰撞


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //请注意这里的hash是已经算过的hash(key)，然后计算数组下标位置(n - 1) & hash
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //首先判断数组哈希表是否为null或者长度为0，是则进行数组初始化操作
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //这里tab指向table数组  n是数组长度
    //如果该数组下标位置没有数据直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {//该位置有元素     
        Node<K,V> e; K k;
        //首先判断此位置的值的hash和key的地址和值是否相等
        //如果相等直接覆盖
        //小问题这里为什么先判断hash值而不是判断key值，因为hash值判断最快，如果hash值不同就不用判断下面的
        //hash不同则key一定不同，但key相同hash值是可能相同的，效率提高
        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);
                    //如果链表长度大于等于转为红黑树阈值8，则转为红黑树
                    //这里为什么要-1，因为数组下标从0开始
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      //转为红黑树操作时，内部还会判断数组长度是否小于MIN_TREEIFY_CAPACITY 64，如果是的话不转换
                        treeifyBin(tab, hash);
                    break;//退出
                }
                //如果链表中已经存在该key，直接覆盖
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                //遍历数组 e = p.next
                p = e;
            }
        }
        //e代表被覆盖的值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
           // 如果onlyIfAbsent为false并且oldValue为null,我们便对我们的value进行保存
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //如果键值对个数大于扩容阈值，进行扩容操作
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

流程图

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HHFhKMDq-1618929232359)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20210420203344879.png)]$

五、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;
    //如果桶为空，size为0，目标位置是否为空，是直接返回null
    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;
        //否则如果头节点的next有值
        if ((e = first.next) != null) {
            //如果该类型为红黑树，从红黑树中找
            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;
}

六、resize

数组的扩容和初始化都要靠resize完成


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;
        }
        //2倍扩容不能大于最大值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            //扩容阈值/2
            newThr = oldThr << 1; // double threshold
    }
    //数组中没有值，带参初始化会进入这里
    //且扩容因子大于0
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //不带参默认会到这里
    else {//否则扩充因子 <= 0
        //就是没初始化过，使用默认的初始化容量，16 * 0.75
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新容量为0，重新计算threshold扩容阈值
    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;
                    }
                    //高位引用 直接讲原索引+oldCap放到哈希桶中
                    //因为是2倍扩容，	扩容后位置是原位置+增长的长度
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

七、基于JDK1.7的优化

7.1 底层实现

1.7基于数组+链表而1.8基于链表+数组+红黑树

7.2 hash


final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

效率基于1.8低