Hashmap数据结构
hashMap是一种基于数组和链表（或红黑树）的数据结构，它可以通过一个哈希函数将键映射到数组的一个位置，并在该位置存储一个键值对的节点。hashMap的put方法主要是计算键的哈希值和索引，然后在相应的位置插入或更新节点，如果节点数超过阈值，就会进行扩容或树化。hashMap的get方法主要是根据键的哈希值和索引，找到对应的位置，然后遍历链表或红黑树，返回匹配的值。
Node和TreeNode节点
如果是链表的Map用Node节点，如果是红黑树Map用TreeNode节点。
put源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put方法通过hash函数计算key对应的哈希值，hash函数源码如下：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这里可以看出HashMap是允许key为null，当是null的时候key就是0。
不为null利用hash异或公式得到一个散列的值。hashCode能懂，就是求key的hash值，为什么要异或？
具体来说，h = key.hashCode()是将键的hashCode()方法返回的整数值赋给h，h >>> 16是将h无符号右移16位，也就是将高16位移到低16位，高位补0。^是异或运算符，它对两个操作数的每一位进行逻辑运算，相同为0，不同为1。所以，h ^ (h >>> 16)就是将h的高16位和低16位按位异或，得到一个新的整数值。
对于^运算
- 0 ^ 0 = 0
- 1 ^ 0 = 1
- 0 ^ 1 = 1
- 1 ^ 1 = 0
对于“|”，或运算：
- 0 | 0 = 0
- 0 | 1 = 1
- 1 | 0 = 1
- 1 | 1 = 1
对于"&"，与运算：
- 0 & 0 = 0
- 0 & 1 = 0
- 1 & 0 = 0
- 1 & 1 = 1
为什么要无符号右移16位
假如一个key是：
11100000 00000000 00000000 00000000
数组长度是8:
00000000 00000000 00000000 00001000
那么再运算下坐标的时候i = (n - 1) & hash，如果不把高位拿到后边产生如下结果
11100000 00000000 00000000 00000000
00000000 00000000 00000000 00000111
就会导致永远都是7
为了防止高位有值，低位没有值，所以会将
这样做的好处是，如果键的hashCode()方法返回的值只在高16位或低16位有差异，那么经过这个表达式后，这种差异就会传播到低16位，从而增加了低16位的随机性和均匀性。这对于hashMap来说很重要，因为它在计算键在数组中的索引时，只用到了低n位（n是数组长度的二进制位数），如果低n位相同，就会导致哈希冲突。通过这个表达式，可以让低n位更加分散，从而提高hashMap的性能，提高离散性。
举个例子：
int a = 2182082319;
a的二进制表示形式是（32位）：
10000010 ， 00001111 ，11101111 ， 00001111
然后，我们无符号右移16位：
00000000 ，00000000，10000010 ， 00001111
最后，我们做异或操作：
10000010 ， 00001111 ，01101101 ， 00001111
所以，这个过程的确可以提高低16位的随机性和均匀性，减少哈希冲突，并提高HashMap的性能。
putVal插入元素
得到key对应的哈希值后，再调用putVal(hash(key), key, value, false, true)方法插入元素：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果数组(哈希表)为null或者长度为0，则进行数组初始化操作
if ((tab = table) == null || (n = tab.length) == 0)
//resize()用于调整hash表的大小，也就是调整table[]的大小。
n = (tab = resize()).length;
// 根据key的哈希值计算出数据插入数组的下标位置，公式为(n-1)&hash
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果该下标位置还没有元素，则直接创建Node对象，并插入
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 如果目标位置key已经存在，则直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果目标位置key不存在，并且节点为红黑树，则插入红黑树中
else if (p instanceof TreeNode)
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);
// 如果链表长度大于等于TREEIFY_THRESHOLD 8，则考虑转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 转换为红黑树操作，内部还会判断数组长度是否小于MIN_TREEIFY_CAPACITY，如果是的话不转换
treeifyBin(tab, hash);
break;
}
// 如果链表中已经存在该key的话，直接覆盖替换
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
// 返回被替换的值
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 模数递增
++modCount;
// 当键值对个数大于等于扩容阈值的时候，进行扩容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
以上代码解释:
1、如果table[]数组为空，则进行resize()，进行调整哈希表table[]的大小。
2、求出下坐标并且判断再table[]是否有值。没有值直接将自己的节点封装成Node赋值进去。
i = (n - 1) & hash这里用到了且，求出来的值一定是小于等于n - 1的
3、如果table[]下坐标有值。
3.1、如果key相同，则将value替换。
3.2、判断节点是不是TreeNode，如果是treeNode，调用红黑树的插入。
红黑树是一种自平衡的二叉搜索树，它有以下五个性质：
每个节点是红色或黑色的。
根节点是黑色的。
所有的叶子节点（空节点）是黑色的。
如果一个节点是红色的，那么它的两个子节点都是黑色的。
从任意一个节点到其后代叶子节点的每条路径都包含相同数目的黑色节点。
在红黑树中插入一个新节点时，需要遵循以下规则：
如果树为空，那么插入新节点作为根节点，并将其颜色设为黑色。
如果树不为空，那么插入新节点作为一个叶子节点，并将其颜色设为红色。
如果新节点的父节点是黑色的，那么不需要做任何改变。
如果新节点的父节点是红色的，那么需要根据新节点的叔叔节点（父节点的兄弟节点）的颜色进行不同的操作：
如果叔叔节点是红色的，那么将父节点和叔叔节点的颜色设为黑色，将祖父节点（父节点的父节点）的颜色设为红色，并将新节点指向祖父节点，重复步骤3和4。
如果叔叔节点是黑色或空的，那么根据新节点、父节点和祖父节点之间的位置关系，有四种情况：
左左情况：父节点是祖父节点的左子节点，新节点是父节点的左子节点。这时需要对祖父节点进行右旋，并交换父节点和祖父节点的颜色。
左右情况：父节点是祖父节点的左子节点，新节点是父节点的右子节点。这时需要对父节点进行左旋，然后转化为左左情况。
右右情况：父节点是祖父节点的右子节点，新节点是父节点的右子节点。这时需要对祖父节点进行左旋，并交换父节点和祖父节点的颜色。
右左情况：父节点是祖父节点的右子节点，新节点是父节点的左子节点。这时需要对父节 点进行右旋，然后转化为右右情况。
其实只要记住是一个自平衡二叉树，之前看左神说的，为什么要写红黑树而不写二叉平衡树，可能的原因是装 .，看的高深一点，没别的了，你写个平衡树二叉树不好吗，写这么复杂，看吧最后这部分源码的改。笑死了哈哈哈。
3.3、如果不是树节点，则循环链表，从头开始循环，如果查过8，则将链表转换为红黑树，如果每有超过则节点赋值到最后。这里会有个问题，因为再插入的时候不是原子操作。如果这个时候有另外一个线程把链表改成二叉树，那么这个节点可能就找不到了。
扩容
再put的最后：
if (++size > threshold)
resize();
- size：这个成员变量表示 HashMap 当前已存储的键值对的数量。这里size是map里边的数量，由于不是原子，所以，有可能mapi边的值大于size。
- threshold：这个成员变量表示 HashMap 的阈值，当 HashMap 中存储的键值对数量超过这个阈值时，HashMap 会自动增大容量（即进行 rehashing）。默认情况下，threshold 是 HashMap 容量数组的长度的 0.75 倍（因为 HashMap 的加载因子默认为 0.75），你可以在 HashMap 的构造函数中指定其它的加载因子。
当你调用 put 方法添加键值对时，size 会增加。如果 size 超过了 threshold，则调用 resize 方法来扩容和重新哈希 HashMap。这个过程是在 HashMap 的内部自动完成的，你不需要手动给 size 和 threshold 赋值。
为了避免频繁扩容，再初始化hashMap的时候设置好hashMsp的容量。
为什么扩容是2的倍数
举个例子来看，有两个key分别是：
00000000 ， 00000000，00000000， 00001101
00000000 ， 00000000，00000000， 01001101
数组的长度是8然后-1是：
00000000 ， 00000000，00000000， 00000111
再数组*2-1也就是扩容完之后：
00000000 ， 00000000，00000000， 00001111
运算有可能仍然是原来index，变化不大。如果扩容乘以3之后-1
00000000, 00000000, 00000000, 00010111
这中间有个0，10111，对比原来的1111，如果每次扩容的时候，&运算变化很大的情况就导致，原来的node一直在数组中换下坐标。
为什么是扩容因子是0.75倍？
HashMap的查找效率依赖于哈希冲突的程度。如果哈希冲突太多，每个桶(bucket)里的元素就会增多，这样查找时就需要遍历更多的元素。在极端情况下，如果所有的元素都在同一个桶里，那么HashMap就退化成了链表，查找效率会显著下降。
加载因子较低意味着HashMap会更早地进行扩容，这会使得元素更分散，减少哈希冲突，提高查找效率。但是过低的加载因子会导致内存浪费，因为很多桶都是空的。
加载因子的选择涉及到时间和空间效率的权衡：
- 如果加载因子太高，例如1.0或接近1.0，那么HashMap中的哈希冲突会更频繁，这会导致查找效率下降，因为需要经常遍历链表（或者在Java 8中可能是红黑树）。
- 如果加载因子太低，例如0.1或更低，那么虽然哈希冲突会减少，查找效率提高，但是HashMap占用的内存空间会大幅度增加，因为很多槽位(bucket)都是空的。
因此，我们需要在空间和时间之间找到一个平衡点。经过实验和实践，0.75是被发现的一个不错的折中方案，它在空间和时间效率之间取得了一个较好的平衡。这也是为什么Java中的HashMap默认加载因子是0.75。
扩容的为什么要尾插法？
扩容会把原来的hashMap数组扩容到原来的两倍，并且里边所有的node都需要重新插入一次。重新插入不会转换成为红黑树，只有再put的时候会去判断。
举个例子来解释：有两个线程分别是t1、t2。两个节点分别是n1、n2。其中n1->n2。
扩容后，会将原来的桶的链表循环插入新的链表。一定要注意是循环，中止条件是next不为null。
线程1执行，将n1放入到新数组中。
线程2执行，将n1放到新数组中。
线程1执行，将n1的next指向null，并将n2插入数组的头不，n2next指向n1。
好了产生循环了，n2->1
线程2执行，去拿n2的时候，这时候n2已经指向了n1，产生了循环，它next永远不是null，所以线程2的循环不会停止。
尾插法不会导致死循环，主要是因为当使用尾插法时，新节点总是被插入到链表的尾部。所以不会出现一个节点的next指向自己之前的节点，即不会形成一个环。