写点东西
\[\int x dx\]/*
* In this problem, I follow some basic settings in JDK, such as
* DEFAULT_INITIAL_CAPACITY and DEFAULT_LOAD_FACTOR value. Inside
* MyHashMap, there is an inner static class MyEntry to save the
* key-value pair. MyEntry also serves as a linked list with its
* next field. Following the JDK size modification, resize() is also
* implemented to do the element moving operation. The hash()
* method is directly copied from JDK source code for simplification.
*/
class MyHashMap<K, V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
private MyEntry[] table;
private int size;
public static class MyEntry<K, V> {
K key;
V value;
int hash;
MyEntry<K, V> next;
public MyEntry(K key, V value, int hash, MyEntry<K, V> next) {
this.key = key;
this.value = value;
this.hash = hash;
this.next = next;
}
}
public MyHashMap() {
table = new MyEntry[DEFAULT_INITIAL_CAPACITY];
size = 0;
}
public V get(K key) {
if (key == null) {
throw new RuntimeException("key is null");
}
int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);
MyEntry<K, V> e = table[index];
while (e != null) {
if (hash == e.hash && (key == e.key || key.equals(e.key))) {
return e.value;
}
e = e.next;
}
return null;
}
public V put(K key, V value) {
if (key == null) {
throw new RuntimeException("key is null");
}
int hash = hash(key.hashCode());
int index = indexFor(hash, table.length);
MyEntry<K, V> e = table[index];
while (e != null) {
if (e.hash == hash && (key == e.key || key.equals(e.key))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
e = e.next;
}
MyEntry<K, V> next = table[index];
table[index] = new MyEntry<>(key, value, hash, next);
if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) {
resize();
}
return null;
}
private void resize() {
int newCapacity = table.length * 2;
MyEntry[] newTable = new MyEntry[newCapacity];
MyEntry[] src = table;
for (int j = 0; j < src.length; j++) {
MyEntry<K, V> e = src[j];
src[j] = null;
while (e != null) {
MyEntry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
table = newTable;
}
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
h = h > 0 ? h : -h;
return h % length;
}
}
public class q3 {
public static void main(String[] args) {
MyHashMap<String, String> map = new MyHashMap<>();
map.put("Tom", "good");
map.put("Bob", "bad");
map.put("Ash", "fair");
// return old value and save new value
String oldValue = map.put("Ash", "good");
System.out.println("value for " + "Tom: " + map.get("Tom"));
System.out.println("value for " + "Bob: " + map.get("Bob"));
System.out.println("old value for Ash:" + oldValue);
System.out.println("new value for Ash:" + map.get("Ash"));
}
}