一篇让你彻底搞懂HashMap，面试再也不怕了（文末有彩蛋）_一篇彻底理解hashmap

作者：凡人多烦事01 | 2024-05-03 03:39:29

踩

一篇彻底理解hashmap

问题：
1.为什么面试官特别爱问HashMap的底层实现？
2.HashMap的底层实现能不能图形化？
3.问到我的话，我该怎么回答这个问题呢？

问题1
首先半仙先扯一分钟这个事情，一般公司招聘人才的时候，都会先看看这个人的技术水平怎么样，但是每个人所掌握的东西业务都不一样，但是用到的技术大同小异，但是最基本的java基础部分是每个人必须掌握的部分，所以这个问题一方面可以看出来技术水平，还可以看出来平时的业余时间的利用，当然还有最重要的一点就是这个问题可以很方便的就给面试者一个定位，也方便公司筛选人才，举个例子，公司需要招聘一个中级程序员，上来面你的第一个问题就是问你classLoader的作用以及优缺点，回答上来还好，说明水平够的，但是回答不上来，就凉凉了，但是大部分公司招程序员来，是看看你是否有可造之才，也许就因为这个问题，就导致公司可能损失了将来的CTO了，（外包公司另说），这个很像四六级的及格线，只要你干过你的前面还有后面的人，你准过四级，所以你只要给自己定位好，然后自信一点，基本上面试都没有问题，即使答不上来，你照样可以留个好印象（这个下次文章在扯，是个杀手锏，不能轻易使用），但是还是要基础扎实才行
问题2
今天的硬菜，我们要想搞懂HashMap，需要先提前搞懂一些概念还有思想，
前戏

数组
链表
数据结构中的表树图思想理念

首先我们要在内心里相信存在即合理，存储数据的结构有数组和链表，但是这都是两个比较极端的情况，为什么这么说呢？
数组存储数据的区间是连续的，占用内存比较多，也就是空间复杂度很大，但是数组的二分查找时间复杂度小，所以数组的特点就是寻址容易，插入和删除比较难。
链表存储数据的区间是离散的，占用内存宽松，空间复杂度很小，但时间复杂度很大，所以对链表进行寻址是比较困难的，但是插入和删除容易
哈希表
按照人性的理解那肯定不能只用一种是吧，有没有一种可能性，可以既能让我寻址容易，然后插入和删除也比较简单呢？哈希表正式登场，一个满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便hash table，首先定义一个概念，什么是哈希表，我自己的理解就是：根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度，这个映射函数叫做散列函数或者哈希函数，存放记录的数组叫做散列表，而核心还是hash算法（不扯算法）
哈希表有多种不同的实现方法，接下来解释的是最常用的一种方法—— 拉链法，可以理解为“链表的数组” ，如图：
数组链表图
该图中就是数组+链表的形式来存储数据的，一个长度为16的数组中，每个元素存储的是一个链表的头结点，那么我一个值来了，是怎么存进去的呢，首先通过hash算法，通过hash(key)%len获得，也就是元素的key的哈希值对数组长度取模得到，比如上面的12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置喽！
那么我往map里面存一个值的话，过程好像不是这样的，其实可以这样理解哒，HashMap就是一个线性数组实现存储的，那么一个数组怎么可能会根据键值对取值呢，那是HashMap内部实现了一个静态内部类Entry，里面的属性有key value next，其中key value 能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，所以上面说到的HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面，等下可以追溯一下源码就清楚了

