HashMap常见面试题(超全面):实现原理、扩容机制、链表何时升级为红黑树、死循环

简介: HashMap常见面试题:红黑树、散列表,HashMap实现原理、扩容机制,HashMap的jd1.7与jdk1.8有什么区别,寻址算法、链表何时升级为红黑树、死循环

文章目录

一、红黑树、散列表

  • 1.1 红黑树
  • 1.2 散列表

二、HashMap源码分析(底层实现)

  • 2.1 HashMap成员变量

  • 2.2 HashMap构造函数

  • 2.3 HashMap关键方法

    • 2.3.1 put方法
    • 2.3.2 get方法,查找
    • 2.3.3 remove方法,删除

三、说一下HashMap的实现原理

四、HashMap的jdk1.7和jdk1.8有什么区别

五、HashMap的put方法的具体流程

六、讲一讲HashMap的扩容机制

  • 6.1 扩容机制

  • 6.2 为什么扩容

  • 6.3 什么时候扩容

  • 6.4 如何扩容/源码分析

  • 6.5 补充:JDK1.7与1.8扩容的区别

    • JDK1.7扩容
    • JDK1.8扩容

七、hashMap的寻址算法

八、链表升级成红黑树的条件

九、红黑树退化成链表的条件

十、HashMap是怎么解决哈希冲突的

十一、为什么我们需要hash()函数 (n-1)\&hash,而不是直接用key的hashcode直接计算下标

十二、为何HashMap的数组长度一定是 2^n 次幂?

十三、hashmap在1.7情况下的多线程死循环问题

十四、为什么经常使用String作为HashMap的Key

十五、HashMap与Hashtable的区别

十六、HashMap的key和value可以为null

  • 16.1 结论
  • 16.2 Hashtable的key为什么不能为null
  • 16.3 HashMap的key为什么可以null
  • 16.4 ConcurrentHashMap的key和value都不能为null
  • 16.5 总结

0-1.png

该面试题主要参考 黑马程序员相关视频和笔记,同时结合自己实际面试过程中遇到的问题,加以补充。

在HashMap中的最重要的一个数据结构就是散列表,在散列表中又使用到了红黑树链表

一、红黑树、散列表

1.1 红黑树

  • 红黑树:一颗自平衡的二叉搜索树(BST),所有的红黑规则都是希望红黑树能够保证平衡。红黑规则如下:

    • 每一个节点或是红色的,或者是黑色的
    • 根节点必须是黑色
    • 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为Nil,这些Nil视为叶节点,每个叶节点(Nil)是黑色的空节点
    • 如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)
    • 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
  • 查找、添加、删除的时间复杂度都是O(n)。

1-1.png

1.2 散列表

(散列表的概念、散列函数、散列冲突、拉链法)

1)散列表(Hash Table):又名哈希表/Hash表,是根据键(Key)直接访问在内存存储位置值(Value)的数据结构,它是由数组演化而来的,利用了数组支持按照下标进行随机访问数据的特性。

假设有100个人参加马拉松,不采用1-100的自然数对选手进行编号,编号有一定的规则比如:2023ZHBJ001,其中2023代表年份,ZH代表中国,BJ代表北京,001代表原来的编号,那此时的编号2023ZHBJ001不能直接作为数组的下标,此时应该如何实现呢?

1-2.png

2)散列冲突:也叫哈希冲突、哈希碰撞,指多个key映射到同一个数组下标位置

3)散列冲突-链表法(拉链):在散列表中,数组的每个下标位置我们可以称之为桶(bucket)或者槽(slot),每个桶(槽)会对应一条链表,所有散列值相同的元素我们都放到相同槽位对应的链表中。时间复杂度如下

  • 插入操作:O(1)。通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可
  • 查找、删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查找或者删除
    • 平均情况下基于链表法解决冲突时查询的时间复杂度是O(1)
    • 散列表可能会退化为链表,查询的时间复杂度就从 O(1) 退化为 O(n)
    • 将链表法中的链表改造为其他高效的动态数据结构,比如红黑树,查询的时间复杂度是 O(logn)

1-3.png

二、HashMap源码分析(底层实现)

我们分析源码 主要从以下几个方面来考虑:成员变量、构造函数、关键方法

2.1 HashMap成员变量

//默认的初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大数量,该数组最大值为2^30。
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的加载因子。如果构造的时候不传则为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//一个位置里存放的节点转化成树的阈值,也就是8,比如数组里有一个node,这个node链表的长度达到该值才会转化为红黑树。
static final int TREEIFY_THRESHOLD = 8;
//当一个反树化的阈值,当这个node长度减少到该值就会从树转化成链表
static final int UNTREEIFY_THRESHOLD = 6;
//满足节点变成树的另一个条件,就是存放node的数组长度要达到64
static final int MIN_TREEIFY_CAPACITY = 64;
//具体存放数据的数组!!!
transient Node<K,V>[] table;  //见下
//entrySet,一个存放k-v缓冲区
transient Set<Map.Entry<K,V>> entrySet;
//size是指hashMap中存放了多少个键值对
transient int size;
//对map的修改次数
transient int modCount;
//The next size value at which to resize (capacity * load factor).
int threshold;
//加载因子
final float loadFactor;
//链表中的键值对对象
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;
    }
}
//红黑树中的键值对对象
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);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
   
        for (TreeNode<K,V> r = this, p;;) {
   
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

    //...
}

注意HashMap中的 transient Node<K,V>[] table,该table是真正存放数据的容器,该容器由一个又一个node组成,而node有三种实现,所以hashMap中存放的node的形式既可以是Node也可以是TreeNode。可见HashMap是基于数组、链表或者树实现的。

2-1.png

【HashMap 的定义是一个散列表,这是一种支持快速查找元素的数据结构,那么其背后就必然会使用到数组随机访问的特点。因此,HashMap 的一维结构就是一个数组,数组元素是一个包含 Key、Value 和 hashcode 的 Entry 节点。当我们需要访问集合元素时,其实就是先通过 key 计算 hashcode,再将 hashCode 对数组长度取余得到数组下标,最后通过下标去数组中找到对应的 Value】

DEFAULT_INITIAL_CAPACITY 默认的初始容量

DEFAULT_LOAD_FACTOR 默认的加载因子

扩容阈值 == 数组容量 * 加载因子

2.2 HashMap构造函数

public HashMap(int initialCapacity, float loadFactor) {
   
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //当容量大于2^31就取最大值1<<31;
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //当前数组table的大小,一定是2的幂次方
    // tableSizeFor保证了数组一定是2的幂次方,是大于initialCapacity最接近的值。
    this.threshold = tableSizeFor(initialCapacity);
}

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

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

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

HashMap是懒惰加载,在创建对象时并没有初始化数组;在无参的构造函数中,设置了默认的加载因子是0.75。

