引言
上一篇博客学习了HashMap的源码，了解了hash函数设计原理和基本的增删改查及扩容实现，今天我们依葫芦画瓢，基于数组和单链表尝试手写简单的HashMap,实现它的put\get\remove\resize操作。
Map接口
包含了基本的操作:put\get\remove\size方法:
package hash;
/**
* Created by chenming on 2018/6/10
* 基本的map接口
*/
public interface Map<K, V> {
/**
* 大小
* @return
*/
int size();
/**
* 添加元素
* @param key
* @param object
*/
void put(K key, V object);
/**
* 查找元素
* @param key
* @return
*/
V get(K key);
/**
* 删除元素
* @param key
* @return
*/
V remove(K key);
}
节点Node定义
节点为单链表节点,思路和JDK一样
package hash;
/**
* Created by chenming on 2018/6/10
*/
public class Node<K, V> {
private int hash;//桶中的hash值,与key不一样
private K key;
private V value;
public Node next;
public Node(int hash, K key, V value) {
this.hash = hash;
this.key = key;
this.value = value;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final String toString() {
return key + "=" + value;
}
public int getHash() {
return hash;
}
public void setHash(int hash) {
this.hash = hash;
}
public void setKey(K key) {
this.key = key;
}
public void setValue(V value) {
this.value = value;
}
}
hash函数
参考JDK1.8，具体设计思想参考上篇的源码分析，这里不在赘述
/**
* 对key重新hash
*
* @param key
* @return
*/
private int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* hash函数，hash到索引的映射
*
* @param hash
* @param len
* @return
*/
private int indexFromHash(int hash, int len) {
int index = (len - 1) & hash;
return index;
}
判断key命中
前提:
1.hashcode相等;
2.key对象相同。
/**
* 判断key是否命中
*
* @param key
* @param n
* @return
*/
private boolean isNodeHit(K key, Node n) {
int hash = hash(key);
if (n.getHash() == hash) {
if (key == n.getKey() || (key != null) && (key.equals(n.getKey()))) {
return true;
}
}
return false;
}
put方法
/**
* put操作
* @param key
* @param value
*/
@Override
public void put(K key, V value) {
int hash = hash(key);
int index = indexFromHash(hash, table.length);
Node first = table[index];
if (first == null) {//空坑直接占上
first = new Node(hash, key, value);
table[index] = first;
} else {
Node p = first;
while (p.next != null) {
if (isNodeHit(key, p)) {//链表中存在hit的node
//替换value,直接反馈
p.setValue(value);
return;
}
p = p.next;
}
p.next = new Node(hash, key, value);
}
if (++size > threhold) {
resize();//扩容
}
return;
}
程序结构和JDK1.8有出入，思路是一样的.
get方法
/**
* 获取方法
* @param key
* @return
*/
@Override
public V get(K key) {
int index = indexFromHash(hash(key), table.length);
Node<K, V> first = table[index];
if (first == null) {
return null;
} else {
Node<K, V> p = first;
while (p != null) {
if (isNodeHit(key, p)) {//如果命中则返回节点值
return p.getValue();
}
p = p.next;
}
}
return null;
}
remove方法
/**
* 删除元素
* @param key
* @return
*/
@Override
public V remove(K key) {
int index = indexFromHash(hash(key), table.length);
Node<K, V> first = table[index];
V oldVal = null;
if (first != null) {
if (first.next == null) {//桶里面只有一个元素，直接删除
oldVal = first.getValue();
//直接删除
table[index] = null;
} else {
if (isNodeHit(key, first)) {//头结点命中，则删除头结点
//直接删除头结点
table[index] = first.next;
} else {
//开始遍历，查找key命中的节点
Node<K, V> pre = first;
Node<K, V> p = pre.next;
while (p != null) {
if (isNodeHit(key, p)) {//找到命中节点
oldVal = p.getValue();
pre.next = p.next;//删除操作
p.next = null;
break;
}
pre = p;
p = p.next;
}
if (p == null) {//没找到命中节点,直接返回
return null;
}
}
}
}
size--;
return oldVal;
}
思路:如果对应位置只有一个元素，则直接删除，否则遍历单链表，删除节点。
扩容操作
/**
* 扩容操作
*/
private void resize() {
int oldCap = table.length;
int newCap = oldCap << 1;
threhold = (int) (newCap * DEFAULT_LOAD_FACTOR);
Node<K, V>[] newTable = new Node[newCap];
for (int i = 0; i < oldCap; i++) {
Node<K, V> first = table[i];
if (first != null) {
int hash = first.getHash();
if (first.next == null) {
newTable[indexFromHash(hash, newCap)] = first;
} else {//拆分单链表成两个部分，一个挂载低索引，另外一个挂载高索引
Node<K, V> next;//保存旧链表的后继节点
//两个单链表的首尾指针
Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> p = first;
do {
next = p.next;
if ((oldCap & p.getHash()) == 0) {//低位索引
if (loTail == null) {
loHead = p;
} else {
loTail.next = p;
}
loTail = p;
} else {//高位索引
if (hiTail == null) {
hiHead = p;
} else {
hiTail.next = p;
}
hiTail = p;
}
} while ((p = next) != null);
if (loHead != null) {
loTail.next = null;
newTable[i] = loHead;
}
if (hiHead != null) {
hiTail.next = null;
newTable[i + oldCap] = hiHead;
}
}
}
}
table = newTable;//替换旧数组
}
单链表的拆分操作和设计思想和jdk一样，具体分析看上篇文章。
最后献上测试代码:
/**
* 测试哈希基本操作
*/
@Test
public void testHashMap() {
HashA a = new HashA("ABC");
HashB b = new HashB("ABC");
//HashMap的key可以为空
hash.HashMap<Object, String> hashMap = new hash.HashMap<>();
hashMap.put(null, "90");
System.out.println(hashMap.get(null));
hash.HashMap<Object, String> myHashMap = new hash.HashMap<>();
hash.HashMap<Object, String> myHashCrashMp = new hash.HashMap<>();
System.out.println("=====哈希冲突测试====");
myHashCrashMp.put(a, "a");
myHashCrashMp.put(b, "b");
System.out.println(myHashCrashMp.get(a));
System.out.println(myHashCrashMp.get(b));
List<HashA> keys = new LinkedList<>();
for (int i = 0; i < 13; i++) {
HashA hashObj = new HashA("ABC" + i);
keys.add(hashObj);
myHashMap.put(hashObj, "" + i);
}
System.out.println("=====哈希删除测试====");
int delIndex = 4;
myHashMap.remove(keys.get(delIndex));
keys.remove(delIndex);
System.out.println("=====哈希大小====");
System.out.println(myHashMap.size());
System.out.println("=====哈希打印====");
for (int i = 0; i < keys.size(); i++) {
HashA hashObj = keys.get(i);
String v = myHashMap.get(hashObj);
System.out.println(v);
}
}
完整代码地址:数据结构与算法学习JAVA描述GayHub地址
