1.hash
哈希算法也叫散列，就是把任意长度的key值通过散列算法变成固定长度的key值的地址，我们通过这个地址进行访问数据结构。
它通过把关键码值映射到表中的一个位置来访问记录，以加快查找的速度。
映射的函数叫做散列函数，存放记录的数组叫做散列表。
public static void main(String[] args) {
//Map<String,String> map = new HashMap();
Map<Integer, Integer> map = new HashMap<>(12);
map.put(1,1);
map.put(2,2);
map.put(3,3);
map.put(4,4);
map.put(5,5);
map.put(6,6);
map.put(14,14);
map.keySet().forEach(DemoArraysList::put);
}
public static void put(Integer key){
// HashMap默认数组长度为16
System.out.printf("key:%s,hash值:%s,存储位置:%s\r\n",key,key.hashCode(),Math.abs(key.hashCode() % 6));
}
输出：
key:1,hash值:1,存储位置:1
key:2,hash值:2,存储位置:2
key:3,hash值:3,存储位置:3
key:4,hash值:4,存储位置:4
key:5,hash值:5,存储位置:5
key:6,hash值:6,存储位置:0
key:14,hash值:14,存储位置:2
1和14属于hash冲突，用链表存放
2.HashMap 技术实质
1.存储内容：key 、value
2.存储结构：数组、链表、红黑数（JDK8）
3.存储位置：数组下标
4.存储大小：数组长度
3.构造方法
3.1. 空参构造方法，0.75负载因子的赋值
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
3.2.初始化map容量
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
3.3.求2的n次方 >= initialCapacity
/**
* Returns a power of two size for the given target capacity.
*/
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;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float) s / loadFactor) + 1.0F;
int t = ((ft < (float) MAXIMUM_CAPACITY) ? (int) ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
} else if (s > threshold)
//扩容
resize();
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
static final int hash(Object key) {
/**
获取key的hash值
对象的hashcode值 ^(异或) 对象的hashcode值的高位（前16位）
目的：尽可能降低hash冲突，提高hashcode的随机性
*/
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
获取key的hash值
对象的hashcode值 ^(异或) 对象的hashcode值的高位（前16位）
目的：尽可能降低hash冲突，提高hashcode的随机性
3.4 HashMap的PUT操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K, V>[] tab;
Node<K, V> p;
int n, i;
//判断table数组是否为空或者长度为0
if ((tab = table) == null || (n = tab.length) == 0)
//为空 则初始化table
n = (tab = resize()).length;
//16 -1 = 15 & hash值 = i, 计算当前传入hash位置为i
// p = tab[i],p 为当前hash在table位置的值 p是否为空，表示当前hash值在table中没有元素（没有hash冲突）
//(n - 1) & hash 表示当前hash值在table中的位置
if ((p = tab[i = (n - 1) & hash]) == null)
//p 为空则表示当前位置没有值，newNode赋值赋值給tab[i]
tab[i] = newNode(hash, key, value, null);
else {//tab[i] 有值的情况， p为当前tab[i]的值，有hash冲突的情况
Node<K, V> e;//新建节点
K k;//k 为当前tab[i]的哇key值
//判断当前hash 和 当前位置的节点p 的key值与传入的key值是否相等，相等则e = p等于当前hash位置的值
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是树结构，红黑树如插入值， JDK1.8 = 红黑树优化方案
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
//链表结构 插入元素
for (int binCount = 0;; ++binCount) {
//判断p的下一个匀速是否为Null
if ((e = p.next) == null) {
//如果为空则插入到P对应链表的下一个元素
p.next = newNode(hash, key, value, null);
//判断阈值，查找的次数>=8次，则换换为红黑树（链表默认长度是8，大于8则需要转换为红黑树）
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为 红黑树
treeifyBin(tab, hash);
break;
}
//掺入的hash和key与p链表的下一个元素相等 ，当前链表包含要插入的key值 ，循环结束
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
//到一下个节点
p = e;
}
}
//判断插入的值是否存在hashmap中
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//修改次数
++modCount;
//判断当前数组是否大于阈值（默认16）
if (++size > threshold)
//扩容
resize();
afterNodeInsertion(evict);
return null;
}
3.5 Node转换为红黑树
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
int n, index; HashMap.Node<K,V> e;
//判断如果tab为空 或者 tab的长度小于 MIN_TREEIFY_CAPACITY（最小树容量64），则进行扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//满足树的容量，则转换为树
//如果当前hash对应的位置 有元素
else if ((e = tab[index = (n - 1) & hash]) != null) {
//重建树
TreeNode<K,V> hd = null, tl = null;
do {
//新建一个树节点p
HashMap.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);
//hd为重建树的根节点
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
4.HashMap中hash(Object key)的原理，为什么这样做?
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
4.1 h >>> 16 是什么，有什么用?
h是hashcode。h >>> 16是用来取出h的高16，(>>>是无符号右移) 如下展示：
0000 0100 1011 0011 1101 1111 1110 0001 >>> 16
0000 0000 0000 0000 0000 0100 1011 0011
4.2 为什么 h = key.hashCode()) 与 (h >>> 16) 异或
还要看一个方法indexFor，在jdk1.7中有indexFor(int h, int length)方法。jdk1.8里没有，但原理没变。下面看下1.7源码
1.8中用tab[(n - 1) & hash]代替但原理一样。
static int indexFor(int h, int length) {
return h & (length-1);
}
这个方法返回值就是数组下标。
但由于绝大多数情况下length一般都小于2^16即小于65536。所以return h & (length-1);结果始终是h的低16位与（length-1）进行&运算
例如1：为了方便验证，假设length为8。HashMap的默认初始容量为16
length = 8; （length-1） = 7；转换二进制为111；
假设一个key的 hashcode = 78897121 转换二进制：0000 0100 1011 0011 1101 1111 1110 0001，与（length-1）& 运算如下
0000 0100 1011 0011 1101 1111 1110 0001
&运算
0000 0000 0000 0000 0000 0000 0000 0111
0000 0000 0000 0000 0000 0000 0000 0001 （就是十进制1，所以下标为1）
上述运算实质是：001 与 111 & 运算。也就是哈希值的低三位与length与运算。如果让哈希值的低三位更加随机，那么&结果就更加随机。
如何让哈希值的低三位更加随机，那么就是让其与高位异或。
补充知识：
当length=8（1000）时 下标运算结果取决于哈希值的低三位
当length=16（10000）时 下标运算结果取决于哈希值的低四位
当length=32时（100000） 下标运算结果取决于哈希值的低五位
当length=2的N次方， 下标运算结果取决于哈希值的低N位。
4.3 原因总结
由于和（length-1）运算，length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列。
所以这样高16位是用不到的，如何让高16也参与运算呢。所以才有hash(Object key)方法。让他的hashCode()和自己的高16位^运算。所以(h >>> 16)得到他的高16位与hashCode()进行^运算。
4.4 为什么用^而不用&和|
因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念,所以用^。
这就是为什么有hash(Object key)的原因。
4.4.1 位异或运算（^）
运算规则是：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1。
4.4.2 位与运算符（&）
运算规则：两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。
4.4.3 位或运算符（|）
运算规则：两个数都转为二进制，然后从高位开始比较，两个数只要有一个为1则为1，否则就为0。
4.4.4.位非运算符（~）
运算规则：如果位为0，结果是1，如果位为1，结果是0.
比如：~37
在Java中，所有数据的表示方法都是以补码的形式表示，如果没有特殊说明，Java中的数据类型默认是int,int数据类型的长度是8位，一位是四个字节，就是32字节，32bit.
8转为二进制是100101.
补码后为： 00000000 00000000 00000000 00100101
取反为： 11111111 11111111 11111111 11011010
因为高位是1，所以原码为负数，负数的补码是其绝对值的原码取反，末尾再加1。
因此，我们可将这个二进制数的补码进行还原： 首先，末尾减1得反码：11111111 11111111 11111111 11011001 其次，将各位取反得原码：
00000000 00000000 00000000 00100110，此时二进制转原码为38
所以~37 = -38.
5.TREEIFY_THRESHOLD树化域名，默认为8，链表长度超过8则需要转换为经黑树
原文链接：https://blog.csdn.net/qq_42034205/article/details/90384772
