数据结构——hash（hashmap源码探究）

hash是什么？

hash也称为散列，就是把任意长度的输入，通过散列算法，变成固定长度的输出，这个输出值就是散列值。

举例来说明一下什么是hash：

假设我们要把1~12存入到一个大小是5的hash表中，我们就是用index=number%5的公式去计算索引存入数据

hash是一个神奇的数据结构，可以以接近O(1)的时间复杂度去进行查询

但是很快我们就会发现一个问题，就是相同的余数的值储存在同一个索引下，这样就会造成一个问题，比如我查询8是否存储在结构中，我们能直接访问array[3]这个位置，里面存储8，会返回给我们的一个true，然后如果我们想要查询13是否存在该结构中，还是会去array[3]中查找，发现里面没存有数据13，返回false

如何解决hash冲突？

首先，先来说一下哈希冲突，哈希冲突（Hash Collision）是指在使用哈希表存储数据时，两个或多个不同的键（Key）被哈希函数映射到同一个位置的情况。这种情况会导致数据的存储和查找变得复杂，因此需要采取一些措施来解决哈希冲突。

解决hash冲突的方法：

1.拉链法:

链地址法是一种处理哈希冲突的方法，它是将所有散列到同一个地址的数据项存储在一个单链表中。这样，当查找某个数据项时，只需要在对应的链表中进行搜索即可。例如，HashMap 在解决存储对象存在 hash 冲突的问题时，采用的就是链地址法，将相同 hash 值的对象以链表的形式进行存储。

2.再hash法

在发生冲突的时候，再用另一个哈希函数算出哈希值，直到算出的哈希值不同为止。

3.线性探测

就是发生hash冲突时，往后面继续去找空的地方，找到后把冲突的值放到空的散列值的里面。

hashmap源码

Ctrl+鼠标左键点进去

先来看一下hash这个方法

定义了一个h，如果key==null那么就返回0作为hash值，如果不等于null，那么首先把h无符号右移16位相当于保留了原哈希码的高16位，并将它们放在低16位的位置（同时丢弃了原始的低16位）。然后，这个右移后的值与原始的哈希码进行异或操作。异或操作的一个特性是，任何数与0异或都保持不变，而与自身异或则结果为0。这种变换有助于将哈希码的不同部分混合在一起，从而增加哈希值的分布范围，减少哈希冲突的可能性。这个称之为一次扰动，每运算一次就算作一次扰动，就是为了让hash码的每一位都参与运算并减少冲突。

hash这个函数就是给一个对象经过一个算法处理返回一串数字作为hash码。

然后我们回过来看putVal函数

首先是判断table是否为空；如果是空的话，先进行一个初始化

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)//如果数组中这个位置是空的，那么直接创建一个新的点把key，hash，value装进去tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k)))) //先判断我们取得的hash值和p的这个hash值是不是一样如果一样再开始判定key是不是一样，判断key相等的时候先判断两个key==，再判断两个key的值是不是一样，如果一样就令e=pe = p;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);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}//一旦发现有相等的就直接跳出循环if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}//如果e不是空的，那就直接把这个值赋给老的，就是说当两次put操作的key相等的时候后面put的值会覆盖前面put的值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}

1.如果hashmap是空的话，也就是它内部的table数组是null，在添加第一个元素的时候会进行初始化，为table分配内存空间，设置初始容量为16，和加载因子0.75

2.对要插入的键，计算hash值，拿到hash值之后使用hash值得与table数组的长度来确定该键的存储位置，万一出现了产生相同的hash值的情况下，hashmap采用链表或红黑树（链表大于8的时候用红黑树）。如果该桶中没有元素就直接创建一个新的结点，如果不是空就遍历链表或者红黑树，查找是否存在相同的键，存在相同的键就用新的键代替旧的键，如果不存在就将新的结点添加到末尾，（红黑树就按红黑树规则插入）