【JDK源码】HashMap源码分析（附常见面试题）

HashMap源码分析（附面试题）

1.什么是哈希？

在分析HashMap之前，我们先来了解什么是哈希？

概念：Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值。

Hash的特点:

1. 从hash值不可以反向推导出原始的数据
2. 输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的
3. 哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
4. hash算法的冲突概率要小

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。
这一现象就是我们所说的“抽屉原理”。

2.HashMap的继承体系

HashMap采用

key/value

存储结构，每个key对应唯一的value，查询和修改的速度都很快，能达到

O(1)

的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序。

从继承体系可以看出：

• HashMap 实现了Cloneable接口，可以被克隆。
• HashMap 实现了Serializable接口，属于标记性接口，HashMap 对象可以被序列化和反序列化。
• HashMap 继承了AbstractMap，父类提供了 Map 实现接口，具有Map的所有功能，以最大限度地减少实现此接口所需的工作。

3.底层存储结构

• 1.7 数组 + 链表
• 1.8 数组 + （链表 | 红黑树）

在Java中，HashMap的实现采用了（数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。

在添加元素时，会根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率。

数组的查询效率为

O(1)

，链表的查询效率是

O(k)

，红黑树的查询效率是

O(log k)

，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。

树化需要同时满足两个条件：

1. 链表长度大于8，并不是大于等于8
2. 数组长度达到64。如果数组长度不够64，会优先进行resize()扩容。

4.内部类

Node内部类

Node

是HashMap的静态内部类，实现了

Map.Entry<K,V>

接口。我们存储的键值对都是以Node的形式存储在map中的。其重要属性如下：

