建议收藏！细说HashMap实现，Hash冲突模拟思路讲解。
思路记录:
1.HashMap主体是一个Entry数组，当多个key值经过hash计算得到的索引一致，则发生Hash冲突，该索引上的Entry对象就会成为链表的头结点，后续同索引的Entry将会插入该链表。
2.当进行删除时，应考虑如果目标对象在链表中且还有子节点，就需要按照链表的删除法进行，防止后续对象丢失。假设father为目标对象的前一个结节。则father.next = father.next.next
3.扩容对于新旧两个数组以及索引需要理清思路，并且在put，get，remove的代码里分清值传递与引用传递，防止自以为对象追加进链表其实没有。
4.代码每个关键处都有注释，阅读前需对HashMap的基本特点心中有大概的理解。
代码实现：
接口类
对于每个操作的hashConfictIndex参数作用，因为能引起hash冲突的情况比较难找到，所以追加了这个参数，传入-1就按正常情况调用hash方法对数组规模取余计算索引，如果我们想给索引5的位置追加对象来模仿哈希冲突，就需要传入5来模拟。这种模拟的对象在get和remove时也需要我们手动传入同index，因为正常的hash计算根据我们给的key并不一定能求得我们插入时设定的索引。
package com.lx.myhashmap;
public interface MyHashMapInter {
public String get(String key,int hashConfictIndex);
public void put(String key,String value,int hashConfictIndex);
public void remove(String key,int hashConfictIndex);
interface MyEntryInter{
public String get();
public void set();
}
}
实现类
在每个关键处都有注释以及控制台输出，如果看着不清楚可以复制代码运行跟断点走，记得修改包名com.xx.xxx
package com.lx.myhashmap;
import java.util.Map;
public class MyHashMap implements MyHashMapInter {
//初始容量
private int initCapacity;
//已放入元素
public int counts;
//Entry数组
MyEntry[] table;
//扩容系数
private double loadFactory = 0.75;
public MyHashMap(int initCapacity, double loadFactory) {
this.initCapacity = initCapacity;
this.loadFactory = loadFactory;
table = new MyEntry[initCapacity];
}
@Override
public String get(String key, int hashConflictIndex) {
int index;
if (-1 == hashConflictIndex) {
index = hash(key) % initCapacity;
} else {
index = hashConflictIndex;
}
//数组该索引处空
if (table[index] == null) {
return null;
}
//key相同
if (table[index].key.equals(key)) {
return table[index].value;
}
//遍历链表
MyEntry temp = table[index];
while (temp.next != null) {
temp = temp.next;
if (temp.key.equals(key)) {
return temp.value;
}
}
return null;
}
@Override
public void put(String key, String value, int hashConflictIndex) {
int index;
//计算该key索引
if (-1 == hashConflictIndex) {
index = hash(key) % initCapacity;
} else {
index = hashConflictIndex;
}
System.out.println("计算得到索引为 " + index);
if (null == table[index]) {//如果该索引上无对象
table[index] = new MyEntry(key, value, null);
counts++;
reLoad();
System.out.println("put: 在数组中添加");
} else {//如果已有对象
//如果key相同
if (table[index].key.equals(key)) {
table[index].value = value;
System.out.println("put: 覆盖数组对象");
} else {//遍历链表
System.out.println("put: 进入链表");
MyEntry temp = table[index];
MyEntry father = temp;
while (temp.next != null) {
father = temp;
temp = temp.next;
if (temp.key.equals(key)) {
temp.value = value;
System.out.println("put: 链表对象覆盖");
return;
}
}
temp.next = new MyEntry(key, value, null);
counts++;
reLoad();
System.out.println("put: 链表尾追加");
}
}
}
@Override
public void remove(String key, int hashConflictIndex) {
int index;
if (-1 == hashConflictIndex) {
index = hash(key) % initCapacity;
} else {
index = hashConflictIndex;
}
if (table[index] == null) {
System.out.println("remove:没有该值");
}
if (table[index].key.equals(key)) {
if (table[index].next == null) {
table[index] = null;
System.out.println("remove: 数组中找到了 删除");
return;
} else {
table[index] = table[index].next;
System.out.println("remove: 找到了 删除 该链下一元素补位");
return;
}
}
MyEntry temp = table[index];
while (temp.next != null) {
MyEntry father = temp;
temp = temp.next;
if (temp.key.equals(key)) {
if (temp.next == null) {
father.next = null;
System.out.println("remove: 链表中已经找到，删除");
} else {
father.next = father.next.next;
System.out.println("remove: 链表中已经找到，删除并链接两端");
}
return;
}
}
System.out.println("remove: 已遍历完链表，没有该值");
}
/*
散列方法
*/
private int hash(String key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
private void reLoad() {
double top = initCapacity * loadFactory;
if (counts >= top) {
System.out.println("reload: 达到阈值，扩容 ");
initCapacity = 2 * initCapacity;
MyEntry[] oldTable = table;
table = new MyEntry[initCapacity];
counts = 0;
for(int i = 0; i < oldTable.length; i++) {
MyEntry entry = oldTable[i];
while (entry != null) {
put(entry.key, entry.value, -1);
entry = entry.next;
}
}
}
}
class MyEntry implements MyEntryInter {
public String key;
public String value;
public MyEntry next;
public MyEntry(String key, String value, MyEntry next) {
this.key = key;
this.value = value;
this.next = next;
}
@Override
public String get() {
return value;
}
@Override
public void set() {
this.value = value;
}
}
}
测试案例
1.数组覆盖
代码：
package com.lx.myhashmap;
import java.util.HashMap;
public class Demo {
public static void main(String[] args) {
MyHashMap map = new MyHashMap(8,0.75);
map.put("1","hello",-1);
System.out.println("------------------------------");
System.out.println("值为:"+map.get("1",-1)+"
----------------");
map.put("1","world",-1);
System.out.println("------------------------------");
System.out.println("值为:"+map.get("1",-1)+"
----------------");
}
}
输出：
计算得到索引为 1
put: 在数组中添加
------------------------------
值为:hello
----------------
计算得到索引为 1
put: 覆盖数组对象
------------------------------
值为:world
----------------
2.链表追加
这里我们不传-1，而是传入索引1来模拟哈希冲突(假设也计算出了1)
代码：
package com.lx.myhashmap;
import java.util.HashMap;
public class Demo {
public static void main(String[] args) {
MyHashMap map = new MyHashMap(8,0.75);
map.put("1","hello",-1);
System.out.println("------------------------------");
System.out.println("值为:"+map.get("1",-1)+"
----------------");
map.put("3","world",1);
System.out.println("------------------------------");
System.out.println("值为:"+map.get("3",1)+"
----------------");
}
}
输出：
计算得到索引为 1
put: 在数组中添加
------------------------------
值为:hello
----------------
计算得到索引为 1
put: 进入链表
put: 链表尾追加
------------------------------
值为:world
----------------
3.扩容
代码：
package com.lx.myhashmap;
import java.util.HashMap;
public class Demo {
public static void main(String[] args) {
MyHashMap map = new MyHashMap(8,0.75);
map.put("1","hello",-1);
map.put("2","hello",-1);
map.put("3","hello",1);
map.put("4","hello",1);
map.put("5","hello",-1);
map.put("6","hello",-1);
map.put("7","hello",-1);
}
}
输出：
计算得到索引为 1
put: 在数组中添加
计算得到索引为 2
put: 在数组中添加
计算得到索引为 1
put: 进入链表
put: 链表尾追加
计算得到索引为 1
put: 进入链表
put: 链表尾追加
计算得到索引为 5
put: 在数组中添加
计算得到索引为 6
reload: 达到阈值，扩容
计算得到索引为 1
put: 在数组中添加
计算得到索引为 3
put: 在数组中添加
计算得到索引为 4
put: 在数组中添加
计算得到索引为 2
put: 在数组中添加
计算得到索引为 5
put: 在数组中添加
计算得到索引为 6
put: 在数组中添加
put: 在数组中添加
计算得到索引为 7
put: 在数组中添加
4.元素在链表中间的删除
这是最特殊的地方，删除不能简单的设空，需要考虑链会不会断掉。
代码：
package com.lx.myhashmap;
import java.util.HashMap;
public class Demo {
public static void main(String[] args) {
MyHashMap map = new MyHashMap(8,0.75);
map.put("1","hello",-1);
map.put("3","hello",1);
map.put("4","hello",1);
System.out.println(map.get("3",1));
map.remove("3",1);
System.out.println(map.get("3",1));
}
}
输出：
计算得到索引为 1
put: 在数组中添加
计算得到索引为 1
put: 进入链表
put: 链表尾追加
计算得到索引为 1
put: 进入链表
put: 链表尾追加
hello
remove: 链表中已经找到，删除并链接两端
null
总结：
主要还是学习思路，目前剩余链表size大于8转红黑树的功能待实现，因为树的体系比较复杂才学到二叉查找树，直接跳过去学红黑树不现实，后面等可以写出红黑树了再回头把这里完善。