下面实现一个用于存储键值对的数据格式类，它包含以下属性
- 用于存放元素的key，和对应的值value的实体 （称为node）
- 用于存放元素实体的数组 node[] table
- node元素尽可能散列在table上
- node为链表格式实体
64a63042-280e-3651-ba05-abeaa96fea07.jpg
以上为该工具类的一个基础架构 （注意该工具线程不安全）
代码实现
- 我们创建一个接口 MyMap
//简单起见，我们暂时只预留两个方法
package deng.yb.map;
public interface MyMap {
//根据key获取元素
Object get(Object key);
//保存元素
Object put(Object key, Object value);
}
- 实现该接口，和添加工具类需要的属性
package deng.yb.map;
public class MyHashMap implements MyMap {
//用于存放Node元素的数组
Node[] table;
//数组默认大小 16
final static int DEFAULT_INITIAL_CAPACITY= 1 << 4;
//存放元素的实体，链表结构，通过next指针指向下一个元素
static class Node {
//元素key的hash值，用于散列分布在table上
final int hash;
//元素key
final Object key;
//元素值
Object value;
//具有相同hash值，但key不同元素地址
Node next;
//元素构造方法
Node(int hash, Object key, Object value, Node next){
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
//简单添加key的hash方法
int hash(Object key) {
if (null == key) {
return 0;
}
return key.hashCode();
}
//获取元素
public Object get(Object key) {
// TODO Auto-generated method stub
return null;
}
//存储元素
public Object put(Object key, Object value) {
// TODO Auto-generated method stub
return null;
}
}
- 我们首先实现put方法，代码如下
public Object put(Object key, Object value) {
//该工具类不允许存储key为空的元素
if (key == null) {
return null;
}
//数组采用懒加载方式初始化
if (table == null) {
table = new Node[DEFAULT_INITIAL_CAPACITY];
}
int length = table.length;
int positition;
int hash;
//注意要保证hash后的key在tables分布均匀
//假如数组指定的位置没有元素，则把该地址指向元素对象
if (table[positition = (length - 1 & (hash = hash(key)))] == null) {
table[positition] = new Node(hash, key, value ,null);
} else {
//假如指定的数组位置
//假如确实存在则替换
Node e = table[positition];
if (e.hash == hash && (key == e.key || key.equals(e.key))) {
Object oldValue = e.value;
e.value = value;
return oldValue;
} else {
//把新添的元素挂在链表上 , hash值相同的key在同一个链表上
Node n;
//自旋直至把新元素添加在相同hash链表尾部，或者把链表除头部以外相同key的替换掉值
for (;;) {
//判断所在节点链表下一个是否为空
if ((n = e.next) == null) {
e.next = new Node(hash(key), key, value, null);
break;
}
//判断链表以下有没有相同key
if (n.hash == hash && (key == n.key || key.equals(n.key))) {
Object oldValue = n.value;
n.value = value;
return oldValue;
}
e = n;
}
}
}
return null;
}
-
上述代码最难理解的是，新添的元素怎么散列分布在数组上
1). 和DEFAULT_INITIAL_CAPACITY 做&操作 - 保证元素在数组大小范围内分布
2). 为什么是 (length - 1) & hash(key)- 首先数组大小的要保证是2的n次方，会发现结果-1在转换为二进制的时候，数码都为1；举例 （8-1）= 111； （16-1）= 1111； （32-1）= 11111；...这样在与hash(key)做&操作的时候就能尽量根据hash值不同，相对均匀的分布在数组上，方便后续查询操作
接着实现get方法，代码如下
//查找元素
public Object get(Object key) {
if (key == null) {
return null;
}
int length = 0;
Node first;
if (table != null && (length = table.length) > 0) {
//定位元素在数组中的位置
if ((first = table[(length - 1) & hash(key)]) != null) {
//查找该链表下的第一个node节点是否匹配
if (first.key == key || key.equals(first.key)) {
return first.value;
}
//遍历链表
Node next;
if ((next = first.next) != null) {
for (;;) {
//查找链表next节点下的元素
if (next.key == key || key.equals(next.key)) {
return next.value;
}
next = next.next;
//到达链表尾节点结束
if (null == next) {
break;
}
}
}
}
}
return null;
}
-
测试一下
测试自己写的map工具.png 随着添加的元素越来越多，为了保证查找方便，需要添加扩容resize方法
//MyHashMap新增resize方法
//该类加上
//临界值
int threshold = DEFAULT_INITIAL_CAPACITY;
//元素个数
int size;
- put方法加上以下
//元素个数超过临界值就开始扩容
if (++size >= threshold) {
resize();
}
return null;
- resize方法
//扩容
private void resize() {
if (table != null) {
Node[] oldTab = table;
int oldLength = oldTab.length;
//临界值为原来两倍
threshold <<= 1;
//新数组长度为原来两倍
int newCap = oldLength << 1;
//扩容
Node[] newTab = new Node[newCap];
//元素复制
for (int i = 0 ; i < oldLength ; i++) {
Node e;
if ((e = table[i]) != null) {
if (e.next == null) {
//直接复制
newTab[(newCap - 1) & hash(e.key)] = e;
} else {
//扩容的方式是*2，转换为二进制相当于最高位进1
//通过之前的元素key的hash跟扩容后的容量做&操作，来判断元素需不需要移动, 需要移动的都是做&操作后，高位为1
//需要移动的位置是 (原来的位置 + 原来数组的长度)
//不需要移动的链表头和尾指针 (低位链表的头和尾)
Node lowerHeader = null, lowerTail = null;
//需要移动的链表头和尾 (高位链表头和尾)
Node higherHeader = null, higherTail = null;
Node next;
do {
next = e.next;
if ((hash(e.key) & newCap) == 0) {
//元素不需要移动
if (lowerTail == null) {
lowerHeader = e;
} else {
lowerTail.next = e;
}
lowerTail = e;
} else {
//元素需要移动
if (higherTail == null) {
higherHeader = e;
} else {
higherTail.next = e;
}
higherTail = e;
}
} while ((e=next) != null);
//最后只需要把链表的第一个节点放好数组中即可
if (lowerTail != null) {
lowerTail.next = null;
newTab[i] = lowerHeader;
}
if (higherTail != null) {
higherTail.next = null;
newTab[i + oldLength] = higherHeader;
}
}
}
}
table = newTab;
}
}
