首先附上HashMap结构图一张，方便大家更好的认其底层数据结构，本篇博客主要是对HashMap基本知识以及如何实现HashMap的总结。
一、HashMap的底层数据结构
首先介绍我们会涉及到的基础数据结构
1）数组:对于数组而言，可以根据所找值的索引直接查找该值的位置，即查找容易，删除插入不易。
2）链表：对于链表而言，查找不易，删除插入容易。
3）红黑树：：一种自平衡二叉查找树O(log2N) 的时间内做查找、添加、删除。
4）哈希表又称为散列表，是根据关键码key直接访问内存存储位置的数据结构，即通过关于key的函数，映射到一个地址来访问数据，这样来加快查找速度。
HashMap底层则是基于哈希表实现的，但是当同一位置的元素越来越多，hash值相等的元素也越来越多时，使用key查找的效率也会越来越低。
为了解决这种问题即哈希冲突：
jdk1.8之前，引入链表，使用数组加链表的数据结构；jdk1.8之后则采用数组+链表+红黑树，引入红黑树是当链表的阈值超过8并且数组长度大于64时，链表即会转为红黑树，从而减少了查询时间从O(N)->O(log2N)，极大的提高了数据查询性能。
二、HashMap的使用
HashMap简单使用示例：
public class TestDemo2 {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("ywj", 10);
map.put("zhangsan", 20);
map.put("hhhh", 30); //具体实现都在HashMap
System.out.println(map.isEmpty());
map.remove("ywj", 10);
System.out.println(map.size());
map.containsKey("zhangsan");
map.containsValue(10);
//利用迭代器遍历打印出所有元素
//每一个元素作为一个节点 称为Entry节点 作为set返回
// 获取所有节点的集合
Set<Map.Entry<String, Integer>> entries = map.entrySet();
//获取set集合的迭代器对象
Iterator<Map.Entry<String, Integer>> iterator = entries.iterator();
while (iterator.hasNext()) {
//判断是否还有下一个可迭代的元素 打印输出
Map.Entry<String, Integer> next = iterator.next();
System.out.println(next.getKey() + "::" + next.getValue());
}
}
}
代码运行结果：
三、HashMap的实现
首先HashMap底层是数组+链表的数据结构，那么我们实现的时候，第一步就是实现对应的数组+链表。
属性及构造函数
class MyHashMap<K, V>{
//定义哪些属性
private int size; //有效节点个数
private Node<K, V>[] table;//HashMap底层的桶 数组
private static final int initalCapacity = 16;
class Node<K, V> { //节点
protected K key;
protected V value;
protected Node<K, V> next;
protected int hash;
public Node(int hash, K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
}
//有哪些构造函数
public MyHashMap() {
this(initalCapacity);
}
public MyHashMap(int capacity) {
table = new Node[capacity];
}
}
Hash函数
确定完基本数据结构之后，HashMap当然会用到hash函数，这里我们类比于HashMap中的hash函数，不单独实现代码如下：
//1.8中采用key的hashCode()异或上key的hashCode()进行无符号右移16位的结果
public int hash(Object key) { //hash函数
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法实现(以put()方法为例)
要写代码，首先要确定思路，才能更好的写出代码，我们已经知道HashMap底层的数据结构，那么可以分析得到以下步骤实现put()方法，具体思路如下：
1）key-> hash(key) 散列码 -> hash & table.length-1 index
2）table[index] == null 是否存在节点
3）不存在 直接将key-value键值对封装成为一个Node 直接放到index位置
4）存在 注意key不允许重复，那么分为两种情况
5）存在 key重复 考虑新值去覆盖旧值
6）存在 key不重复 尾插法 将key-value键值对封装成为一个Node 插入新节点
代码实现如下：
public void put(K key, V value) {
//key -》 h = hash(key)散列码 -》table.length-1 & h -> index（确定位置）
//判断index位置是否存在节点
//如果不存在，直接将当前key,value封装为一个Node,插入到该index位置
//如果存在节点(保证HashMap中key不重复)
//判断key是否重复
//如果key有重复，考虑新值覆盖旧值
//如果key没有重复，将当前key,value封装为一个Node 尾插法 插入当前index位置
//key -》 h = hash(key)散列码 -》table.length-1 & h -> index（确定位置）
int hash = hash(key);
int index = table.length - 1 & hash;
//判断index位置是否存在节点
if (table[index] == null) {
//如果不存在，直接将当前key,value封装为一个Node,插入到该index位置
table[index] = new Node(hash, key, value);
size++;
} else {
//如果存在节点(保证HashMap中key不重复)
//获取该位置第一个节点
Node<K, V> firstNode = table[index];
if (firstNode.key.equals(key)) {
firstNode.value = value; //更新值
} else {
Node<K, V> tmp = firstNode;
//判断key是否重复
while (tmp.next != null && !tmp.key.equals(key)) {
//tmp一直跑，要么跑到最后一个节点，要么找到一个key与之相等的节点
tmp = tmp.next;
}
if (tmp.next == null) {
//跑到最后一个节点
if (tmp.key.equals(key)) {
//如果key有重复，考虑新值覆盖旧值
tmp.value = value;
} else {
//如果key没有重复，将当前key,value封装为一个Node 尾插法 插入当前index位置
tmp.next = new Node(hash, key, value);
size++;
}
} else {
//如果key有重复，考虑新值覆盖旧值
tmp.value = value;
}
}
}
}
HashMap扩容
HashMap的扩容，是对数组进行二倍扩容，那么扩容完之后数组中每个链表节点即需要重新确定位置。
int index = key % table.length(简化一下求index函数)
原始链表长度为4
0 1 2 3
key 0 2
4 6
8
新链表长度为8(2倍扩容)
0 1 2 3 4 5 6 7
key 0 2 4 6
8
观察分析可得：key=4 移到了 index=4 oldIndex+(newTable.length-oldTable.length) 0+4
key=6 移到了 index=2 oldIndex+(newTable.length-oldTable.length) 2+4
那么可以得到结论：原来的结点要么在原位置，要么在 原位置+两表长度之差
*/
代码实现如下：
public void resize(){
//HashMap的扩容
//table进行扩容 2倍的方式 扩容数组
Node<K, V>[] newTable = new Node[table.length*2];
//index -> table.length-1 & hash
//重哈希
for(int i=0; i<table.length; i++){
rehash(i, newTable);
}
this.table = newTable;
}
public void rehash(int index, Node<K,V>[] newTable){
//只是针对于数组中的某一个
//index 当前要遍历哪一个位置点 index = key % table.length
//给定新数组 重哈希到新数组
//相当于对原先哈希表中每一个有效节点 进行 重哈希的过程
Node<K,V> currentNode = table[index];
if(currentNode == null){
return;
}
Node<K,V> lowHead = null; //低位的头
Node<K,V> lowTail = null;//低位的尾
Node<K,V> highHead = null;//高位的头
Node<K,V> highTail = null;//高位的尾
while(currentNode != null){
//遍历index位置的所有节点
int newIndex = hash(currentNode.key) & (newTable.length-1);
if(newIndex == index){
//当前节点链到lowTail之后
if(lowHead == null){
lowHead = currentNode;
lowTail = currentNode;
}else{
lowTail.next = currentNode;
lowTail = currentNode;
}
}else{
//当前节点链到highTail之后
if(highHead == null){
highHead = currentNode;
highTail = currentNode;
}else{
highTail.next = currentNode;
highTail = currentNode;
}
}
currentNode = currentNode.next;
}
//要么在原位置 （低位位置）
if(lowHead != null && lowTail != null){
lowTail.next = null;
newTable[index] = lowHead;
}
//要么跑到原位置 + 扩容前长度 （高位位置）
if(highHead != null && highTail != null){
highTail.next = null;
newTable[index + table.length] = highHead;
}
}
}
文章不足之处，欢迎大家指正！后期附上源码链接撒！
本文地址：https://blog.csdn.net/m0_45177725/article/details/113359737
黄山市民网：https://www.huangshanshimin.com/