构造方法一共重载了四个,主要初始化了三个参数:

  • initialCapacity 初始容量(默认16): hashMap底层由数组实现+链表(或红黑树)实现,但是还是从数组开始,所以当储存的数据越来越多的时候,就必须进行扩容操作,如果在知道需要储存数据大小的情况下,指定合适的初始容量,可以避免不必要的扩容操作,提升效率

  • threshold 阈值:hashMap所能容纳的最大价值对数量,如果超过则需要扩容,计算方式:threshold=initialCapacity*loadFactor(构造方法中直接通过tableSizeFor(initialCapacity)方法进行了赋值,主要原因是在构造方法中,数组table并没有初始化,put方法中进行初始化,同时put方法中也会对threshold进行重新赋值,这个会在后面的源码中进行分析)

  • loadFactor 加载因子(默认0.75):当负载因子较大时,去给table数组扩容的可能性就会少,所以相对占用内存较少(空间上较少),但是每条entry链上的元素会相对较多,查询的时间也会增长(时间上较多)。反之就是,负载因子较少的时候,给table数组扩容的可能性就高,那么内存空间占用就多,但是entry链上的元素就会相对较少,查出的时间也会减少。所以才有了负载因子是时间和空间上的一种折中的说法。所以设置负载因子的时候要考虑自己追求的是时间还是空间上的少。(一般情况下不需要设置,系统给的默认值已经比较适合了)

我们最常使用的是无参构造,在这个构造方法里面仅仅设置了加载因子为默认值,其他两个参数会在resize方法里面进行初始化,在这里知道这个结论就可以了,下面会在源码里面进行分析; 另外一个带有两个参数的构造方法,里面对初始容量和阈值进行了初始化,对阈值的初始化方法为 tableSizeFor(int cap),看一下源码:

//找到大于或等于 cap 的最小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;
}

tableSizeFor()方法保证了数组大小一定是2的幂次方,是如何实现的呢? —— 该方法将一个二进制数第一位1后边的数字全部变成1,然后再加1,这样这个二进制数就一定是100…这样的形式。此处实现在ArrayDeque的实现中也用到了类似的方法来保证数组长度一定是2的幂次方。

对于无符号右移运算符不了解的,可以看一下这篇文章了解一下,下面偷一张图 以10为例进行分析:

2-2.png

另外,需要注意一下的是,第一步 int n = cap - 1; 这个操作,执行这个操作的主要原因是为了防止在cap已经是2的n次幂的情况下,经过运算后得到的结果是cap的二倍的结果,例如如果n为l6,经过一系列运算之后,得到的结果是0001 1111,此时最后一步n+1 执行之后,就会返回32,有兴趣的可以自己进行尝试

2.3 HashMap关键方法

2.3.1 put方法

在hashMap源码中,put方法逻辑是最为复杂的,接下来先看一下源码:

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) {
   
    //tab 局部变量,用来记录哈希表中数组的地址值(成员变量table放在堆中,方法放在栈中,如果一直调用table 需要反复去堆中获取,故定义tab)
    //p 临时的第三方变量,用来记录键值对对象的地址值;n 表示当前数组的长度;i 表示索引
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        //resize()方法逻辑:
        //1.如果当前是第一次添加数据,底层会创建一个默认长度为16、加载因子为0.75的数组
        //2.如果不是第一次添加数据,会看数组中的元素是否达到了扩容的条件:如果没有达到扩容条件,底层不会做任何操作;如果达到了扩容条件,底层会把数组扩容为原先的两倍,并把数据全部转移到新的哈希表中
        n = (tab = resize()).length;
    // i = (n - 1) & hash  拿着数组长度与键的哈希值进行计算,得出当前键值对对象 在数组中应存入的位置
    if ((p = tab[i = (n - 1) & hash]) == null)
        //通过hash找到下标,如果hash值指定的位置数据为空,则创建一个键值对对象,直接放到数组中
        tab[i] = newNode(hash, key, value, null);
    else {
   
        //如果通过hash找到的位置有数据,发生碰撞
        Node<K,V> e; K k;
        //p.hash == hash 判断键是否一样
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            //如果需要插入的key和当前hash值指定下标的key一样,先将p赋值给e
            e = p;
        else if (p instanceof TreeNode)
            //如果此时桶中数据类型为 treeNode,使用红黑树进行插入,调用putTreeVal方法
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
   
            //如果此时桶中数据类型为链表,遍历
            // 进行循环。注意e = p.next这个一直将下一节点赋值给e,直到尾部,注意开头是++binCount
            for (int binCount = 0; ; ++binCount) {
   
                if ((e = p.next) == null) {
   
                    //如果链表中没有最新插入的节点,将新放入的数据放到链表的末尾
                    p.next = newNode(hash, key, value, null);
                    //判断当前链表长度是否超过8.如果超过8 就会调用treeifyBin方法
                    //treeifyBin方法的底层还会继续判断 数组的长度是否大于等于64,如果同时满足这两个条件 就会把这个链表转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //如果哈希值一样,就会调用equals方法比较内部的属性值是否相同。若都相同 跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //如果e为null 表示当前不需要覆盖任何元素
        //如果e不为null,表明当前的键是一样的,值会被覆盖
        if (e != null) {
    // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //如果此时hashMap size大于阈值,则进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);  //与LinkedHashMap有关
    //表示当前没有覆盖任何元素,返回null
    return null;
}

源码详解

1.看源码之前需要了解的一些内容

Node<K,V>[] table   哈希表结构中数组的名字

DEFAULT_INITIAL_CAPACITY:   数组默认长度16

DEFAULT_LOAD_FACTOR:        默认加载因子0.75



HashMap里面每一个对象包含以下内容:
1.1 链表中的键值对对象
    包含:  
            int hash;         //键的哈希值
            final K key;      //键
            V value;          //值
            Node<K,V> next;   //下一个节点的地址值


1.2 红黑树中的键值对对象
    包含:
            int hash;                 //键的哈希值
            final K key;              //键
            V value;                  //值
            TreeNode<K,V> parent;      //父节点的地址值
            TreeNode<K,V> left;        //左子节点的地址值
            TreeNode<K,V> right;    //右子节点的地址值
            boolean red;            //节点的颜色



2.添加元素
HashMap<String,Integer> hm = new HashMap<>();
hm.put("aaa" , 111);
hm.put("bbb" , 222);
hm.put("ccc" , 333);
hm.put("ddd" , 444);
hm.put("eee" , 555);

添加元素的时候至少考虑三种情况:
2.1 数组位置为null,底层会创建一个键值对对象,直接放到数组当中
2.2 数组位置不为null,键不重复,挂在下面形成链表或者红黑树
2.3 数组位置不为null,键重复,元素覆盖


//参数一:键
//参数二:值

//返回值:被覆盖元素的值,如果没有覆盖,返回null
public V put(K key, V value) {
   
    return putVal(hash(key), key, value, false, true);
}


//利用键计算出对应的哈希值,再把哈希值进行一些额外的处理
//简单理解:返回值就是返回键的哈希值
static final int hash(Object key) {
   
    int h;
    // key.hashCode():返回散列值也就是hashcode
    // ^ :按位异或
    // >>>:⽆符号右移,忽略符号位,空位都以0补⻬
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//参数一:键的哈希值
//参数二:键
//参数三:值
//参数四:如果键重复了是否保留
//           true,表示老元素的值保留,不会覆盖
//           false,表示老元素的值不保留,会进行覆盖
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
   
    //定义一个局部变量,用来记录哈希表中数组的地址值。
    Node<K,V>[] tab;

    //临时的第三方变量,用来记录键值对对象的地址值
    Node<K,V> p;

    //表示当前数组的长度
    int n;

    //表示索引
    int i;

    //把哈希表中数组的地址值,赋值给局部变量tab
    tab = table;

    if (tab == null || (n = tab.length) == 0){
   
        //1.如果当前是第一次添加数据,底层会创建一个默认长度为16,加载因子为0.75的数组
        //2.如果不是第一次添加数据,会看数组中的元素是否达到了扩容的条件
        //如果没有达到扩容条件,底层不会做任何操作
        //如果达到了扩容条件,底层会把数组扩容为原先的两倍,并把数据全部转移到新的哈希表中
        tab = resize();
        //表示把当前数组的长度赋值给n
        n = tab.length;
    }

    //拿着数组的长度跟键的哈希值进行计算,计算出当前键值对对象,在数组中应存入的位置
    i = (n - 1) & hash;//index
    //获取数组中对应元素的数据
    p = tab[i];


    if (p == null){
   
        //底层会创建一个键值对对象,直接放到数组当中
        tab[i] = newNode(hash, key, value, null);
    }else {
   
        Node<K,V> e;
        K k;

        //等号的左边:数组中键值对的哈希值
        //等号的右边:当前要添加键值对的哈希值
        //如果键不一样,此时返回false
        //如果键一样,返回true
        boolean b1 = p.hash == hash;

        if (b1 && ((k = p.key) == key || (key != null && key.equals(k)))){
   
            e = p;
        } else if (p instanceof TreeNode){
   
            //判断数组中获取出来的键值对是不是红黑树中的节点
            //如果是,则调用方法putTreeVal,把当前的节点按照红黑树的规则添加到树当中。
            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,如果超过8,就会调用方法treeifyBin
                    //treeifyBin方法的底层还会继续判断
                    //判断数组的长度是否大于等于64
                    //如果同时满足这两个条件,就会把这个链表转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                //e:              0x0044  ddd  444
                //要添加的元素: 0x0055   ddd   555
                //如果哈希值一样,就会调用equals方法比较内部的属性值是否相同
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))){
   
                     break;
                }

                p = e;
            }
        }

        //如果e为null,表示当前不需要覆盖任何元素
        //如果e不为null,表示当前的键是一样的,值会被覆盖
        //e:0x0044  ddd  555
        //要添加的元素: 0x0055   ddd   555
        if (e != null) {
   
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null){
   

                //等号的右边:当前要添加的值
                //等号的左边:0x0044的值
                e.value = value;
            }
            afterNodeAccess(e);
            return oldValue;
        }
    }

    //threshold:记录的就是数组的长度 * 0.75,哈希表的扩容时机  16 * 0.75 = 12
    if (++size > threshold){
   
         resize();
    }

    //表示当前没有覆盖任何元素,返回null
    return null;
}

