【深究系列】实现自己的HashMap
public class MyHashMap {
static class Entry{
private Object key;
private Object value;
private Entry next;
public Entry(Object key, Object value) {
this.key = key;
this.value = value;
}
public Object getKey() {
return key;
}
public void setKey(Object key) {
this.key = key;
}
public Object getValue() {
return value;
}
public void setValue(Object value) {
this.value = value;
}
public Entry getNext() {
return next;
}
public void setNext(Entry next) {
this.next = next;
}
}
private Entry[] table;
private int capacity = 16;
private float loadfactor = 0.75f;
private int size = 0;
public MyHashMap() {
table = new Entry[capacity];
}
public void put (Object key, Object value) {
int index = key.hashCode() % capacity;
Entry entry = new Entry(key, value);
//头结点
Entry head = table[index];
if (head == null){
table[index] = entry;
size++;
}
else {//发生hash冲突,查看是更新还是重新赋值
for (Entry e = head; e != null; e = e.getNext()) {
//对于每一个entry,先判断是不是要覆盖
if ((e.getKey().hashCode() == key.hashCode()) && (e.getKey() == key || e.getKey().equals(key))) {
e.value = value;
break;
} else {
if (e.next == null) {
//当前e是最后一个节点
entry.next = head;
table[index] = entry;
size++;
}
}
}
if (size > capacity * loadfactor) {
resize(capacity << 1);
}
}
}
private void resize(int newCapacity) {
System.out.println("-----------------扩容了-----------------");
Entry[] newTable = new Entry[newCapacity];
Entry[] src = table;
for (int i = 0; i < src.length; i++) {
Entry head = src[i];
if (head != null) {
Entry e = head;
do {
Entry nextEntry = head.next;
int index = e.getKey().hashCode() % newCapacity;
e.next = newTable[index];
newTable[index] = e;
e = nextEntry;
} while(e != null);
}
}
table = newTable;
capacity = newCapacity;
}
public Object get(Object key) {
if (key == null) return null;
int index = key.hashCode() % capacity;
Entry head = table[index];
for (Entry e = head; e != null; e = e.next) {
if (e.key.equals(key) || e.key == key)
return e.getValue();
}
return null;
}
public void remove(Object key) {
if (key == null) return;
int index = key.hashCode() % capacity;
Entry pre = null;
Entry cur = table[index];
while (cur != null) {
if (cur.getKey().hashCode() == key.hashCode() && (cur.getKey() == key || cur.getKey().equals(key))) {
if (pre == null)
table[index] = cur.next;
else
pre.next = cur.next;
size--;
return;
}
pre = cur;
cur = cur.next;
}
}
public void print() {
for (int i = 0; i < table.length; i++) {
System.out.print("下标[" + i + "] ");
for (Entry e = table[i]; e != null; e = e.next) {
System.out.print("【key = " + e.key + ",value = " + e.value + "】 ");
}
System.out.println();
}
}
}