staticclassNode<K,V>implementsMap.Entry<K,V>{//基于key的hashValue经过hash扰动后得到的，是hash分布更均匀finalint hash;//put进来的keyfinalK key;//对应的valueV value;//指向链表中的下一个NodeNode<K,V> next;...}

5.HashMap核心属性分析

/**
     * HashMap的初始化容量（必须是 2 的 n 次幂）默认的初始容量为16
     */staticfinalint DEFAULT_INITIAL_CAPACITY =1<<4;// aka 16/**
     * table最大长度
     */staticfinalint MAXIMUM_CAPACITY =1<<30;/**
     * 默认的负载因子
     */staticfinalfloat DEFAULT_LOAD_FACTOR =0.75f;/**
     * 树化阈值：当一个桶中的元素个数大于8时进行树化（同时需要数组长度达到64）
     */staticfinalint TREEIFY_THRESHOLD =8;/**
     * 树降级为链表的阈值：当一个桶中的元素个数小于等于6时把树转化为链表
     */staticfinalint UNTREEIFY_THRESHOLD =6;/**
     * Node数组，又叫作桶（bucket）
     */transientNode<K,V>[] table;/**
     * 作为entrySet()的缓存
     */transientSet<Map.Entry<K,V>> entrySet;/**
     * 当前哈希表中元素的个数
     */transientint size;/**
     * 当前哈希表结构修改次数
     */transientint modCount;/**
     * 扩容阈值，当你的哈希表中的元素超过阈值时，触发扩容（threshold = capacity * loadFactor）
     */int threshold;/**
     * 负载因子（默认0.75）
     */finalfloat loadFactor;

从属性源码我们可以得到几个信息：

1. 容量：容量为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以树化。
2. 装载因子：用来计算容量达到多少时才进行扩容，默认装载因子为0.75。
3. 树化：当容量达到64且链表的长度大于8时进行树化，当链表的长度小于6时反树化。

6.HashMap构造方法

HashMap()

构造一个空的HashMap，默认初始容量（16）和默认负载因子（0.75）

publicHashMap(){// 将默认的负载因子0.75赋值给loadFactor，并没有创建数组this.loadFactor = DEFAULT_LOAD_FACTOR;}

HashMap(int initialCapacity)

构造指定初始容量

initialCapacity

的HashMap，其实也是调用

HashMap(int initialCapacity，float loadFactor)

，默认的负载因子

/**
* 指定初始容量大小的构造函数
* @param initialCapacity
*/publicHashMap(int initialCapacity){this(initialCapacity, DEFAULT_LOAD_FACTOR);}

HashMap(int initialCapacity，float loadFactor)

构造一个具有指定的初始容量

initialCapacity

和负载因子

loadFactor

的 HashMap

/*
指定“容量大小”和“负载因子”的构造函数
initialCapacity：指定的容量
loadFactor:指定的负载因子
*/publicHashMap(int initialCapacity,float loadFactor){//判断初始容量initialCapacity是否小于0if(initialCapacity <0)thrownewIllegalArgumentException("Illegal initial capacity: "+
                                           initialCapacity);//判断初始容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITYif(initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;//判断负载因子loadFactor是否<=0或者是否是一个非数值if(loadFactor <=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegal load factor: "+
                                           loadFactor);//将指定的负载因子loadFactor赋值给HashMap成员变量的负载因子this.loadFactor = loadFactor;//给扩容阈值赋值（只能是2的次方）this.threshold =tableSizeFor(initialCapacity);}/**
     * 作用：返回比指定cap容量大的最小2的n次幂数
     * 栗子：cap=10
     * n=10-1=9
     * 0b1001 | 0b0100 = 0b1101
     * 0b1101 | 0b0011 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * ob1111->15
     * 15>0 -> return 15+1(16)
     * 模式：0001 1101 1100 => 0001 1111 1111 +1 => 0010 0000 0000
     */staticfinalinttableSizeFor(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;}

7.put方法

put方法的整体流程：

1. 计算key的hash值
2. 如果桶（数组）数量为0，则初始化桶
3. 如果key所在的桶没有元素，则直接插入
4. 如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理
5. 如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
6. 如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
7. 如果找到了对应key的元素，则转后续流程（9）处理
8. 如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
9. 如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
10. 如果插入了元素，则数量加1并判断是否需要扩容

publicVput(K key,V value){// 调用hash(key)计算出key的hash值returnputVal(hash(key), key, value,false,true);}

/**
     * 作用：让key的hash值的高16位参与运算
     * @param key
     * @return
     */staticfinalinthash(Object key){int h;//key==null直接返回0//1、否则调用key的hashCode()方法计算出key的哈希值然后赋值给h,//2、后与h无符号右移16位后的二进制进行按位异或得到最后的hash值,//3、这样做是为了使计算出的hash更分散，让高16位可以参与（低16位具有高16位的特征）return(key ==null)?0:(h = key.hashCode())^(h >>>16);}

/**
     *
     * @param hash  key的hash值
     * @param key   原始key
     * @param value 要存放的值
     * @param onlyIfAbsent  如果 true 代表不更改现有的值，也就是说如果存在key就不改变，一般传入false
     * @param evict  如果为false表示 table 为创建状态
     * @return
     */finalVputVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict){//tab：引用当前hashMap的散列表//p：表示当前散列表的元素//n：表示散列表数组的长度//i：表示路由寻址结果Node<K,V>[] tab;Node<K,V> p;int n, i;// 如果桶的数量为0，则初始化if((tab = table)==null||(n = tab.length)==0)// 调用resize()初始化
        n =(tab =resize()).length;//最简单的一种情况：寻址找到的桶位null，直接将创建一个新结点放入桶中if((p = tab[i =(n -1)& hash])==null)
        tab[i]=newNode(hash, key, value,null);else{//e：不为null的话，找到一个与当前要插入的key-value一致的key元素//k：临时的一个keyNode<K,V> e;K k;//表示桶位中的该元素，与你当前插入的元素key完全一致，表示后续要进行替换操作if(p.hash == hash &&((k = p.key)== key ||(key !=null&& key.equals(k))))
            e = p;elseif(p instanceofTreeNode)// 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素
            e =((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else{// 遍历这个桶对应的链表，binCount用于存储链表中元素的个数for(int binCount =0;;++binCount){//条件成立的话，说明迭代到最后一个元素了，也没找到一个与你插入的key一致的node//说明需要加入到当前链表的尾部if((e = p.next)==null){
                    p.next =newNode(hash, key, value,null);//条件成立的话，说明当前链表的长度达到树化的标准了，需要进行树化if(binCount >= TREEIFY_THRESHOLD -1)//树化操作treeifyBin(tab, hash);break;}//说明条件成立的化，找到了相同key的node元素，进行替换操作if(e.hash == hash &&((k = e.key)== key ||(key !=null&& key.equals(k))))break;
                p = e;}}//e不等于null，说明找到了一个与你插入元素key完全一致的数据，需要进行替换if(e !=null){// existing mapping for keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)
                e.value = value;// 在节点被访问后做点什么事，在LinkedHashMap中用到afterNodeAccess(e);// 返回旧值return oldValue;}}//散列表结果修改次数加一，替换Node元素的value不计数++modCount;//插入新元素，size自增//如果大于扩容阈值，扩容if(++size > threshold)resize();// 在节点插入后做点什么事，在LinkedHashMap中用到afterNodeInsertion(evict);// 没找到元素返回nullreturnnull;}

8.resize扩容方法

整个扩容流程：

1. 如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12
2. 如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方
3. 如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍
4. 创建一个新容量的桶
5. 搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置

/**
     * 为什么需要扩容？
     * 为了解决hash冲突导致的链化影响查询效率的问题，扩容会缓解该问题
     *
     * @return
     */finalNode<K,V>[]resize(){//引用扩容前的哈希表Node<K,V>[] oldTab = table;//表示扩容之前的table数组的长度int oldCap =(oldTab ==null)?0: oldTab.length;//扩容之前的扩容阈值int oldThr = threshold;//newCap：扩容之后table数组的大小//newThr：扩容之后，下次在触发扩容的条件int newCap, newThr =0;//条件入如果成立：说明hashMap中的散列表已经初始化过了，是一次正常扩容if(oldCap >0){//如果旧容量达到最大容量，则不再进行扩容if(oldCap >= MAXIMUM_CAPACITY){
            threshold =Integer.MAX_VALUE;return oldTab;}// 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两部，扩容门槛也扩大为两倍elseif((newCap = oldCap <<1)< MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr <<1;// double threshold}elseif(oldThr >0)// initial capacity was placed in threshold//使用非默认构造方法创建的map，第一次插入元素会走到这里//1.new HashMap(initCap,loadFactor);//2.new HashMap(initCap);//3.new HashMap(map); map有数据// 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛
        newCap = oldThr;else{//使用默认构造方法创建的map，第一次插入元素会走这里
        newCap = DEFAULT_INITIAL_CAPACITY;//如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子
        newThr =(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if(newThr ==0){//如果旧容量旧扩容门槛都是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>[])newNode[newCap];//把桶赋值为新数组
    table = newTab;//如果旧数组不为空，则搬移元素if(oldTab !=null){//遍历旧数组for(int j =0; j < oldCap;++j){//当前node节点Node<K,V> e;//如果当前桶中第一个元素不为空，说明当前桶位有数据，赋值给eif((e = oldTab[j])!=null){//清空旧桶，方便JVM GC时回收内存
                oldTab[j]=null;if(e.next ==null)//第一种情况：当前桶位只有一个元素，从未发生过碰撞//该情况直接计算出当前元素应该存放的新数组中的位置，然后扔进去就行
                    newTab[e.hash &(newCap -1)]= e;elseif(e instanceofTreeNode)//第二种情况：当前桶位已经树化,则把这颗树打散成两颗树插入到新桶中去((TreeNode<K,V>) e).split(this, newTab, j, oldCap);else{//第三种情况：链表情况// 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中// 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去// 也就是分化成了两个链表//低位链表：存放在扩容之后下标位置与当前数组下标位置一致Node<K,V> loHead =null, loTail =null;//高位链表：存放在扩容之后的数组的下标位置=为当前数组下标位置+扩容之前数组的长度Node<K,V> hiHead =null, hiTail =null;Node<K,V> next;do{
                        next = e.next;// (e.hash & oldCap) == 0的元素放在低位链表中//比如3&4==0if((e.hash & oldCap)==0){if(loTail ==null)
                                loHead = e;else
                                loTail.next = e;
                            loTail = e;}else{// (e.hash & oldCap) != 0的元素放在高位链表中//比如，7&4！=0if(hiTail ==null)
                                hiHead = e;else
                                hiTail.next = e;
                            hiTail = e;}}while((e = next)!=null);// 遍历完成分化成两个链表了// 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）if(loTail !=null){
                        loTail.next =null;
                        newTab[j]= loHead;}// 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）if(hiTail !=null){
                        hiTail.next =null;
                        newTab[j + oldCap]= hiHead;}}}}}return newTab;}

