原谅人家写的资料我看不懂，有兴趣看看：JAVA HASHMAP的死循环
该写的注释已经都写在的代码里面，直接拷贝就能测
package com.lw.vrv.javacore.hashmap;
import java.util.Map;
import java.util.Objects;
/**
* 自定义HashMap: 实现简单put和get方法，方便理解hashcode 用取模算出，key用int方便计算模，取模结果就是数组的下标，即key=value所要存放的位置
*
*
* 创建类：TODO
*
* @author BruceLiu
*
* @param <K>
* @param <V>
*/
public class MyHashMap<K, V> {
static final Entry<?, ?>[] EMPTY_TABLE = {};
transient Entry<K, V>[] table = (Entry<K, V>[]) EMPTY_TABLE;
int capacity;
public static void main(String[] args) {
MyHashMap<Integer, Object> myHashMap = new MyHashMap<>(2);//初始化容量为2
myHashMap.put(1, "v1");
myHashMap.put(2, "v2");
myHashMap.put(3, "v3");
myHashMap.put(5, "v5");
//key%2 = 2 1,3
//array: [0] [1]
//linked: v2 v5 //后进来的放最前面
// v3
// v1
//
System.out.println(myHashMap);
System.out.println(myHashMap.get(2));//链表上就一条
System.out.println(myHashMap.get(1));//链表上三条，分表是5,3,1
System.out.println(myHashMap.get(3));
System.out.println(myHashMap.get(5));
myHashMap.resize(4);
}
public MyHashMap(int capacity) {
this.capacity = capacity;
table = new Entry[capacity];
}
public void put(K key, V value) {
//int index = key.hashCode() % capacity;// bluckIndex
int index = (Integer)key % capacity;// 这样简单点，能一眼看出来在哪个位置
/**
* 取出当前下标位置的Entry，作为下一个Entry
* 第一次：currentEntry = null，因为默认是空数组，没有数据
* 第二次：如果index下标位置有数据：取出当前下标的Entry对象，作为当前key-value的下一个节点（新数据替换老数据）
* 第三次：同第二次
* ... ...
*/
Entry<K, V> nextEntry = table[index];
table[index] = new Entry<>(index, key, value, nextEntry);
}
public Entry<K, V> get(K key) {
int index = key.hashCode() % capacity; // bluckIndex
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
Object k;
if (e.hash == index && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
/**
* 扩容方法：
*
* 把原来的table数据复制到新的table上，因为索引变了，所在位置也就变了，重新赋值
*
* @param capacity
*/
public void resize(int newCapacity){
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable; //替换成新数组
}
/**
*
* 关键代码：如果是自己写，你会怎么移动old table到new table
*
* [0] [1] 代表数组的下标位置
*
* key%2
* old table [0] [1]
* key 2 5
* 3
* 1
*
* key%4
* new table [0] [1] [2] [3]
* 1 2 3
* 5
*
*/
void transfer(Entry[] newTable) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) { //遍历老数组
while(null != e) {
int index = (Integer)e.getKey() % newCapacity; //重新取模 新数组下标
//参考：put方法
Entry newNextEntry = newTable[index];
newTable[index] = new Entry<>(index, e.getKey(), e.getValue(), newNextEntry);
//错误写法：因为在新的table中，下一个节点不一定还是在下一个节点，需要重新计算了，直接赋值下一个节点就是错误的
//newTable[index] = new Entry<>(index, e.getKey(), e.getValue(), e.getNext());
//获取下个节点，继续遍历
e = e.getNext();
//源码 ( 逻辑是一样的，就是代码精简一点，你品，你细品 )
//Entry<K,V> next = e.next; //next为临时对象，保存老数据
//e.next = newTable[index]; //相当于重新声明一个新table的下一个节点：相当于Entry next = newTable[index];
//newTable[index] = e; //此处就是为了不重新new对象，复用对象e： 相当于newTable[index] = new Entry<>(index, e.getKey(), e.getValue(), newNextEntry);
//e = next; //准备下一次循环：将next作为下一次遍历的对象e
}
}
}
/**
* Entry对象：就是table[i]所要存放的对象，因为对象里面包含next节点，所以当作单链式结构（因为没有定义前一个节点信息）
*
* 创建类：TODO
* @author BruceLiu
*
* @param <K>
* @param <V>
*/
static class Entry<K, V> implements Map.Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public Entry<K, V> getNext() {
return next;
}
public void setNext(Entry<K, V> next) {
this.next = next;
}
public final String toString() {
return getKey() + "=" + getValue()+", next:"+next;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
}
}
网友评论