1、引用类型的公共父类——Object，Object中的hashCode()；

hashCode的存在主要是用于查找的快捷性，如Hashtable、HashMap、HashSet等，hashCode是用来在散列存储结构中确定对象的存储地址的；

2、<Key,Value>中要求Key为引用类型；

那么引用类型它们的公共父类就是Object，而我们知道，Object方法中拥有hashCode()方法，我们可以获取到这个key对象的hashCode值，而Object为我们提供的hashCode值就是为我们在Java中使用散列相关的操作做准备的；

3、不同对象可能存在一样的hashCode值；

hashCode取值范围是int范围，为有限数。
对象的个数可以无穷，为无限数。
想要用有限的值来表示无限的对象，必定存在重复。

相同的hashCode字符串记录

System.out.println("Aa".hashCode()); // 2112
System.out.println("BB".hashCode()); // 2112
System.out.println("ABCDEa123abc".hashCode()); // 165374702
System.out.println("ABCDFB123abc".hashCode()); // 165374702

4、HashMap存储数据，先判断key的hashCode，不存在相同的hashCode元素则直接存储；存在相同则再比较key的equals，如果依然相等则用新value替换原value；

            Node<K,V> e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
...
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

如此，针对同样的一个key(引用类型equals判断相等)，只会对应存储一个value值。
附Key代码——重写Key类型hashCode、equals

class Key {
    Integer id;
    String name;
    public Key(Integer id, String name) {
        this.id = id;
        this.name = name;
    }
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Key key = (Key) o;
        // equals()跟hashCode()保持一致
        return Objects.equals(id, key.id);
    }
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

5、HashMap是如何快速寻址的？如何快速获取value——map.get(key)；

根据key的hashCode值，经过一些计算，快速定位Node<K,V>在散列表(数组)中的下标位置，直接获取Node，获取Node中V；(如果下标位置处存在冲突，则会存在额外链表/二叉树寻址操作)

6、HashMap数据结构——散列表(数组)+解决冲突方案(链表、二叉树)；

容量及散列表(数组)长度，默认负载因子0.75，当存储的Node数据量(size)大于 0.75 * 容量，则会对HashMap进行扩容。

7、存、取数据，如何定位数组下标(散列值)？

1、我们知道int，4个字节，32位。我们没办法确认一个key对应的hashCode有多大，只知道在int范围内，可以用32位二进制表示，可能这个值非常小，可能非常大；
2、hashCode——32位，包含高16位跟低16位；
3、hashMap中是这样操作的——获取一个更具有代表性的数值。将原hashCode值右移16位(也就是保留高16位)跟原hashCode值(全32位)按位异或(^)取得一个值(32位，高位可能都为0)；(如果key为null，则直接用0表示)
4、因为可能容量比较小，所以用高低16位都参与，获取一个更具有代表性的数值，以便于接下来的取模操作；——我们把这个值叫做HashMap中的hash值

image.png
5、这样做的好处？如果这个key的hashCode值比较小，那么它的高16位跟它自己按位^还是它原来的hashCode值；如果这个key的hashCode值比较大，那么形成的数更具有代表这个hashCode的能力，因为高低位都参与了，对于大hashCode值的重新离散效果更好；(假想高16位不参与，当hashCode较大时那么可能存在大量的重复值，不利于离散)，毕竟我们数组初始化容量的值都比较小，这也跟我们的后面取模算法相关；
6、然后用这个^后产生的hash数值，跟hash&数组最大下标值(容量-1)，取模——即该元素需要存储的数组下标值；hash&(len-1)即h%len(前提条件，len必须为2的n次幂值)，&运算优于%运算；

8、为何默认初始化容量16？为啥15不行？10不行？

容量16 -> 数组最大下标15 = 1111 -> 扩容 数组下标最大 31 = 11111 -> 一半移动；
容量15 -> 数组最大下标14 = 1110 -> 扩容 数组下标最大 29 = 11101 -> 重新hash、很多数据都要移动；

9、为何二倍扩容？1.5倍不行？

容量16 -> 数组最大下标15 = 1111 -> 1.5倍扩容 数组下标最大 23 = 10111 -> 重新hash、很多数据都要移动；
初始化大小、时间空间综合考虑，16是最合适的，2倍扩容，算法是最优的；

扩容核心

新增一倍的空间，将原空间中的一半数据分过去！达到一个新的离散平衡，并且扩容时间成本最低！

10、树形化；

条件：

1、 冲突位置长度>8;
2、 容量大小已经>64，否则会用扩容机制减少冲突而非树形化；
树形化之后，原链表结构依旧存在且继续维持，便于退化成链表，减少时间操作，且链表更适合遍历，遍历元素时，依旧使用链表特性；

11、链表+红黑二叉树同存；

在链表转化成红黑二叉树之后，其实链表结构并没有退化，而是继续维持且更新，便于后期扩容、或数据缩减时退化成链表，也可以继续使用链表的优势，比如全局遍历...

12、HashMap最大容量；

1、HashMap在确定数组下标Index的时候，采用的是( length-1) & hash的方式，只有当length为2的指数幂的时候才能较均匀的分布元素。所以HashMap规定了其容量必须是2的n次方；
2、由于HashMap规定了其容量是2的n次方，所以我们采用位运算<<来控制HashMap的大小。使用位运算同时还提高了Java的处理速度。HashMap内部由Entry[]数组构成，Java的数组下标是由Int表示的。所以对于HashMap来说其最大的容量应该是不超过int最大值的一个2的指数幂，而最接近int最大值的2的指数幂用位运算符表示就是 1 << 30；
3、初始容量问题，可以赋值容量小于16！