9.get方法

publicVget(Object key){Node<K,V> e;//这里hash(key)是因为put的时候hash了，这里取自然也需要hashreturn(e =getNode(hash(key), key))==null?null: e.value;}finalNode<K,V>getNode(int hash,Object key){//引用当前hashMap的散列表Node<K,V>[] tab;//first:桶位中的头元素//e:临时node元素Node<K,V> first, e;//n:table数组长度int n;K k;// 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空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;// 第一个元素不是要查找的元素，并且当前桶位不止一个元素，可能存在链表或者树if((e = first.next)!=null){// 如果第一个元素是树节点，则按树的方式查找if(first instanceofTreeNode)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);}}returnnull;}

get方法具体分这几步：

1. 计算key的hash值
2. 找到key所在的桶及其第一个元素
3. 如果第一个元素的key等于待查找的key，直接返回
4. 如果第一个元素是树节点就按树的方式来查找
5. 否则就按链表方式查找

10.remove方法

publicVremove(Object key){Node<K,V> e;return(e =removeNode(hash(key), key,null,false,true))==null?null: e.value;}finalNode<K,V>removeNode(int hash,Object key,Object value,boolean matchValue,boolean movable){//引用当前hashMap中的散列表Node<K,V>[] tab;//当前node元素Node<K,V> p;//n:表示散列表数组长度//index:表示寻址结果int n, index;// 如果桶的数量大于0且待删除的元素所在的桶的第一个元素不为空if((tab = table)!=null&&(n = tab.length)>0&&(p = tab[index =(n -1)& hash])!=null){//node:表示查找到的结果//e:表示当前node的下一个元素Node<K,V> node =null, e;K k;V v;// 如果第一个元素正好就是要找的元素，赋值给node变量后续删除使用if(p.hash == hash &&((k = p.key)== key ||(key !=null&& key.equals(k))))
            node = p;// 第一个元素不是要查找的元素，并且当前桶位不止一个元素，可能存在链表或者树elseif((e = p.next)!=null){if(p instanceofTreeNode)// 如果第一个元素是树节点，则以树的方式查找节点
                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);}}// 如果找到了元素，则看参数是否需要匹配value值，如果不需要匹配直接删除，如果需要匹配则看value值是否与传入的value相等if(node !=null&&(!matchValue ||(v = node.value)== value ||(value !=null&& value.equals(v)))){if(node instanceofTreeNode)// 如果是树节点，调用树的删除方法（以node调用的，是删除自己）((TreeNode<K,V>) node).removeTreeNode(this, tab, movable);elseif(node == p)// 如果待删除的元素是第一个元素，则把第二个元素移到第一的位置
                tab[index]= node.next;else// 否则删除node节点，将当前元素p的下一个元素设置为删除元素的下一个元素
                p.next = node.next;++modCount;--size;// 删除节点后置处理afterNodeRemoval(node);return node;}}returnnull;}

