public class MyHashMap {
private class Entry {
int hash;
K key;
V value;
Entry next;
Entry(int hash, K key, V value, Entry next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
private static final int DEFAULT_CAPACITY = 1 <<2;
private Entry[] table;
private int capacity;
private int size;
private final float loadFactor = 0.75f;
public MyHashMap() {
this(DEFAULT_CAPACITY);
}
@SuppressWarnings("unchecked")
public MyHashMap(int capacity) {
if (capacity <0) {
throw new IllegalArgumentException();
} else {
table = new Entry[capacity];
size = 0;
this.capacity = capacity;
}
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0 ? true : false;
}
public V put(K key, V value) {
if (key == null) {
throw new RuntimeException("key不可以为空!");
}
if (size >= capacity * loadFactor) {
// 开始rehash
resize(2 * table.length);
int hash = (null != key) ? hash(key) : 0;
int index = indexFor(hash, table.length);// 注意此时的table已经扩容了
}
V newValue = putEntry(key, value);
return newValue;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
private void resize(int newCapacity) {
System.out.println("我们要扩容了!!当前的size是:" + size);
// 让数组长度乘以两倍
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, true);
table = newTable;
}
@SuppressWarnings({ "rawtypes", "unchecked" })
private void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry e : table) {
while (e != null) {
if (rehash) {
// 要重新hash
e.hash = null == e.key ? 0 : hash(e.key);
}
int index = indexFor(e.hash, newCapacity);
// 开始把e放进新的数组中
// 注意,每次插入新的值都必须要插在散列链表的头部
e.next = newTable[index];
newTable[index] = e;
e = e.next;
}
}
}
private V putEntry(K key, V value) {
if (key == null) {
throw new RuntimeException("key不可以为空!");
}
int hash = hash(key);
int i = indexFor(hash, table.length);
Entry newEn = new Entry(hash, key, value, null);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 代表当前的e和要添加的key冲突了,那么就覆盖
V oldValue = e.value;
e.value = value;// 当前的e的value要替换为新的value
return oldValue;
}
}
// 如果上面没有找到的话,就要往链表添加元素了
size++;
addEntry(newEn, i);
return value;
}
private void addEntry(Entry entry, int index) {
Entry e = table[index];
table[index] = entry;
entry.next = e;
}
public V get(K key) {
if (key == null) {
throw new RuntimeException("key不可以为空!");
}
Entry entry = getEntry(key);
return null == entry ? null : entry.value;
}
private Entry getEntry(K key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
for (Entry e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
return e;
}
}
return null;
}
public V remove(K key) {
Entry e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
private Entry removeEntryForKey(K key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry cur = table[i];
Entry e = cur;
while (e != null) {
if (e.hash == hash && (e.key == key || key.equals(e.key))) {
size--;
// 如果删除的是prev的话
if (cur == e) {
table[i] = e.next;
} else {
// 就让cur的next等于e的next
cur.next = e.next;
}
return e;
}
cur = e;
e = e.next;
}
return null;
}
private int indexFor(int hash, int length) {
return hash & (length - 1);// 哈希值和长度减一做与运算
}
private int hash(K key) {
return key.hashCode();
}
public static void main(String[] args) {
MyHashMap map = new MyHashMap<>();
}
}