class HashBuck<K, V> {
private static class Node<K, V> {
private K key;
private V val;
private Node<K, V> next;
public Node(K key, V val) {
this.key = key;
this.val = val;
}
}
private static final double LOAD_DEFAULT_FACTOR = 0.75;
private Node<K, V>[] array = (Node<K, V>[])new Node[10];
private int usedSize;
public void put(K key, V val) {
int index = key.hashCode() / array.length;
Node<K, V> cur = array[index];
while (cur != null) {
if (cur.val.equals(key)) {
cur.val = val;
return;
}
cur = cur.next;
}
Node<K, V> node = new Node<>(key, val);
node.next = array[index];
array[index] = node;
usedSize++;
if (loadFactor() >= LOAD_DEFAULT_FACTOR) {
resize();
}
}
public void resize() {
Node<K, V>[] newArray = (Node<K, V>[])new Node[array.length *2];
for (int i = 0; i < array.length; i++) {
Node<K, V> cur = array[i];
while (cur != null) {
int index = cur.key.hashCode() / newArray.length;
Node<K, V> curNext = cur.next;
cur.next = newArray[index];
newArray[index] = cur;
cur = curNext;
}
}
array = newArray;
}
private double loadFactor() {
return 1.0 * usedSize / array.length;
}
public V get(K key) {
int index = key.hashCode() / array.length;
Node<K, V> cur = array[index];
while (cur != null) {
if (cur.key.equals(key)) return cur.val;
}
return null;
}
}
|
