基于Java快速实现一个简单版的HashMap详解
短信预约 -IT技能 免费直播动态提醒
简单实现一个底层数据结构为数组 + 链表的HashMap,不考虑链表长度超过8个时变为红黑树的情况。
1.示例图
2.分析需求
put数据时：
- key值hash后的索引处没有元素，需要创建链表头节点，放到该位置的数组空间里。
- key值hash后的索引处有元素，说明产生Hash碰撞，需要在链表中结尾处挂载节点，如果在遍历链表的过程中，发现了同key的数据，则执行覆盖即可，不再继续往下遍历去挂载新节点。
- 假设数组使用的空间超过了总长度的75%，那么对数组进行扩容。先创建新数组，把旧数据写到新数组中(此时需要重新根据key计算Hash，因为数据长度变化了，影响计算结果了)，在用新数据替换掉原来的旧数组。
get数据时：
- key值hash后的索引下标处的元素为空的话，则不存在数据。
- key值hash后的索引下标处存在链表的话，需要遍历链表，找到key相对应的value值。
3.代码实现
Node类实现
package com.zaevn.hashmap;
public class Node {
String key;
String value;
Node next;
public Node(String key, String value, Node nextNode) {
this.key = key;
this.value = value;
this.next = nextNode;
}
}LinkNode类实现
package com.zaevn.hashmap;
public class ListNode {
// 头节点
Node head;
public void addNode(String key,String value){
// 如果头节点是空,则结束
if(head == null ){return;}
// 如果头节点不为空，则往下挂载节点
Node node = new Node(key,value,null);
Node temp = head;
while(true){
// 遇到相同的key,覆盖数据
if(key.equals(temp.key)){
temp.value = value;
return;
}
if(temp.next == null){
break;
}
temp = temp.next;
}
// 循环结束后则挂上数据
temp.next = node;
}
public String getNode(String key){
if(head == null ){return null;}
Node temp = head;
while(true){
if(key.equals(temp.key)){
return temp.value;
}
if(temp.next == null){
break;
}
temp = temp.next;
}
return null;
}
}
MyHashMap类实现
package com.zaevn.hashmap;
public class MyHashMap {
// 数组初始化:2的n次方
ListNode[] map = new ListNode[8];
// ListNode的个数
int size;
// 由于扩容时是先创建一个新数组，因此先声明出来
ListNode[] mapNew;
int sizeNew;
public void put(String key,String value){
if(size>map.length * 0.75){
System.out.println("开始进行扩容，当前size="+size+",数组长度为："+map.length);
doExtendMap();
System.out.println("扩容结束，当前size="+size+",数组长度为："+map.length);
}
// 1.对key进行hash算法然后取模
int index = Math.abs(key.hashCode())%map.length;
ListNode listNode = map[index];
// 如果索引位置的元素为空，则新加一个元素(创建头节点)
if(listNode == null){
ListNode listNodeNew = new ListNode();
Node node = new Node(key,value,null);
listNodeNew.head = node;
map[index] = listNodeNew;
size ++;
}else{
// 如果索引位置的元素不为空，则往链表中挂载数据
listNode.addNode(key,value);
}
}
public String get(String key){
// 1.对key进行hash算法然后取模
int index = Math.abs(key.hashCode())%map.length;
if(map[index] == null){
return null;
}else{
return map[index].getNode(key);
}
}
public void doExtendMap(){
sizeNew = 0;
// 1.先创建一个新的数组，长度为原来的二倍
mapNew = new ListNode[map.length * 2];
// 2.将旧数据映射到新的数组上(因为数组长度变化，因此hash规则变化，所有的值需要重新计算hash值)
for(int i = 0;i<map.length;i++){
ListNode listNode = map[i];
if(listNode == null){
continue;
}
Node temp = listNode.head;
while (true){
doPutData(mapNew,temp.key,temp.value);
if(temp.next == null){
break;
}
temp = temp.next;
}
}
// 3.将新的数组替换旧的数组
map = mapNew;
this.size = sizeNew;
}
private void doPutData(ListNode[] mapParam,String key,String value){
int index = Math.abs(key.hashCode())%mapParam.length;
ListNode listNode = mapParam[index];
if(listNode == null){
ListNode listNodeNew = new ListNode();
Node node = new Node(key,value,null);
listNodeNew.head = node;
mapParam[index] = listNodeNew;
sizeNew ++;
}else{
listNode.addNode(key,value);
}
}
public static void main(String[] args) {
// 1、一般校验
MyHashMap hashMap0=new MyHashMap();
hashMap0.put("key1","value1");
System.out.println("一般校验："+hashMap0.get("key1"));
System.out.println("--------------------------------------------");
// 2、同key覆盖校验
MyHashMap hashMap1=new MyHashMap();
hashMap1.put("key2","value00");
hashMap1.put("key2","value01");
System.out.println("同key覆盖校验："+hashMap1.get("key2"));
System.out.println("--------------------------------------------");
// 3、哈希碰撞校验(k1和k9的经过哈希计算后得到的索引都是6)
MyHashMap hashMap2=new MyHashMap();
hashMap2.put("k1","value_k1");
hashMap2.put("k9","value_k9");
System.out.println("哈希碰撞校验：k1:"+hashMap2.get("k1")+" k9:"+hashMap2.get("k9"));
System.out.println("--------------------------------------------");
// 4、扩容校验
MyHashMap hashMap3=new MyHashMap();
hashMap3.put("m3","cccccc");
hashMap3.put("c1","kkkkkk");
hashMap3.put("c2","mmmmmmm");
hashMap3.put("b1","bbbbbbb");
hashMap3.put("m1","cccccc");
hashMap3.put("c3","kkkkkk");
hashMap3.put("c4","mmmmmmm");
hashMap3.put("b2","bbbbbbb");
hashMap3.put("m2","cccccc");
hashMap3.put("c5","kkkkkk");
hashMap3.put("c6","mmmmmmm");
hashMap3.put("b3","bbbbbbb");
System.out.println("扩容后的c4:"+hashMap3.get("c4"));
System.out.println("扩容后的b3:"+hashMap3.get("b3"));
}
}3.运行结果
到此这篇关于基于Java快速实现一个简单版的HashMap详解的文章就介绍到这了,更多相关Java HashMap内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
免责声明：
① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的，并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据，供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。
② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
