Map.java
package com.collection;
public interface Map<K, V> {
public V put(K k, V v);
public V get(K k);
public int size();
interface Entry<K, V> {
public K getKey();
public V getValue();
}
}
HashMap.java
package com.collection;
public class HashMap<K, V> implements Map<K, V> {
private Entry<K, V>[] table = null;
private int size = 0;
private static int defaultLength = 16;
public HashMap() {
table = new Entry[defaultLength];
}
@Override
public V put(K k, V v) {
int index = hash(k);
Entry<K, V> entry = table[index];
if (entry == null) {
table[index] = new Entry<K, V>(k, v, null, index);
size++;
} else {
table[index] = new Entry<K, V>(k, v, entry, index);
}
return table[index].getValue();
}
private int hash(K k) {
int index = k.hashCode() & (defaultLength - 1);
return Math.abs(index);
}
@Override
public V get(K k) {
if (size == 0) {
return null;
}
int index = hash(k);
Entry<K, V> entry = getEntry(k, index);
return entry == null ? null : entry.getValue();
}
private Entry<K, V> getEntry(K k, int index) {
for (Entry<K, V> entry = table[index]; entry != null; entry = entry.next) {
if (entry.hash == index && (k == entry.getKey() || k.equals(entry.getKey()))) {
return entry;
}
}
return null;
}
@Override
public int size() {
return 0;
}
class Entry<K, V> implements Map.Entry<K, V> {
K k;
V v;
Entry<K, V> next;
int hash;
public Entry(K k, V v, Entry<K, V> next, int hash) {
this.k = k;
this.v = v;
this.next = next;
this.hash = hash;
}
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return v;
}
}
}
TestHashMap.java
package com.collection;
public class TestHashMap {
public static void main(String[] args) {
com.collection.HashMap map = new com.collection.HashMap<>();
for (int i = 0; i < 6666; i++) {
map.put("Monkey" + i, "計算方法的事實");
System.out.println(map.get("Monkey"));
}
System.out.println(map);
}
}