/**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table; 
    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V>  //数据实际上存储在这里
    final int hash;
        final K key;
        V value;
        Node<K,V> next;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

好了，这就是我们所需要的前戏，只有前戏充足，才能尽可能快的高潮，最基本的是先知道怎么用，按照用途来进行庖丁解牛
存储数据

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     * “这个map里面，有专门的键和专门的值相关联，如果先前的map包含了一个映射的key，那么老的值就会被替代”
     * @param key key with which the specified value is to be associated //与指定的值关联的键
     * @param value value to be associated with the specified key //与指定的key关联的值
     * @return the previous value associated with <tt>key</tt>, or // 允许为空
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

put添加键值对
当你写下map.put(“key1”,1)，内部是这样操作的，注意看仔细每一行注释，思路不会断，全在注释里说明了,一定要注意case的地方，我们先理顺大体的思路，然后再细入分析case部分

 /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key  //这个是hash函数，主要是用来生成hashCode
     * @param key the key //键
     * @param value the value to put //值
     * @param onlyIfAbsent if true, don't change existing value //这个参数的意思是当key重复的时候，false 覆盖原来的value ，true 不覆盖，默认是false 
     * @param evict if false, the table is in creation mode. //用于子类LinkedHashMap。
     * @return previous value, or null if none //当覆盖掉时，返回原来的值，或者空
     */
     final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //	tab：内部数组
        //	p：hash对应的索引位中的首节点
        //	n：内部数组的长度
        //	i：hash对应的索引位
        
        //		首次put数据时，内部数组为空，扩充数组。----------->case 1:数组扩容机制?
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //	计算数组索引，获取该索引位置的首节点，如果为null，添加一个新的节点
        if ((p = tab[i = (n - 1) & hash]) == null)                 ------------->case 2:怎么去计算并找到索引的呢？
            tab[i] = newNode(hash, key, value, null);
        else {
        //	如果首节点的key和要存入的key相同，那么直接覆盖value的值。
            Node<K,V> e; K k;
            //	这个判断hash值是否一样，一样的话，就是同一个key，那么就直接覆盖
            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);
         // 此时首节点为链表，如果链表中存在该键值对，直接覆盖value。
        // 如果不存在，则在末端插入键值对。然后判断链表是否大于等于7，尝试转换成红黑树。
        // 注意此处使用“尝试”，因为在treeifyBin方法中还会判断当前数组容量是否到达64，
        // 否则会放弃次此转换，优先扩充数组容量。
        上面就是一种情况
        -----------------------------------------------------------------------------------
        // 走到这里，恭喜你，hash碰撞了。检查链表中是否包含key，或将键值对添加到链表末尾
            else {
                for (int binCount = 0; ; ++binCount) {
                // 如果p.next == null，则就是到达链表末尾，添加新节点，如果长度足够，转换成树结构
                //static final int TREEIFY_THRESHOLD = 8;
                //static final int UNTREEIFY_THRESHOLD = 6;
                //这两个参数很重要，可以判断是否需要转为树或者列表的区间值
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);									--------------------->case3:treeifyBin方法?
                        break;
                    }
           // 检查链表中是否已经包含key
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 覆盖value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                //返回老的值，-------------------->case 4:put之后的返回值代表什么含义
                return oldValue;
            }
        }
        ++modCount;//容错机制
        //如果数组的长度大于阈值，扩充数组
        if (++size > threshold)
            resize();					
        afterNodeInsertion(evict);
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

好，到此为止，你会发现put的操作整体完成，虽然看源码很痛苦，但是得到的结果却很甜蜜是吧，总结来将put操作就是以下几个步骤：

检查数组是否为空，然后执行resize()扩充；
通过hash值计算数组索引，获取到该索引位的首节点
如果首节点为null，直接添加节点到该索引位。
如果首节点不为null，那么有3种情况：
① key和首节点的key相同，覆盖value；否则执行②或③
② 如果首节点是红黑树节点（TreeNode），将键值对添加到红黑树。
③ 如果首节点是链表，将键值对添加到链表。添加之后会判断链表长度是否到达TREEIFY_THRESHOLD - 1这个阈值，“尝试”将链表转换成红黑树
5.最后判断当前元素个数是否大于threshold阈值，判断是否扩充数组
好，现在回过头来，来看注释中的case部分
case1:数组扩容resize()
首先数组扩容不是简单的说就是把长度翻倍，然后把老数组中的元素拷贝到新数组中就好了，因为元素的索引是通过hash&(n - 1)得到的，那么数组的长度由n变为2n，重新计算的索引就可能和原来的不一样了。在jdk1.7中，是通过遍历每一个元素，每一个节点，重新计算他们的索引值，存入新的数组中，也就是rehash。而java1.8对此进行了一些优化，因为当数组长度是通过2的次方扩充的，那么会发现以下规律：元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置
元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，这个设计确实非常的巧妙，既省去了重新计算hash值的时间，而且同时，由于新增的1bit是0还是1可以认为是随机的，因此resize的过程，均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别，JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置（因为从一个链表存遍历到另一个链表时导致倒置了）但是1.8的不会倒置，还是先看代码
这里有几个重要的成员信息需要知道

/**
  * 数组的默认初始长度，java规定hashMap的数组长度必须是2的次方
  * 扩展长度时也是当前长度 << 1。
  */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 数组的最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;

// 默认负载因子，当元素个数超过这个比例则会执行数组扩充操作。
static final float DEFAULT_LOAD_FACTOR = 0.75f;

// 树形化阈值，当链表节点个大于等于TREEIFY_THRESHOLD - 1时，
// 会将该链表换成红黑树。
static final int TREEIFY_THRESHOLD = 8;

// 解除树形化阈值，当链表节点小于等于这个值时，会将红黑树转换成普通的链表。
static final int UNTREEIFY_THRESHOLD = 6;

// 最小树形化的容量，即：当内部数组长度小于64时，不会将链表转化成红黑树，而是优先扩充数组。
static final int MIN_TREEIFY_CAPACITY = 64;

// 这个就是hashMap的内部数组了，而Node则是链表节点对象。
transient Node<K,V>[] table;

// 下面三个容器类成员，作用相同，实际类型为HashMap的内部类KeySet、Values、EntrySet。
// 他们的作用并不是缓存所有的key或者所有的value，内部并没有持有任何元素。
// 而是通过他们内部定义的方法，从三个角度（视图）操作HashMap，更加方便的迭代。
// 关注点分别是键，值，映射。
transient Set<K>        keySet;  // AbstractMap的成员
transient Collection<V> values; // AbstractMap的成员
transient Set<Map.Entry<K,V>> entrySet;