整个remove流程分为这几步：

1. 先查找元素所在的节点
2. 如果找到的节点是树节点，则按树的移除节点处理
3. 如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置
4. 否则按链表删除节点处理
5. 修改size，调用移除节点后置处理等

11.总结

1. HashMap是一种散列表，采用（数组 + 链表 + 红黑树）的存储结构
2. HashMap的默认初始容量为16（1<<4），默认装载因子为0.75f，容量总是2的n次方
3. HashMap扩容时每次容量变为原来的两倍
4. 当桶的数量小于64时不会进行树化，只会扩容
5. 当桶的数量大于64且单个桶中元素的数量大于8时，进行树化
6. 当单个桶中元素数量小于6时，进行反树化
7. HashMap是非线程安全的容器
8. HashMap查找添加元素的时间复杂度都为O(1)

HashMap在JDK1.7和1.8中不同

• 1.7 数组 + 链表
• 1.8 数组 + （链表 | 红黑树）

为啥要用红黑树？

红黑树用来避免

DoS

攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略

为何不一上来就树化？

• hash 表的查找，更新的时间复杂度是 O ( 1 ) O(1) O(1)，而红黑树的查找，更新的时间复杂度是 O ( l o g 2 ⁡ n ) O(log_2⁡n ) O(log2​⁡n)
• TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

