散列表 - 手动实现 哈希表（HashMap）
1.1 哈希表的介绍
- 散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)
- 存储原理
- 哈希函数
- 散列表在本质上也是一个数组
- 散列表的Key则是以字符串类型为主的
- 通过hash函数把Key和数组下标进行转换
- 作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值，就像数组生成了对应的整数下标，便于寻找对应hash关系的元素
- 哈希函数
操作
-
写操作（put）
- 写操作就是在散列表中插入新的键值对（在JDK中叫作Entry或Node）
- 第1步，通过哈希函数，把Key转化成数组下标
- 第2步，如果数组下标对应的位置没有元素，就把这个Entry填充到数组下标的位置
-
Hash冲突（碰撞）
-
由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的，这种情况，就叫作哈希冲突
-
解决哈希冲突的方法主要有两种：
-
开放寻址法
-
开放寻址法的原理是当一个Key通过哈希函数获得对应的数组下标已被占用时，就寻找下一个空档位置
-
在Java中，ThreadLocal所使用的就是开放寻址法
-
-
链表法
- 数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可，默认next指向null
- 数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可，默认next指向null
-
-
-
读操作（get）
- 读操作就是通过给定的Key，在散列表中查找对应的Value
- 第1步，通过哈希函数，把Key转化成数组下标
- 第2步，找到数组下标所对应的元素，如果key不正确，说明产生了hash冲突，则顺着头节点遍历该单链表，再根据key即可取值
-
Hash扩容（resize）
-
散列表是基于数组实现的，所以散列表需要扩容
-
当经过多次元素插入，散列表达到一定饱和度时，Key映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能都有很大影响
-
影响扩容的因素有两个
- Capacity：HashMap的当前长度
- LoadFactor：HashMap的负载因子（阈值），默认值为0.75f
-
1.2 手动实现哈希表（HashMap）
package com.lagou.hashMap.entity;
/**
* @author 云梦归遥
* @date 2022/5/13 11:25
* @description
*/
public class MyHashMap {
// 自己构建每一个元素是一个 链表节点
public class MyLink{
private String key; // 键
private String value; // 值
private MyLink link; // 指针域
public MyLink(String key, String value){
this.key = key;
this.value = value;
this.link = null;
}
public MyLink(String key, String value, MyLink node){
this.key = key;
this.value = value;
this.link = node;
}
}
// 操作链表（链地址法）
public class ListNode{
private MyLink head; // 头结点
// 添加节点
public void addNode(String key, String value){
if (head == null){
return;
}
// 新建节点
MyLink newLink = new MyLink(key, value);
MyLink temp = head;
// 添加新的节点到链表上使用 尾插法
while (true){
// 如果 key 相同，则进行更新值
if (temp.key.equals(key)){
temp.value = value;
}
if (temp.link == null){
break;
}
temp = temp.link; // 向后遍历
}
// 将新的节点更新到链表的尾部
temp.link = newLink;
}
// 查询 键所对应的值
public String getNodeValue(String key){
String result = "null";
if (head == null){
return result;
}
MyLink temp = head;
while (true){
// 匹配对应的 key，将结果返回
if (temp.key.equals(key)){
result = temp.value;
break;
}
if (temp.link == null){
break;
}
temp = temp.link;
}
return result;
}
}
private ListNode[] myHashMap = null;
private static final int HASHMAP_LENGTH = 8; // 设置默认数组长度
private int length = 0; // 记录实时的 HashMap 的长度
private static final float EXPANSION_FACTOR = 0.75F; // 扩容因子
public MyHashMap(){
this.myHashMap = new ListNode[HASHMAP_LENGTH];
}
public MyHashMap(int len){
this.myHashMap = new ListNode[len];
}
// 进行扩容
public void resize(){
// 首先进行扩容操作
MyHashMap newMyHashMap = new MyHashMap(myHashMap.length * 2);
for (int i = 0; i < this.myHashMap.length; i++){
ListNode listNode = this.myHashMap[i];
if (listNode == null){
continue;
} else {
MyLink temp = listNode.head;
newMyHashMap.put(temp.key, temp.value); // 对头节点进行重新计算位置
// 进行遍历 数组中每个节点 所连接的链表
while (true){
if (temp.link == null){
if(temp != listNode.head){
newMyHashMap.put(temp.key, temp.value); // 最后一个节点进行重新计算位置
}
break;
} else {
temp = temp.link;
newMyHashMap.put(temp.key, temp.value); // 非头结点，非尾节点的节点进行重新计算位置
}
}
}
}
myHashMap = newMyHashMap.myHashMap; // 更新 HashMap
}
// 向 HashMap 中添加元素
public void put(String key, String value){
if (length >= myHashMap.length * EXPANSION_FACTOR){
length = 0;
// 超过扩容因子，进行 HashMap 的扩容
// =======================================================
// 首先进行扩容操作
MyHashMap newMyHashMap = new MyHashMap(myHashMap.length * 2);
for (int i = 0; i < myHashMap.length; i++){
ListNode listNode = myHashMap[i];
if (listNode == null){
continue;
} else {
MyLink temp = listNode.head;
newMyHashMap.put(temp.key, temp.value); // 对头节点进行重新计算位置
// 进行遍历 数组中每个节点 所连接的链表
while (true){
if (temp.link == null){
if(temp != listNode.head){
newMyHashMap.put(temp.key, temp.value); // 最后一个节点进行重新计算位置
}
break;
} else {
temp = temp.link;
newMyHashMap.put(temp.key, temp.value); // 非头结点，非尾节点的节点进行重新计算位置
}
}
}
}
myHashMap = newMyHashMap.myHashMap; // 更新 HashMap
// =======================================================
System.out.println("HashMap 进行扩容成功");
}
int index = Math.abs(key.hashCode()) % myHashMap.length;
ListNode arrayListNode = myHashMap[index]; // 这是哈希函数对应索引上的元素
if (arrayListNode == null){
// 索引对应位置上没有元素
ListNode newListNode = new ListNode(); // 构建新节点
MyLink headLink = new MyLink(key, value); // 没有头节点，创建头结点
newListNode.head = headLink; // 更新头节点
myHashMap[index] = newListNode; // 更新 hashMap 中的元素
length++;
} else {
// 索引对应位置上已经存在元素，直接想向链表上添加元素
arrayListNode.addNode(key, value);
}
//length++;
}
// 查询值
public String get(String key){
String result = "null";
int index = Math.abs(key.hashCode()) % myHashMap.length;
ListNode arrayListNode = myHashMap[index]; // 这是哈希函数对应索引上的元素
if (arrayListNode.head == null){
return result;
} else {
MyLink temp = arrayListNode.head.link;
while (true){
// 匹配键，更新结果
if (temp.value.equals(key)){
result = temp.value;
break;
}
if (temp.link == null){
break;
}
temp = temp.link;
}
}
return result;
}
// 展示全部
public String select(){
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("【HashMap】\n");
for (int i = 0; i < myHashMap.length; i++){
ListNode listNode = myHashMap[i];
if (listNode == null){
stringBuilder.append("【哈希码值：null】\n");
} else {
stringBuilder.append("【哈希码值：" + listNode.head.key.hashCode() + "】");
MyLink temp = listNode.head;
// 进行遍历 数组中每个节点 所连接的链表
while (true){
if (temp.link == null){
stringBuilder.append(temp.value + "\n");
break;
} else {
stringBuilder.append(temp.value + " => ");
temp = temp.link;
}
}
}
}
return stringBuilder.toString();
}
}
1.3 进行测试
package com.lagou.hashMap.test;
import com.lagou.hashMap.entity.MyHashMap;
/**
* @author 云梦归遥
* @date 2022/5/13 12:50
* @description
*/
public class MyHashMapTest {
public static void main(String[] args) {
MyHashMap myHashMap = new MyHashMap(10);
for (int i = 1; i <= 20; i++){
myHashMap.put(i + "", i + "");
}
System.out.println(myHashMap.select());
}
}
1.4 哈希表的总结
-
时间复杂度
- 写操作： O(1) + O(m) = O(m) ，m为单链元素个数
- 读操作：O(1) + O(m) ，m为单链元素个数
- Hash冲突写单链表：O(m)
- Hash扩容：O(n) ，n是数组元素个数 rehash
- Hash冲突读单链表：O(m) ，m为单链元素个数
-
优缺点
- 优点：读写快
- 缺点：哈希表中的元素是没有被排序的、Hash冲突、扩容 重新计算
-
应用
-
HashMap
- JDK1.7中HashMap使用一个table数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同，那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表，在极端情况下比如说所有key的hashcode都相同，将会导致这个链表会很长，那么put/get操作需要遍历整个链表，那么最差情况下时间复杂度变为O（n）
- 扩容死链
- 针对JDK1.7中的这个性能缺陷，JDK1.8中的table数组中可能存放的是链表结构，也可能存放的是红黑树结构，如果链表中节点数量不超过8个则使用链表存储，超过8个会调用treeifyBin函数，将链表转换为红黑树。那么即使所有key的hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O（logn）的开销
-