// 元素个数，注意和内部数组长度区分开来。
transient int size;

// 是容器结构的修改次数，fail-fast机制。
transient int modCount;

// 阈值，超过这个值时扩充数组。 threshold = capacity * load factor，具体看上面的静态常量。
int threshold;

// 装在因子，具体看上面的静态常量。
final float loadFactor;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

好，看到这些我们就知道还有构造方法了下面我们来欣赏一下构造函数，这个是可以指定初始容量，指定负载因子

//默认数组初始容量为16，负载因子为0.75f
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//这个构造可以由我们指定数组的初始容量和负载因子。
//但是数组容量必须是2的次方。所以就需要通过某个算法将我们给的数值转换成2的次方。
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // NaN：Not a Number。例如给-1开方就会得到NaN。
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    this.loadFactor = loadFactor;
    // 这个方法可以将任意一个整数转换成2的次方。
    // 另外，有人可能疑惑，不是说threshold是 数组容量 * loadFactor得到的吗？
    // 是的，在第一次put操作，扩充数组时，会将这个threshold作为数组容量，然后再重新计算这个值。
    this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

tableSizeFor该方法是将我们自己给的数值转换成2的次方

// 这个方法可以将任意一个整数转换成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;
    //原理实际上就是补位，将原本为0的空位填补为1，最后加1时，最高有效位进1，其余变为0。
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

Case 2:如何将hashCode转换成数组的索引（hash方法和取模运算）
以上就是数组扩容的原理，但是还有一个问题就是，我们第一次进行push操作的时候，用到的一个hash函数，

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
1
2
3
4
5
6
7

那么这个函数到底发挥了什么的作用呢？hash方法的作用是将hashCode进一步的混淆，增加其“随机度”，试图减少插入hash map时的hash冲突，换句更专业的话来说就是提高离散性能。而这个方法知乎上有人回答时称为“扰动函数”。
上面的代码只是用hashCode的高16位与低16位进行异或运算，为什么就能提高离散性能呢？
这里还是要看hashCode转换成数组索引时的取模运算。
在putVal方法中（不仅仅只在putVal中），有这么一行代码

if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
1
2

i = (n - 1) & hash，n是数组长度，hash就是通过hash()方法进行高低位异或运算得出来的hash值。这个表达式就是hash值的取模运算，上面已经说过当除数数为2的次方时，可以用与运算提高性能。大多数情况下，内部数组的容量一般都不会很大，基本分布在16~256之间。所以一个32位的hashCode，一直都用最低的4到8位进行与运算，而高位几乎没有参与，所以通过hash()方法，将hashCode高16位与低16位进行异或运算，能有效的提高离散性能。
Case3:涉及到红黑树了

/**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这个小李子果然不一般，这个具体的就不分析了，百度一下红黑树实现原理
Case4:返回值信息
返回值的信息主要是用来判断是否有重复的可以值，看测试结果
在这里插入图片描述
一目了然啦
取模和位运算
现在，我们可以来解释下当除数为2的次方时，取余运算可以用与运算代替的原理。
首先，我们知道2的次方的数，用二进制表示如下，是不会出现有两个1的情况。
0000 0001 // 1
0000 0010 // 2
0000 0100 // 4
0000 1000 // 8
0001 0000 // 16
0010 0000 // 32
0100 0000 // 64
1000 0000 // 128
当我们除以2的n次方时，可以看作是将二进制右移n位。例如123除以8，实际上就是123的二进制右移3位。

123 / 8
// 用移位运算可以表示为右移3位：
1111011 >> 3

123除以4的结果为15，那么余数呢？
余数正是被移位运算移走的最低3位，011，也就是余数为3。

是不是好像发现了新大陆？原来移位运算移走的那些二进制就是余数！

那么，我们只要将被移走的这3位保存起来，实际上就得到了余数，问题是怎么保存呢？
没错，通过与运算，例如一个数和15进行与运算（二进制为0000 1111），就可以取到该数的低4位。

而上面例子中，我们只要能和7（二进制为0000 0111）做与运算就可以直接得到余数了！
大家发现了什么没有，8的二进制为 0000 1000，如果减去1，是不是正好为0000 0111？
那么，只要我们 123 & （8 - 1），就可以取到123 / 8的余数了！也就是 N % M == N & (M - 1)
好了，以上就是涉及到hashMap的相关东西了，当然肯定还有很多没有提到的，还需要我们继续努力学习啊
总结来说：
先计算新数组的长度和新的阈值（threshold），然后将旧数组的内容迁移到新数组中，和1.7相比不需要执行rehash操作。因为以2次幂扩展的数组可以简单通过新增的bit判断索引位。
不过无论是1.7还是1.8版本，HashMap的扩充总归是挺消耗性能的。所以如果知道需要存入的大概数量，手动指定数组初始长度是比较好的选择。另外，如果对于内存要求比较高，可以将装载因子（loadFactor）设置成大于1的值，那么内部数组就不会进行扩充操作了，但是牺牲了性能。
皮一下，我是采?END

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/527586