树化阈值为何是8？

hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子

0.75

的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

树化规则

• 当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化
• 树化的两个条件：链表长度超过树化阈值>8 && 数组容量>=64

退化规则

• 情况1：在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表
• 情况2：移除之前，remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

索引计算方法

1. 首先，计算对象的 hashCode()
2. 再进行调用 HashMap 的 hash() 方法进行二次哈希。二次 hash() 是为了综合高位数据，让哈希分布更为均匀
3. 最后 & (capacity – 1) 得到索引

数组容量为何是 2 的 n 次幂

• 计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模
• 扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置 ，否则新位置 = 旧位置 + oldCap

注意：

• 二次 hash 是为了配合 容量是 2 的 n 次幂 这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash
• 容量是 2 的 n 次幂 这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

put 流程

1. HashMap 是懒惰创建数组的，首次使用才创建数组
2. 计算索引（桶下标）
3. 如果桶下标还没人占用，创建 Node 占位返回
4. 如果桶下标已经有人占用 - 已经是 TreeNode 走红黑树的添加或更新逻辑- 是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
5. 返回前检查容量是否超过阈值，一旦超过进行扩容

put流程1.7中和1.8的区别

1. 链表插入节点时，1.7 是头插法，1.8 是尾插法
2. 1.7 是大于等于阈值且没有空位时才扩容，而 1.8 是大于阈值就扩容
3. 1.8 在扩容计算 Node 索引时，会优化

扩容（加载）因子为何默认是 0.75f

1. 在空间占用与查询时间之间取得较好的权衡
2. 大于这个值，空间节省了，但链表就会比较长影响性能
3. 小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

key 的设计要求

1. HashMap 的 key 可以为 null，但 Map 的其他实现则不然（Hashtable等）
2. 作为 key 的对象，必须实现 hashCode 和 equals，并且 key 的内容不能修改（不可变）
3. key 的 hashCode 应该有良好的散列性
4. 如果 key 可变，例如修改了 age 会导致再次查询时查询不到

String 对象的 hashCode() 设计

• 目标是达到较为均匀的散列效果，每个字符串的 hashCode 足够独特
• 字符串中的每个字符都可以表现为一个数字，称为 S i S_i Si​，其中 i 的范围是 0 ~ n - 1
• 散列公式为： S 0 ∗ 3 1 ( n − 1 ) + S 1 ∗ 3 1 ( n − 2 ) + … S i ∗ 3 1 ( n − 1 − i ) + … S ( n − 1 ) ∗ 3 1 0 S_0∗31^{(n-1)}+ S_1∗31^{(n-2)}+ … S_i ∗ 31^{(n-1-i)}+ …S_{(n-1)}∗31^0 S0​∗31(n−1)+S1​∗31(n−2)+…Si​∗31(n−1−i)+…S(n−1)​∗310
• 31 代入公式有较好的散列特性，并且 31 * h 可以被优化为 - 即 $32 ∗h -h $- 即 2 5 ∗ h − h 2^5 ∗h -h 25∗h−h- 即 h ≪ 5 − h h≪5 -h h≪5−h