hashMap 的存储结构
HashMap 的存储结构，是通过用数组＋链表实现。当 HashMap 添加一个元素 add(k,v)时，k、v 被封装为一个 entity 对象，jdk 8 中叫 node 节点对象。该对象会被存放到数组中，key 通过 hash 计算出所在数组唯一位置，如果该位置已被占用（hash 冲突），则用链表方式继续存储。
当数组容量使用到指定阈值时，会触发数组扩容；
当链表长度达到一定时，jdk 8 中，这个长度是 8 ，超过时，链表结构转为红黑树结构，以提高查询效率，当移除元素后长度小于 6 时，便又转回链接结构。
HashMap 添加元素时，判断是 key 是否已存在，主要通过 hash 值的对比，通过 equals 对比 key 内容的对比完成。
相关源码：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @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数组为空，或者长度为0，通过resize()初始化tab数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//hash所在的数组位置为空，则new Node节点
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断hash值相同 && （通过==对比 || 通过equals对比），对相同key重新赋值
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
如何保证 key 是唯一的
在 map 中，key 的比较，可以通过上述源码得知：
(
p.hash == hash
&&
((k = p.key) == key || (key != null && key.equals(k))
)
也就是通过 hashCode 值、==、eqauls 三个方法对比。
hashCode 方法对比
Object 类定义的 hashCode 方法：
hashCode 方法，是 java 中 Object 对象定义的 native 方法，native 方法是 java 应用调用底层 c++程序的入口，参考 Java中如何打印对象内存地址 一文可知，其是根据对象内存地址计算出的 int 类型的值。
/**
* @return a hash code value for this object.
* @see java.lang.Object#equals(java.lang.Object)
* @see java.lang.System#identityHashCode
*/
public native int hashCode();
并且，在不同对象中，对 hashCode 的复写，也是不同的。
String 类中，复写了 hashCode 方法，通过一定的算法，保证计算返回的 hash 值尽量不冲突，既然是尽量不冲突，那么这种计算就还是有一定冲突概率的。了解 String 的 hashCode 算法，推荐阅读：一文说透String的hashCode。以下是 jdk 8 中，hashCode 方法的部分注释：
Returns a hash code for this string. The hash code for a String object is computed as s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
HashMap 中，对 hashCode 的复写，就简单的多：
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
/**
* Objects 的hashCode方法，实际上丢回给了Object方法。
* Returns the hash code of a non-{@code null} argument and 0 for
* a {@code null} argument.
*
* @param o an object
* @return the hash code of a non-{@code null} argument and 0 for
* a {@code null} argument
* @see Object#hashCode
*/
public static int hashCode(Object o) {
return o != null ? o.hashCode() : 0;
}
直接调用了 k/v 所属的各自类型的 hashCode 方法，将皮球踢回去了。
双等号== 对比
在 8 大基础类型中，== 对比的是类型的值，而在对象中，对比的是对象引用的内存地址。
例如：
public static void main(String[] args) {
Integer a = 1;
Integer b = 1;
System.out.println("a:" + a);
System.out.println("b:" + b);
System.out.println("ab:" + (a == b));
Integer c = new Integer(1);
System.out.println("c:" + c);
System.out.println("ac:" + (a == c));
}
//输出的结果是
a:1
b:1
ab:true
c:1
ac:false
延伸：为什么 ab 是相同的呢？gpt 给的答案：
Integer a = 1 Integer b = 1，为什么 a、b 的对象地址是一样的
在 Java 中，对于整型数据的包装类 Integer，Java 提供了一个 Integer 对象缓存池，这个缓存池中缓存了一个固定范围的整数对象 (-128 到 127)。当我们使用自动装箱或者调用 valueOf() 方法创建一个整型包装类对象时，会先检查该对象是否在缓存池中存在，如果存在，则直接返回缓存池中的对象，而不是创建一个新的对象。
所以，当我们写下 Integer a = 1; Integer b = 1; 这两行代码时，由于 1 在缓存池中已经存在，所以 a 和 b 引用的是同一个对象，即它们的对象地址是一样的。
但是需要注意的是，如果超出了缓存池的范围，比如 Integer a = 128; Integer b = 128;，则 a 和 b 引用的将不再是同一个对象，而是分别创建了两个新的对象。这是因为超出了缓存池的范围，Java 会重新创建一个对象来表示该值。
equals 方法对比
java 对象的中的老大哥 Object 中，equals 方法实际上是调用了 == 对比。源码如下：
public boolean equals(Object obj) {
return (this == obj);
}
而在 String 类中，复写了 equals：
/**
* Compares this string to the specified object. The result is {@code
* true} if and only if the argument is not {@code null} and is a {@code
* String} object that represents the same sequence of characters as this
* object.
*
* @param anObject
* The object to compare this {@code String} against
*
* @return {@code true} if the given object represents a {@code String}
* equivalent to this string, {@code false} otherwise
*
* @see #compareTo(String)
* @see #equalsIgnoreCase(String)
*/
public boolean equals(Object anObject) {
//先用==判断，如果对象引用的地址相同，那结果一定相同
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = value.length;
//String类型，并且长度相同，遍历字符串的每个字符是否相同
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}
既然 hashCode 可以通过计算每个属性的 hash 值，从而在属性维度对比两个对象是否相同，为什么还需要再通过 equals 方法对比呢？
Gpt 给了答案：
虽然 hashCode() 方法可以根据对象的属性计算出一个哈希码，但是哈希码并不是绝对唯一的，不同的对象可能会产生相同的哈希码（发生哈希冲突）。因此，仅仅通过比较哈希码是不足以确定两个对象是否相等的。
equals() 方法的作用是在逻辑上比较两个对象是否相等。它是 Object 类中的一个方法，但是在许多类中都会被重写来实现自定义的相等性判断逻辑。
在重写 equals() 方法时，通常会比较对象的属性值是否相等，以确定对象是否相等。这样可以更加精确地判断对象的相等性，不仅仅局限于哈希码。
当我们使用集合类（如 HashSet 或 HashMap）时，它们内部使用了 equals() 和 hashCode() 方法来判断是否已经包含某个对象或者查找某个对象的位置。如果只重写了 hashCode() 方法而没有重写 equals() 方法，可能会导致集合类无法正确地判断对象是否相等，从而引发一些意想不到的问题。
因此，为了保证对象的相等性判断的正确性，一般需要同时重写 equals() 和 hashCode() 方法。equals() 方法用于逻辑上的相等性判断，而 hashCode() 方法则用于高效地定位对象。
Map 中的 key 怎么找到在数组的位置
hashMap 的 key 通过 hash 计算后，如何找到在数组的位置呢？
未完待续...
延伸：
数组的扩容机制
红黑树数据结构简介
资料参考：
https://blog.csdn.net/sanmi8276/article/details/113839351