从代码来看,put方法分为三种情况

  • table尚未初始化,对数据进行初始化

  • table已经初始化,且通过hash算法找到下标所在的位置数据为空,直接将数据存放到指定位置

  • table已经初始化,且通过hash算法找到下标所在的位置数据不为空,发生hash冲突(碰撞),发生碰撞后,会执行以下操作:

    • 判断插入的key如果等于当前位置的key的话,将 e 指向该键值对
    • 如果此时桶中数据类型为 treeNode,使用红黑树进行插入
    • 如果是链表,则进行循环判断, 如果链表中包含该节点,跳出循环,如果链表中不包含该节点,则把该节点插入到链表末尾,同时,如果链表长度超过树化阈值(TREEIFY_THRESHOLD)且table容量超过最小树化容量(MIN_TREEIFY_CAPACITY),则进行链表转红黑树(由于table容量越小,越容易发生hash冲突,因此在table容量\TREEIFY_THRESHOLD,会优先选择扩容,否则会进行链表转红黑树操作)

添加元素的时候至少考虑三种情况:

  • 数组位置为null,底层会创建一个键值对对象,直接放到数组当中
  • 数组位置不为null,键不重复,挂在下面形成链表或者红黑树
  • 数组位置不为null,键重复,元素覆盖(同一个key,值不同)

首先分析table尚未初始化的情况:

