HashMap底层详解

1、HashMap底层存储原理详解

HashMap存储原理
☆获取到传过来的key，调用hash算法获取到hash值
☆获取到hash值之后调用indexFor方法，通过获取到的hash值以及数组的长度算出数组的下标 (把哈希值和数组容量转换为二进，再在数组容量范围内与哈希值进行一次与运算，同为1则1，不然则为0，得出数组的下标值，这样可以保证计算出的数组下标不会大于当前数组容量)把传过来的key和value存到该数组下标当中。
☆如该数组下标下以及有值了，则使用链表，jdk7是把新增元素添加到头部节点 jdk8则添加到尾部节点。

HashMap存储流程
前面寻址算法都是一样的，根据key的hashcode经过高低位异或之后的值，再按位与 &(table.lingth - 1),得到一个数组下标，然后根据这个数组下标内的状况，状况不同，然后情况也不同，大概分为了4种状态：
( 1.)第一种就是数组下标下内容为空：
这种情况没什么好说的，为空据直接占有这个slot槽位就好了，然后把当前.put方法传进来的key和value包装成一个node对象,放到这个slot中就好了。

( 2.)第二种情况就是数组下标下内容不为空，但它引用的node还没有链化：
这种情况下先要对比一下这个node对象的key与当前put对象的key是否完全.相等，如果完全相等的情况下，就行进行replace操作，把之前的槽位中node.下的value替换成新的value就可以了，否则的话这个put操作就是一个正儿.八经的hash冲突,这种情况在slot槽位后面追加一个node就可以了,用尾插法 ( 前面讲过，jdk7是把新增元素添加到头部节点，而jdk8则添加到尾部节点)。

( 3.)第三种就是该数组下标下内容已经被链化了：
这种情况和第二种情况处理很相似，首先也是迭代查找node，看看链表上中元素的key，与当前传过来的key是否完全一致，如果完全一致的话还是repleace操作，用put过来的新value替换掉之前node中的value，否则的话就是一致迭代到链表尾节点也没有匹配到完全一致的node，就和之前的一样，把put进来数据包装成node追加到链表的尾部，再检查一下当前链表的长度，有没有达到树化阈值，如果达到了阈值就调用一个树化方法，树化操作都是在这个方法里完成的。

( 4.)第四种情况就是冲突很严重的情况下，这个链表已经转化成红黑树了：
红黑树就比较复杂要将清楚这个红黑树还得从TreeNode说起 TreeNode继承了Node结构，在Node基础上加了几个字段，分别是指向父节点parent字段，指向左子节点left字段，指向右子节点right字段，还有一个表示颜色的red字段，这就是TreeNode的基本结构，然后红黑树的插入操作，首先找到一个合适的插入点，就是找到插入节点的父节点，然后红黑树它又满足二叉树的所有特性，所以找这个父节点的操作和二叉树排序是完全一致的，然后说一下这个二叉树排序，其实就是二分查找算法映射出来的结构，就是一个倒立的二叉树，然后每个节点都可以有自己的子节点，本且左节点小于但前节点，右节点大于当前节点，然后每次向下查找一层就能那个排除掉一半的数据，查找效率非常的高效，当查找的过程中也是分情况的。

☆首先第一种情况就是一直向下探测，直到查询到左子树或者右子树位null，说明整个树中，并没有发现node链表中的key与当前put key一致的TreeNode,那此时探测节点就是插入父节点的所在了，然后就是判断插入节点的hash值和父节点的hash值大小决定插入到父节点的左子树还是右子树。当然插入会打破平衡，还需要一个红黑树的平衡算法保持平衡。

☆其次第二种情况就是根节点在向下探测过程中发现TreeNode中key与当前put的key完全一致，然后就也是一次repleace操作，替换value。

2、HashMap哈希算法详解

hash再运算

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