n = (tab = resize()).length;  //table尚未初始化的时候,会调用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;

    //1.table已经初始化,且容量 > 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
    }
    //2.阈值大于0 threshold 使用 threshold 变量暂时保存 initialCapacity 参数的值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //3.threshold 和 table 皆未初始化情况,此处即为首次进行初始化
    //也就在此处解释了构造方法中没有对threshold 和 初始容量进行赋值的问题
    else {
                  // zero initial threshold signifies using defaults
        //如果阈值为零,表示使用默认的初始化值。这种情况在调用无参构造的时候会出现,此时使用默认的容量和阈值
        newCap = DEFAULT_INITIAL_CAPACITY;
        //此处阈值即为 threshold=initialCapacity*loadFactor
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // newThr 为 0 时,按阈值计算公式进行计算,容量*负载因子
    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;

    //如果之前的数组桶里面已经存在数据,由于table容量发生变化,hash值也会发生变化,需要重新计算下标
    if (oldTab != null) {
   
        for (int j = 0; j < oldCap; ++j) {
   
            Node<K,V> e;
            //如果指定下标下有数据
            if ((e = oldTab[j]) != null) {
   
                //1)将指定下标数据置空
                oldTab[j] = null;
                //2)指定下标只有一个数据
                if (e.next == null)
                    //直接将数据存放到新计算的hash值下标下
                    newTab[e.hash & (newCap - 1)] = e;
                //3)如果是TreeNode数据结构
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //4)对于链表,数据结构
                else {
    // preserve order
                    //如果是链表,重新计算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;
                        }
                        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;
}

resize方法逻辑比较复杂,需要静下心来一步步的分析,但是总的下来,分为以下几步:

  • 首先先判断当前table是否进行过初始化,如果没有进行过初始化,此处就解决了调用无参构造方法时候,threshold和initialCapacity 未初始化的问题,如果已经初始化过了,则进行扩容,容量为原来的二倍
  • 扩容后创建新的table,并对所有的数据进行遍历
    • 如果新计算的位置数据为空,则直接插入
    • 如果新计算的位置为链表,则通过hash算法重新计算下标,对链表进行分组
    • 如果是红黑树,则需要进行拆分操作

2.3.2 get方法,查找

put方法分析完成之后,剩下的就很简单了,先看一下源码:

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) {
   
        //1)根据hash算法找到对应位置的第一个数据,如果是指定的key,则直接返回。
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
   
            //如果该节点为红黑树,则通过树进行查找
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果该节点是链表,则遍历查找到数据。当链表后续为null 退出循环
            do {
   
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get方法相对于put来说,逻辑简单很多:

  1. 根据hash值查找到指定位置的数据
  2. 校验指定位置第一个节点的数据是key是否为传入的key,如果是直接返回第一个节点,否则继续查找第二个节点
  3. 如果数据是TreeNode(红黑树结构),直接通过红黑树查找节点数据并返回
  4. 如果是链表结构,循环查找所有节点,返回数据
  5. 如果没有找到符合要求的节点,返回null

在这个方法里面,需要注意的有两个地方:hash(key)和hash的取模运算 (n - 1) & hash。

  • (n - 1) & hash 判断当前元素存放的位置(这⾥的 n 指的是数组的⻓度)

hash(key)源码

static final int hash(Object key) {
   
    int h;
    // key.hashCode():返回散列值也就是hashcode
    // ^ :按位异或
    // >>>:⽆符号右移,忽略符号位,空位都以0补⻬
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

这段代码叫做扰动函数,也是hashMap中的hash运算,主要分为下面几步:

  • key.hashCode(),获取key的hashCode值,如果不进行重写的话返回的是根据内存地址得到的一个int值
  • key.hashCode() 获取到的hashcode无符号右移16位并和原hashCode进行^ ,这样做的目的是为了让高位与低进行混合,让两者都参与运算,以便让hash值分布更加均匀

取模运算 (n - 1) & hash

在hashMap的代码中,在很多地方都会看到类似的代码:

first = tab[(n - 1) & hash])

hash算法中,为了使元素分布的更加均匀,很多都会使用取模运算,在hashMap中并没有使用hash%n这样进行取模运算,而是使用(n - 1) & hash进行代替,原因是在计算机中,&的效率要远高于%;需要注意的是,只有容量为2的n次幂的时候,(n - 1) & hash 才能等效hash%n,这也是hashMap 初始化初始容量时,无论传入任何值,都会通过tableSizeFor(int cap) 方法转化成2的n次幂的原因,这种巧妙的设计真的很令人惊叹; 至于为什么只有2的n次幂才能这样进行取模运算,这里就不再详细叙述了,有兴趣的可以看一下一位大佬写的文章:由HashMap哈希算法引出的求余%和与运算&转换问题

2.3.3 remove方法,删除

了解完get方法之后,我们再最后了解一下remove方法:

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

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
   
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    //根据key和key的hash值,查找到对应的元素
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
   
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
   
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
   
                do {
   
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
   
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }

        //如果查找到了元素node,移除即可
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
   
            //如果是TreeNode,通过树进行移除
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            //如果是第一个节点,移除第一个节点,将index下标的位置指向第二个节点
            else if (node == p)
                tab[index] = node.next;
            else
                //如果不是链表的第一个节点,则移除该节点
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

从源码可以看出来,通过key找到需要移除的元素操作过程和get方法几乎一致,最后在查找到key对应的节点之后,根据节点的位置和类型,进行相应的移除操作就完成了,过程非常简单。

三、说一下HashMap的实现原理

HashMap的数据结构: 底层使用hash表数据结构,即数组和链表或红黑树。jdk1.7使用的是 数组+链表,jdk1.8 当链表长度大于阈值(默认为8)并且数组长度达到64时 会转换为红黑树

初始容量:HashMap 的初始容量是 0,这是一种懒加载机制,直到第一次 put 操作才会初始化数组大小,默认大小是 16。

扩容逻辑

HashMap 使用的是拉链法来解决散列冲突,扩容并不是必须的,但是不扩容的话会造成拉链的长度越来越长,导致散列表的时间复杂度会倾向于 O(n) 而不是 O(1)。

HashMap 扩容的触发时机出现在元素个数超过阈值(容量 * loadFactor)的时候时,会将集合的一维数组扩大一倍,然后重新计算每个元素的位置。

  • 当我们往HashMap中put元素时,利用key的hashCode重新hash计算出当前对象的元素在数组中的下标
  • 存储时,如果出现hash值相同的key,此时有两种情况。
    • 如果key相同,则覆盖原始值;
    • 如果key不同(出现冲突),则将当前的key-value放入链表或红黑树中
  • 获取时,直接找到hash值对应的下标,在进一步判断key是否相同,从而找到对应值。

3-1.png

注意:链表的长度大于8 且 数组长度大于64转换为红黑树(如果数组长度小于64,即使链表长度超过 8,也不会进行树华,而是会进行扩容操作)

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都⽤到了红⿊树。红⿊树就是为了解决⼆叉查找树的缺陷,因为⼆叉查找树在某些情况下会退化成⼀个线性结构。

面试官追问:HashMap的jdk1.7和jdk1.8有什么区别

四、HashMap的jdk1.7和jdk1.8有什么区别

  • JDK1.8之前采用的是拉链法。拉链法:将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。
  • jdk1.8在解决哈希冲突时有了较大的变化,当链表长度大于阈值(默认为8) 时并且数组长度达到64时,将链表转化为红黑树,以减少搜索时间。扩容 resize( ) 时,红黑树拆分成的树的结点数小于等于临界值6个,则退化成链表

4-1.png

五、HashMap的put方法的具体流程

5-1.png

  1. 判断键值对数组table是否为空或为null,否则执行resize()进行扩容(初始化)

  2. 根据键值key计算hash值得到数组索引

  3. 判断table[i]==null,条件成立,直接新建节点添加

  4. 如果table[i]==null ,不成立

    • 判断table[i]的首个元素是否和key一样,如果相同直接覆盖value
    • 判断table[i] 是否为treeNode,即table[i] 是否是红黑树,如果是红黑树,则直接在树中插入键值对
    • 遍历table[i],链表的尾部插入数据,然后判断链表长度是否大于8,大于8的话把链表转换为红黑树,在红黑树中执行插入操作,遍历过程中若发现key已经存在直接覆盖value
  5. 插入成功后,判断实际存在的键值对数量size是否超多了最大容量threshold(数组长度*0.75),如果超过,进行扩容。

六、讲一讲HashMap的扩容机制

6.1 扩容机制

6-1.png

  • 在添加元素或初始化的时候需要调用resize方法进行扩容,第一次添加数据初始化数组长度为16,以后每次扩容都是元素数量达到了扩容阈值(数组长度 * 0.75)
  • 每次扩容的时候,都是扩容之前容量的2倍;
  • 扩容之后,会新创建一个数组,需要把老数组中的数据挪动到新的数组中
    • 没有hash冲突的节点,则直接使用 e.hash & (newCap - 1) 计算新数组的索引位置
    • 如果是红黑树,走红黑树的添加
    • 如果是链表,则需要遍历链表,可能需要拆分链表,判断(e.hash & oldCap)是否为0,该元素的位置要么停留在原始位置,要么移动到原始位置+增加的数组大小这个位置上

6-2.png

6.2 为什么扩容

HashMap的扩容,又被很多人叫rehash、重哈希,我本人是很反对这个叫法的,事实上HashMap扩容的时候,Node中存储的Key的hash值并没有发生变化,只是Node的位置发生了变化

HashMap为什么需要扩容?这个问题好像有点简单,不就是因为容量满了就需要库容了吗?这种思想对于链表来说是没有问题的,但是对于HashMap来说,并不是因为这个原因,而是**HashMap认为性能不够好时**。

6.3 什么时候扩容

HashMap在两个时机会发生扩容:1、初始化后放入元素时; 2、元素数量达到阈值时

  • 创建对象以后,HashMap并不是立即初始化table,而是在第一次放入元素时,才会初始化table,这是HashMap节省内存的一种机制,而table的初始化其实是resize方法实现的。
  • 元素数量达到阈值时(数组长度 * 0.75):所谓阈值,就是HashMap中threshold这个属性,阈值计算方式为 capacity(table容量) * loadFactor(负载因子)【个人认为,capacity应该称为理论容量,因为正常情况下达到阈值就扩容了——达到阈值时,HashMap认为哈希冲突的次数会不能接受,因此需要扩容】

6.4 如何扩容/源码分析

1.7版本

  • 首先生成一个新数组

  • 遍历老数组每个位置中的链表元素

  • 取每个元素的key,重新计算每个元素在数组的下标

  • 将元素添加到新数组中

  • 所有元素转移完成之后,将新数组赋值给HashMap里的table属性

1.8版本:先扩容,下一步就是遍历老哈希表、将元素从老的哈希表移到新哈希表中

  • 首先生成一个新数组,新数组大小是旧数组的两倍
  • 遍历老数组每个位置中的链表或者红黑树,重新计算哈希值。在新的桶数组中,键的位置可能会发生变化。新的索引通过对新的数组长度取模来确定
  • 如果Node桶的数据结构是链表,会生成low和high两条链表;是红黑树则生成low和high两颗红黑树
    • 依靠 (hash & oldCap) == 0 判断 Node 中的每个结点归属于 low 还是 high
    • 把 low 插入到 新数组中 当前数组下标的位置,把 high 链表插入到 新数组中 [当前数组下标 + 旧数组长度] 的位置
    • 如果生成的 low,high 树中元素个数小于等于6退化成链表再插入到新数组的相应下标的位置
  • 更新引用:所有的元素转移完成之后,将新数组赋值给HashMap里的table属性。旧数组会被垃圾回收机制回收

以jdk1.8为例,查看HashMap的resize源码为(已加上注解):

final Node<K,V>[] resize() {
   
    //扩容前原本的table
    Node<K,V>[] oldTab = table;
    //这里进行判断,区分尚未初始化的情况
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
      //非初始化情况
        /*
         * 当原本的capacity已经超过最大值以后
         * HashMap选择不再扩容,然后threshold置为最大值
         */
        if (oldCap >= MAXIMUM_CAPACITY) {
   
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        /*
         * 这种是常见的的扩容情况,table容量会扩大两倍
         * 同时HashMap的阈值也跟着扩大两倍
         */
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold,2倍阈值
    }
    else if (oldThr > 0) // 指定大小n的初始化情况下,table容量取>n的最小2倍数。initial capacity was placed in threshold
        newCap = oldThr;
    // 不指定初始化大小,table容量取默认值16
    else {
                  // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
   
        // 指定大小初始化情况下,阈值 = table容量 * 负载因子(默认0.75)
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //确定新阈值。原来默认是12,现在变为24
    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) {
   
            // 遍历原本的table
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
   
                oldTab[j] = null;  //为了GC
                if (e.next == null)
                    // 如果table上没有链表的情况下,直接转移到对应位置
                    // 转移到的位置就是get方法中取的下标位置,tab[(n - 1) & hash]
                    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;
                        //如果entry的哈希值高位为0,会被拆分到lo链表
                        if ((e.hash & oldCap) == 0) {
   
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
   
                             //如果entry的哈希值高位为1,会被拆分到hi链表
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
   
                        loTail.next = null;
                        // 高位是0,因此lo链表不需要移位,
                        // hash & (newCap-1)和hash & (oldCap-1)获得下标位置一样
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
   
                        hiTail.next = null;
                        // 高位是1,hi链表移位到 j+oldCap位置,
                        //  j + oldCap相当于高位补1,直接移到这个位置
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

resize()方法的前半部分主要是对于新阈值和新容量的确定,这里有三种情况:

  • 初始化已完成的正常扩容逻辑:table容量和阈值都扩大2倍
  • 指定大小的初始化逻辑:算出大于等于指定初始化容量的最小2的倍数,作为table容量(譬如指定初始值为3,则table容量为4;指定初始化大小为10,table容量为16;如果指定初始化大小为2的次幂,就直接作为table容量)
  • 未指定大小的初始化逻辑:默认table容量16,阈值为16 * 0.75 = 12

举例说明:假设原本table容量oldCap = 16、有如下个key,其hash值为

key hash值 下标 hash&(length-1)
key1 00000101 00000101 = 5
key2 00010101 00000101 = 5
key3 00100101 00000101 = 5
key4 00110101 00000101 = 5

他们在table中存储的下标位置都是 hash & (table.length-1) = 0101 & 0111 = 0x0101,即都存储在table[5]位置,如下图

6-3.png

当进行扩容时,容量扩大一倍也就是newCap = 32,此时table.length -1 = 31。hash & (table.length - 1) 就会出现两种情况:

  • key1 和 key3 的下标还是5 (0000 0101),原位置
  • key2 和 key4 的下标变为了 21 (0001 0101),原位置+旧容量
key hash值 下标 hash&(length-1)
key1 00000101 00000101 = 5
key2 00010101 00001101 = 21
key3 00100101 00000101 = 5
key4 00110101 00001101 = 21

到这应该能明白,resize方法里的lo列表和hi列表是什么意思了,**其实就是看key高一位的哈希值是1还是0,来决定是放到哪个队列里。**有低位的两个指针 loHead、loTail,高位的两个指针 hiHead、hiTail

6-4.png

扩容到32之后,将两个链表加到对应位置。分别有两种情况,保持原来位置和“原位置+旧容量”这个位置。移位后的HashMap如下图:

6-5.png

所以扩容过程中,对应节点位置变化为:

6-6.png

此处HashMap非常精妙地实现了扩容,没有重新计算对象的哈希值,甚至连下标的重新计算也只需要进行一位相与的计算(hash高位 & newCap-1 )。

即先扩容,下一步就是遍历老哈希表、将元素从老的哈希表移到新哈希表中。移动分两种情况:

  • 情况1:原槽位中只有一个元素,直接将这个元素移到新的slot中作为首元素
  • 情况2:原槽位为链表或红黑树, 重新计算下标、放到新哈希表中,可能会放到两个槽位,如果红黑树的节点数小于6个 红黑树会退化为链表

6-7.png

哈希表在扩容中,同一个槽上的元素的哈希值取模只有两种可能:保持槽位不变、变成另一个固定的值(原位置+旧容量)

6.5 补充:JDK1.7与1.8扩容的区别

JDK1.7扩容

条件:发生扩容的条件必须同时满足两点

  1. 当前存储的数量大于等于阈值
  2. 发生hash碰撞

因为上面这两个条件,所以存在下面这些情况

1.就是hashmap在存值的时候(默认大小为16,负载因子0.75,阈值12),可能达到最后存满16个值的时候,再存入第17个值才会发生扩容现象,因为前16个值,每个值在底层数组中分别占据一个位置,并没有发生hash碰撞。
2.当然也有可能存储更多值(超多16个值,最多可以存26个值)都还没有扩容。原理:前11个值全部hash碰撞,存到数组的同一个位置(这时元素个数小于阈值12,不会扩容),后面所有存入的15个值全部分散到数组剩下的15个位置(这时元素个数大于等于阈值,但是每次存入的元素并没有发生hash碰撞,所以不会扩容),前面11+15=26,所以在存入第27个值的时候才同时满足上面两个条件,这时候才会发生扩容现象。

特点:先扩容,再添加(扩容使用的头插法)

缺点:头插法会使链表发生反转,多线程环境下可能会死循环

扩容之后对table的调整:

table容量变为2倍,所有的元素下标需要重新计算,newIndex = hash (扰动后) & (newLength - 1)

JDK1.8扩容

条件

  1. 当前存储的数量大于等于阈值
  2. 当某个链表长度>=8,但是数组存储的结点数size() < 64时

特点:先插后判断是否需要扩容(扩容时是尾插法)

缺点:多线程下,1.8会有数据覆盖

举例:
线程A:往index插,index此时为空,可以插入,但是此时线程A被挂起
线程B:此时,对index写入数据,A恢复后,就把B数据覆盖了

扩容之后对table的调整

table容量变为2倍,但是不需要像之前一样计算下标,只需要将hash值和旧数组长度相与即可确定位置。

  1. 如果是单个元素直接插入新数组的相应位置;如果 Node 桶的数据结构是链表会生成 low 和 high 两条链表,是红黑树则生成 low 和 high 两颗红黑树
  2. 依靠 (hash & oldCap) == 0 判断 Node 中的每个结点归属于 low 还是 high。
  3. 把 low 插入到 新数组中 当前数组下标的位置,把 high 链表插入到 新数组中 [当前数组下标 + 旧数组长度] 的位置
  4. 如果生成的 low,high 树中元素个数小于等于6退化成链表再插入到新数组的相应下标的位置

七、hashMap的寻址算法

  • 扰动算法:hash值更加均匀,减少hash冲突。主要分为两步
    • key.hashCode(),获取key的hashCode值,如果不进行重写的话返回的是根据内存地址得到的一个int值
    • key.hashCode() 获取到的hashcode无符号右移16位并和原hashCode进行^ ,这样做的目的是为了让高位与低进行混合,让两者都参与运算,以便让hash值分布更加均匀
  • (n - 1) & hash:得到数组中的索引,代替取模,性能更好。数组长度必须是2的n次幂

7-1.png

八、链表升级成红黑树的条件

在Java的HashMap实现中,链表转换为红黑树的条件包括链表长度和HashMap的容量(桶数组大小),即链表长度阈值、最小树化容量。具体规则如下:

单个桶中链表的长度大于8 且 数组长度大于64,转换为红黑树(如果容量小于64,即使链表长度达到8,也不会进行树化,而是会选择扩容)。

补充:

1)最小树化容量——HashMap的总容量(桶数组大小)必须至少为64。如果容量小于64,即使链表长度达到8,也不会进行树化,而是会选择扩容。

2)注意与扩容条件区分

  • HashMap扩容:初始化后放入元素时,或者 元素数量达到阈值时(注意是元素数量,即键值对数量
  • 链表升级为红黑树:链表的长度大于8 且 数组长度大于64转换为红黑树(此处是数组长度、即桶数组大小,而非键值对数量)

九、红黑树退化成链表的条件

在HashMap实现中,红黑树会在一定条件下转换回链表。这主要是为了在删除元素后,保持合适的数据结构以优化性能和空间使用。红黑树转换为链表的条件如下:

  • 红黑树节点数量小于6:扩容 resize( ) 时,红黑树拆分成的树的结点数小于等于临界值6个,则退化成链表【因为在少量节点的情况下,链表的插入和删除操作比红黑树更高效】
  • 删除元素 remove( ) 时,在 removeTreeNode( ) 方法会检查红黑树是否满足退化条件,与结点数无关。如果红黑树根 root 为空,或者 root 的左子树/右子树为空,root.left.left 根的左子树的左子树为空,都会发生红黑树退化成链表

补充:最小树化容量——这是一个辅助条件,用于确保只有在HashMap的容量(桶数组大小)足够大时,才会执行链表到红黑树的转换和反转换。默认情况下,这个值是64。但是转回链表的主要依据还是节点数量。

十、HashMap是怎么解决哈希冲突的

  1. 使用链地址法(使用散列表)来链接拥有相同下标的数据
  2. 使用2次扰动函数(hash函数)来降低哈希冲突的概率,使得数据分布更平均
  3. 引入红黑树进一步降低遍历的时间复杂度,使得遍历更快

十一、为什么我们需要hash()函数 (n-1)\&hash,而不是直接用key的hashcode直接计算下标

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
   
    //...
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    //...
}

让高位也参与运算,使得分布更加散列,最终达到降低哈希冲突的目的。

详解如下:

假设扩容前的长度为16,keyhash值为xxxx 1011,则扩容前元素的下标计算过程为:

int index  =(n - 1) & hash;
            = (16 - 1) & xxxx 1011
            = 15  & xxxx 1011
            = 1111 & xxxx 1011
            = 1011
            = 11

因为与(&)计算原理为必须对位的两个值都是1才为1,所以这里实际参与计算的只有hash值的低4位;

由于HashMap的容量为2的次方,所以(容量-1)可以转化为N个相连的数位1;在发生扩容后,容量增长为原来的两倍即32,此时参与重新计算下标的值为 (n-1)=31,转化为二进制为 1 1111;

int index  =(n - 1) & hash;
            = (32 - 1) & xxxx 1011
            = 31  & xxxx 1011
            = 1 1111 & xxxx 1011

我们看一下两次运算结构的差别

11-1.png

可以看到扩容前hash值实际参与运算的数位为4,扩容后实际参与运算的数位为5;由于扩容前后hash值是不变的,所以运算结果的后4位也不会发生改变;

当扩容后的最高位,也就是第5位对应的x值为0时,最后的运算结果和原来一样,即此节点在新表中的下标和原来一样,归入不需要迁移的链表中;

当第5位对应的x值为1时,最后运算结果的后4为和原来一样,只是第五位变成了1,下标值发生了改变,归入需要迁移的链表中。可以理解为

11011 = 1011 + 1 0000 ;
新下标 = 旧下标 + 旧容量;

总结

  • 当x=0时(也就是源码中 (e.hash & oldCap) == 0),此节点在新表中的位置不需要移动。
  • 当x=1时(也就是源码中 (e.hash & oldCap) == 1),此节点在新表中的位置发生了移动,移动的方式为:新下标 = 旧下标 + 旧容量。

通过计算可以发现,当容量为16时,通过对两个最高位不同、最低位相同的key求下标时,最后的结果是相等的;假如这样的key很多,则可能导致大量元素都被放入同一个桶中,造成hash冲突的可能性非常高。

为了避免这种情况出现,在进行下标计算前,我们需要通过hash函数对key的hashCode进行扰动运算,让高位也参与运算,使得分布更加散列,最终达到降低哈希冲突的目的。

十二、为何HashMap的数组长度一定是 2^n 次幂?

这是为了尽量将集合元素均摊到数组的不同位置上:让 HashMap 存取⾼效,尽量较少碰撞,也就是要尽量把数据分配均匀。

  1. 计算索引时效率更高:如果是 2 的 n 次幂可以使用位与运算代替取模【HashMap 在确定元素对应的数组下标时,是采用了 hashCode 对数组长度取余的运算,它其实等价于 hashCode 对数组长度 - 1 的与运算(h % length 等价于 h & (lenght -1),与运算效率更高,偶数才成立)】
  2. 而 2^n 次幂对应的 length - 1 恰好全是 1(1000-1 = 111),这样就把影响下标的因素归结于 hashCode 本身,因而能够实现尽可能均摊。
  3. 扩容时重新计算索引效率更高: hash & oldCap == 0 的元素留在原来位置 ,否则新位置 = 旧位置 + oldCap

我们上⾯也讲到过,Hash 值的范围值-2147483648 到 2147483647,前后加起来⼤概 40 亿的映射空间,只要哈希函数映射得⽐较均匀松散,⼀般应⽤是很难出现碰撞的。但问题是⼀个 40 亿⻓度的数组,内存是放不下的。所以这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算,得到的余数才能⽤来要存放的位置也就是对应的数组下标。这个数组下标的计算⽅法是“ (n - 1) & hash ”。(n
代表数组⻓度)。这也就解释了 HashMap 的⻓度为什么是 2 的幂次⽅。

这个算法应该如何设计呢? 我们⾸先可能会想到采⽤%取余的操作来实现。但是,重点来了:取余(%)操作中如果除数是 2 的幂次则等价于与其除数减⼀的与(&)操作(也就是说 hash%length==hash&(length-1) 的前提是length 是 2 的 n 次⽅)。并且 采⽤⼆进制位操作 &,相对于%能够提⾼运算效率,这就解释了HashMap 的⻓度为什么是 2 的幂次⽅。

十三、hashmap在1.7情况下的多线程死循环问题

jdk7的的数据结构是:数组+链表

在数组进行扩容的时候,因为链表是头插法,在进行数据迁移的过程中,有可能导致死循环【下面代码是HashMap的扩容操作,重新定位每个桶的下标,并采用头插法将元素迁移到新数组中。头插法会将链表的顺序翻转,这也是形成死循环的关键点】

13-1.png

13-2.png

13-3.png

参考回答

在jdk1.7的hashmap中在数组进行扩容的时候,因为链表是头插法,在进行数据迁移的过程中,有可能导致死循环。

比如说,现在有两个线程

线程一:读取到当前的hashmap数据,数据中一个链表,在准备扩容时,线程二介入

线程二:也读取hashmap,直接进行扩容。因为是头插法,链表的顺序会进行颠倒过来。比如原来的顺序是AB,扩容后的顺序是BA,线程二执行结束。

线程一:继续执行的时候就会出现死循环的问题。

线程一先将A移入新的链表,再将B插入到链头,由于另外一个线程的原因,B的next指向了A,所以B->A->B,形成循环。当然,JDK 8 将扩容算法做了调整,不再将元素加入链表头(而是保持与扩容前一样的顺序),尾插法,就避免了jdk7中死循环的问题。

十四、为什么经常使用String作为HashMap的Key

1、不可变类 String 可以避免修改后无法定位键值对: 假设 String 是可变类,当我们在 HashMap 中构建起一个以 String 为 Key 的键值对时,此时对 String 进行修改,那么通过修改后的 String 是无法匹配到刚才构建过的键值对的,因为修改后的 hashCode 可能是变化的。而不可变类可以规避这个问题。

2、String 能够满足 Java 对于 hashCode() 和 equals() 的通用约定: 既两个对象 equals() 相同,则 hashCode() 相同,如果 hashCode() 相同,则 equals() 不一定相同。这个约定是为了避免两个 equals() 相同的 Key 在 HashMap 中存储两个独立的键值对,引起矛盾。

十五、HashMap与Hashtable的区别

Hashtable和HashMap都是 基于hash表实现的K-V结构的集合,Hashtable是jdk1.0引入的一个线程安全的集合类,内部使用数组+链表的形式来实现

从功能特性的角度来说

1、Hashtable是线程安全的(HashTable 对每个方法都增加了 synchronized),而HashMap不是

2、HashMap的性能要比Hashtable更好,因为Hashtable采用了全局同步锁来保证安全性,对性能影响较大

从内部实现的角度来说

1)Hashtable使用数组加链表,HashMap采用了数组+链表+红黑树

2)HashMap初始容量是16,Hashtable初始容量是11

3)HashMap可以使用null作为key;而Hashtable不允许 null 作为 Key,会抛出NullPointerException异常

他们两个的key的散列算法不同:Hashtable直接是使用key的hashcode对数组长度取模;而HashMap对key的hashcode做了二次散列,从而避免key的分布不均匀影响到查询性能

十六、HashMap的key和value可以为null

16.1 结论

  1. HashMap的key、value都可以为null
  2. Hashtable的key不允许为null,value也不能为null
  3. ConcurrentHashMap的key不允许为null,value也不能为null
  4. HashMap可以存储一个Key为null,多个value为null的元素;但是Hashtable不可以存储

16.2 Hashtable的key为什么不能为null

首先来看看Hashtable为什么不允许key为null、value也不能为null

Hashtable的put方法源码为:

public synchronized V put(K key, V value) {
   
    // Make sure the value is not null
    if (value == null) {
      //确保value不为null
        throw new NullPointerException();
    }

    // Makes sure the key is not already in the hashtable.
    Entry<?,?> tab[] = table;
    int hash = key.hashCode();    //如果key为null,此处会报空指针异常
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
   
        if ((entry.hash == hash) && entry.key.equals(key)) {
   
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}
  • 问题出现在 int hash = key.hashCode(),当key为null时,key.hashCode()会报空指针异常
  • 同理value为null,throw new NullPointerException() 也会抛出异常
  • 所以Hashtable的key、value都不能为空(区别与HashMap的put、hash方法)
  • 如果希望允许key为null,就得改写put方法中的hashCode函数,HashMap就是这么实现

16.3 HashMap的key为什么可以null

  • 源码分析

jdk1.8中,put函数为

public V put(K key, V value) {
   
    return putVal(hash(key), key, value, false, true);
}

hash(key)就是求key的hashcode,查看源码为

static final int hash(Object key) {
   
    int h;
    //当key为null的时候,不走hashCode()方法,直接返回0
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

当key为null的时候,不走hashCode()方法,直接返回0,不会抛出空指针异常,所以HashMap的key可以为null(与hashtable有区别)

示例:

public class MapNull {
   
    public static void main(String[] args) {
   
        Map<Object, Object> map1 = new HashMap<>();
        map1.put("name", "wj");
        map1.put("study", null);
        map1.put(null, "unknown");
        map1.put(null, null);
        System.out.println(map1);
    }
}

16-1.png

输出 {null=null, study=null, name=wj}

16-2.png

  • 从业务需求上来说

    • HashMap支持 null 键的原因主要是为了提供更大的灵活性和编程便利性。在某些应用场景下,开发者可能需要使用 null 作为键来存储数据。

    • 例如在一个系统中,可能存在这样一种情况:某个对象可能没有关联的键,或者出于某种特殊原因,希望用 null 来代表特殊的键值对。允许 null 键的存在使得 HashMap 能够满足这种需求

不过需要注意:虽然 HashMap 允许有一个 null 键,但如果有多个线程同时尝试将 null 键插入 HashMap,最终只会有一个键值对能够成功插入(因为键是唯一的)。此外,HashMap 中只能有一个 null 键,但是可以有任意数量的 null 值。

尽管如此,使用 null 键时仍需谨慎,因为它可能会导致代码难以理解和维护,并且在多线程环境下如果没有正确同步,会增加并发问题的风险。

16.4 ConcurrentHashMap的key和value都不能为null

jdk1.8中,ConcurrentHashMap put函数的源码为:

public V put(K key, V value) {
   
    return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
   
    // 在此处直接过滤掉key或value为null的情况
    if (key == null || value == null) throw new NullPointerException();
    // 另外其hash值采用了二次hash,使得hash值分布更均匀
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
   
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
   
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
   
            V oldVal = null;
            synchronized (f) {
   
                if (tabAt(tab, i) == f) {
   
                    if (fh >= 0) {
   
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
   
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
   
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
   
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
   
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
   
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
   
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

根据源码可知,当key为null、或value为null时,会抛出空指针异常 throw new NullPointerException(),因此ConcurrentHashMap的key和value都不能为null。

16.5 总结

  • HashMap的key、value都可以为null
    • hashMap中使用hash()方法来计算key的哈希值,当key为空时,直接令key的哈希值为0,不走key.hashCode()方法;HashMap将键值对添加进数组时,不会主动判断value是否为null(而Hashtable则首先判断value是否为null)
    • hashMap虽然支持key和value为null,但是null作为key只能有一个,null作为value可以有多个
    • 因为hashMap中,如果key值一样,那么会覆盖相同key值的value为最新,所以key为null只能有一个
  • Hashtable的key不允许为null,value也不能为null。Hashtable首先判断null是否为null;后续也会直接调用key的hashCode()方法,因此如果key为null,则抛出空指针异常
  • HashMap可以存储一个Key为null,多个value为null的元素;但是Hashtable不可以存储。以上原因主要是由于Hashtable继承自Dictionary,而HashMap继承自AbstractMap
  • ConcurrentHashMap的key不允许为null,value也不能为null。虽然ConcurrentHashMap也继承自AbstractMap,但其也过滤掉了key或value为null的键值对。

参考黑马程序员相关视频和笔记、HashMap扩容流程HashMap实现原理, 扩容机制,面试题和总结

相关文章
|
2月前
|
Java 索引
让星星⭐月亮告诉你,HashMap之往红黑树添加元素-putTreeVal方法源码解读
本文详细解析了Java `HashMap` 中 `putTreeVal` 方法的源码,该方法用于在红黑树中添加元素。当数组索引位置已存在红黑树类型的元素时,会调用此方法。具体步骤包括:从根节点开始遍历红黑树,找到合适位置插入新元素,调整节点指针,保持红黑树平衡,并确保根节点是链表头节点。通过源码解析,帮助读者深入理解 `HashMap` 的内部实现机制。
35 2
|
20天前
|
存储 缓存 安全
大厂面试高频:ConcurrentHashMap 的实现原理( 超详细 )
本文详细解析ConcurrentHashMap的实现原理,大厂高频面试,必知必备。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:ConcurrentHashMap 的实现原理( 超详细 )
|
2月前
|
存储 算法 安全
HashMap的实现原理,看这篇就够了
关注【mikechen的互联网架构】,10年+BAT架构经验分享。深入解析HashMap,涵盖数据结构、核心成员、哈希函数、冲突处理及性能优化等9大要点。欢迎交流探讨。
HashMap的实现原理,看这篇就够了
|
18天前
|
SQL 存储 Oracle
大厂面试高频:聊下分库分表与读写分离的实现原理
本文详解了分库分表和读写分离的原理与实现,帮助解决大数据量下的性能瓶颈问题,大厂面试高频,建议收藏。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:聊下分库分表与读写分离的实现原理
|
21天前
|
存储 缓存 Java
大厂面试高频:Volatile 的实现原理 ( 图文详解 )
本文详解Volatile的实现原理(大厂面试高频,建议收藏),涵盖Java内存模型、可见性和有序性,以及Volatile的工作机制和源码案例。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:Volatile 的实现原理 ( 图文详解 )
|
2月前
|
存储 Java 程序员
Java面试加分点!一文读懂HashMap底层实现与扩容机制
本文详细解析了Java中经典的HashMap数据结构,包括其底层实现、扩容机制、put和查找过程、哈希函数以及JDK 1.7与1.8的差异。通过数组、链表和红黑树的组合,HashMap实现了高效的键值对存储与检索。文章还介绍了HashMap在不同版本中的优化,帮助读者更好地理解和应用这一重要工具。
57 5
|
2月前
|
存储
HashMap扩容机制
【10月更文挑战第11天】 `HashMap`的扩容机制是其重要特性之一。当容量达到负载因子(默认0.75)时,会触发扩容。扩容时,新容量通常是原容量的两倍,元素需重新哈希并迁移到新数组中。此过程涉及大量计算和迁移,可能影响性能。合理设置初始容量和负载因子,可减少不必要的扩容。在多线程环境中,还需注意线程安全问题。
|
2月前
|
Java 索引
让星星⭐月亮告诉你,HashMap中红黑树TreeNode的split方法源码解读
本文详细解析了Java中`HashMap`的`TreeNode`类的`split`方法,该方法主要用于在`HashMap`扩容时将红黑树节点从旧数组迁移到新数组,并根据`(e.hash & oldCap)`的结果将节点分为低位和高位两个子树。低位子树如果元素数少于等于6,则进行去树化操作;若多于6且高位子树非空,则进行树化操作,确保数据结构的高效性。文中还介绍了`untreeify`和`replacementNode`方法,分别用于将红黑树节点转换为普通链表节点。
26 2
|
2月前
|
存储 Java
HashMap之链表转红黑树(树化 )-treefyBin方法源码解读(所有涉及到的方法均有详细解读,欢迎指正)
本文详细解析了Java HashMap中链表转红黑树的机制,包括树化条件(链表长度达8且数组长度≥64)及转换流程,确保高效处理大量数据。
96 1
|
2月前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16,负载因子为0.75。当存储元素超过容量 * 负载因子时,会进行扩容。HashMap 使用哈希算法计算键的索引位置,通过链表或红黑树解决哈希冲突,确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
29 0