计算桶位置

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {...代码省略// 计算桶位置if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);...代码省略

☆ 代码讲解
key的hash值做再运算,这里采用的是hash值高16位与低16位的异或运算，有两个问题，
1-为什么要高位与低位进行运算，
2-为什么用异或进行运算，而不用&或者|呢
原因:因为之后的计算hash桶位置的时候，用的算法是除余，并且数组的长度始终是2的n次方，所以桶位置的运算用2的n次方-1做与运算即可，但是这样hash高位的特征就丧失了，为了将高位特征也加入到hash计算中，所以这么操作。
那为什么要用 ^ 运算，而不用&或者|呢？因为使用&，每位数据将会有1/4的概率变为0，使用|每位数据将会有3/4的概率变为1，只有使用 ^ 每位的数据变成0或者1的概率都是1/2，所以使用^。

3、哈希冲突产生的原因详解

☆哈希冲突的产生原因
哈希是通过对数据进行再压缩，提高效率的一种解决方法。但由于通过哈希函数产生的哈希值是有限的，而数据可能比较多，导致经过哈希函数处理后仍然有不同的数据对应相同的值。这时候就产生了哈希冲突。

☆产生哈希冲突的影响因素
装填因子（装填因子=数据总数 / 哈希表长）、哈希函数、处理冲突的方法

☆解决哈希冲突的四种方法
1.开放地址方法
（1）线性探测：按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。　
（2）再平方探测：按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。
（3）伪随机探测：按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。
2.链式地址法（HashMap的哈希冲突解决方法）
对于相同的值，使用链表进行连接。使用数组存储每一个链表。
优点：
（1）拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
（2）由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
（3）开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
（4）在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。
缺点：
指针占用较大空间时，会造成空间浪费，若空间用于增大散列表规模进而提高开放地址法的效率。

3.建立公共溢出区
建立公共溢出区存储所有哈希冲突的数据。
4.再哈希法
对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。

4、HashMap底层存储数据结构详解

JDK7与JDK8及以后的HashMap结构与存储原理有所不同：
Jdk1.7：数组 + 链表 ( 当数组下标相同，则会在该下标下使用链表)
Jdk1.8：数组 + 链表 + 红黑树 (预值为8 如果链表长度 >=8则会把链表变成红黑树 )
Jdk1.7中链表新元素添加到链表的头结点,先加到链表的头节点,再移到数组下标位置
Jdk1.8中链表新元素添加到链表的尾结点
(数组通过下标索引查询，所以查询效率非常高，链表只能挨个遍历，效率非常低。jdk1.8及以
上版本引入了红黑树，当链表的长度大于或等于8的时候则会把链表变成红黑树，以提高查询效率)

5、HashMap在JDK8新增的红黑树详解

其实主要就是为了解决jdk1.8以前hash冲突所导致的链化严重的问题，因为链表结构的查询效率是非常低的，他不像数组，能通过索引快速找到想要的值，链表只能挨个遍历，当hash冲突非常严重的时候，链表过长的情况下，就会严重影响查询性能，本身散列列表最理想的查询效率为O(1)，当时链化后链化特别严重，他就会导致查询退化为O(n)为了解决这个问题所以jdk8中的HashMap添加了红黑树来解决这个问题，当链表长度>=8的时候链表就会变成红黑树，红黑树其实就是一颗特殊的二叉排序树嘛，这个时间复杂…反正就是要比列表强很多

6、头插入和尾插法的优缺点是什么?

尾插法：优点不需要遍历一次链表再进行数据插入，

7、手写实现HashMap并性能测试

HashMap = 数组 + 链表;
哈希表也可称为哈希映射。
设计哈希表的目的：快速查找其实我这个类HashMap的实现方法并不复杂，其内部是一个容量很大的数组，通过在数组每个元素内挂一个链表来存储和查找数据的。

我们看一下官方HashMap的用法（Student类自备）：

HashMap map = new HashMap<>(); 
map.put("1001", new Student(20191001, "张三")); 
Student s = map.get("1001"); 
System.out.println(s);

在这里插入图片描述

Student[] a = new Student[100000000];
a[20191001] = ...
a[20191002] = ...

在这里插入图片描述

Student[] a = new Student[10000];
a[1001]=...
a[1002]=...

这样，我们把数组设置10000的容量，通过数组下标就可以快速的查找到对应的数据。

具体代码实现：

public class MyHashMap
{ //创建一个容量为10000的数组 private Object[] buffer = new Object[10000]; //添加数据 public void put(Object key, Object value) { int index = key2index(key); buffer[index] = value;} public Object get(Object key){int index = key2index(key); return buffer[index];}//映射key值（数组下标），将Key映射为数组下标Indexprivate int key2index(Object key){ //除10000取余return (Integer)key % 10000;}
}

关键步骤：Key2Index方法，将Key映射为数组下标Index
测试一下：

MyHashMap map = new MyHashMap(); 
map.put(20191001, new Student(20191001, "张三"));
map.put(20191002, new Student(20191002, "李四"));
map.put(20191003, new Student(20191003, "麻五"));Student s = (Student)map.get(20191001); System.out.println("结果：" + s);

在这里插入图片描述

map.put(20201001, new Student(20201001, "小新"));
Student s = (Student)map.get(20191001); 
System.out.println("结果：" + s);

在这里插入图片描述

public class MyHashMap
{//每个链表的节点public static class Node{Object key;Object value;Node next;} //创建一个容量为10000的数组 private Node[] buffer = new Node[10000]; //这里使用有头链表实现 public MyHashMap() { //给所有数组元素添加一个头节点（空） for(int i = 0; i < buffer.length; i ++) buffer[i] = new Node(); } //添加数据 public void put(Object key, Object value) { int index = key2index(key); //创建一个链表，将键值对赋值 Node node = new Node();node.key = key;node.value = value; //遍历节点找到尾节点，并将新节点附加Node tail = buffer[index];while(tail.next != null) tail = tail.next; tail.next = node;} public Object get(Object key){int index = key2index(key); Node tail = buffer[index];//遍历节点找到key值所对应的节点，并返回while(tail.next != null){ if(tail.next.key.equals(key)) return tail.next.value; tail = tail.next;} return null;}//映射key值（数组下标），将Key映射为数组下标Indexprivate int key2index(Object key){ //除10000取余return (Integer)key % 10000;}
}

实现按名字检索（字符串查找）

此时，Key应该是字符串类型，我们需要把字符串映射为0-10000的 Index

解决方案：

取得字符串首字母，将其转化为整数，例如：“张三”取“首字母z”映射为109（参照ASCII码）所有字母”z“开头的都挂在buffer[109]位置的链表下
在这里插入图片描述
代码实现：改造key2index方法

 //映射key值（数组下标），将Key映射为数组下标Indexprivate int key2index(Object key){//Key若是数字类型if(key instanceof Integer || key instanceof Double){ return (Integer)key % 10000;}//Key若为字符串else if(key instanceof String){ //取首字母转成字符 char n = ((String) key).charAt(0); int p = n; return p % 10000;}//直接取对象的HashCode(哈希码)return key.hashCode() % 10000;}

HashCode，Object下的方法，默认返回对象的内存地址（整型）

测试：

map.put("zhangsan", new Student(20191001, "张三"));
map.put("zhangsi", new Student(20191002, "张四"));Student s = (Student)map.get("zhangsi"); System.out.println("结果：" + s);

在这里插入图片描述

至此，HashMap的设计基本完成。
最后，再加上泛型的处理就OK啦！
上最终代码

public class MyHashMap
{//节点public static class Node{Object key;Object value;Node next;} //数组缓冲区private Node[] buffer = new Node[10000]; //初始化每个头节点public MyHashMap(){for(int i = 0; i < buffer.length; i ++) buffer[i] = new Node();} /*添加数据* */public void put(K key, V value){int index = key2index(key); Node node = new Node();node.key = key;node.value = value; Node tail = buffer[index];while(tail.next != null) tail = tail.next; tail.next = node;} /*取得数据* */public V get(K key){int index = key2index(key); Node tail = buffer[index];while(tail.next != null){ if(tail.next.key.equals(key)) return (V)tail.next.value; tail = tail.next;} return null;} /*删除* */public void remove(K key){int index = key2index(key); Node tail = buffer[index];while(tail.next != null){ if(tail.next.key.equals(key)) tail.next = tail.next.next; else tail = tail.next;}} //哈希函数public Integer key2index(K key){//Key若是数字类型if(key instanceof Integer || key instanceof Double){ return (Integer)key % 10000;}//Key若为字符串else if(key instanceof String){ //取首字母转成字符 char n = ((String) key).charAt(0); int p = n; return p % 10000;}//直接取对象的HashCode(哈希码)return key.hashCode() % 10000;}
}

测试：

MyHashMap map = new MyHashMap<>(); 
map.put("1001", new Student(20191001, "张三")); 
Student s = map.get("1001"); 
System.out.println(s);

在这里插入图片描述
Key和Value可以是任意类型。这就实现了JDK中HashMap的基本功能了。
————————————————
版权声明：本文为CSDN博主「总是幸福的老豌豆」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_32370913/article/details/119821581