public class OpenAddressing {
// A hash function digest a key to a smaller number which is used as the index of the given element
// located in the hash map. There is a chance/possibility that two keys generates the same index.
// The situation where a newly inserted key maps to an already occupied slot in the hash table is called
// collision and must be handled using some collision handling technique. And here we introduce Open
// Addressing method to address hash collision issue.
public static void main(String[] args) {
MyHashMap<Integer, String> ht = new OpenAddressing().new MyHashMap();
Integer key = 1212;
String value = "1111";
ht.put(key, value);
System.out.println(ht.get(key));
System.out.println(ht.size());
ht.remove(key);
System.out.println(ht.get(key));
System.out.println(ht.size());
key = 1313;
value = "1212";
ht.put(key, value);
System.out.println(ht.get(key));
System.out.println(ht.size());
key = 1313;
value = "1414";
ht.put(key, value);
System.out.println(ht.get(key));
System.out.println(ht.size());
ht.enlarge();
System.out.println(ht.get(key));
System.out.println(ht.size());
}
class MyHashMap<K extends Comparable<K>, V> {
private final static int DEFAULT_LINKED_LIST_SIZE = 16;
private int size = 0;
// Here we employ separate chaining method which makes each cell of hash table point
// to a linked list of records that have same hash function value.
private MyLinkedList<K, V>[] arr;
public MyHashMap() {
// Default initial capacity of the HashMap takes is 16
this(DEFAULT_LINKED_LIST_SIZE);
}
public MyHashMap(int maxSize) {
arr = new MyLinkedList[maxSize];
}
public void put(K key, V val) {
int hashVal = hashCode(key);
if (arr[hashVal] == null) {
arr[hashVal] = new MyLinkedList();
}
int rst = arr[hashVal].add(new Item(key, val));
// rst = 1 represents new node is inserted; rst=0 means update the already existing node.
size += rst;
// A HashMap with overload elements will degrade into a linear search, so you need
// to keep them under 75% full.
if (size * 1.0 / arr.length > 0.75) {
enlarge();
}
}
public V get(K key) {
int hashVal = hashCode(key);
if (arr[hashVal].get(key) == null) {
return null;
}
return arr[hashVal].get(key).obj;
}
public V remove(K key) {
int hashVal = hashCode(key);
Item<K, V> item = arr[hashVal].delete(key);
if (item != null) {
size--;
}
return item.obj;
}
public int hashCode(K key) {
return hashCode(key, arr.length);
}
private int hashCode(K key, int bound) {
return key.hashCode() % bound;
}
public void enlarge() {
// We can increase table size by copying old data if needed.
MyLinkedList<K, V>[] newArr = new MyLinkedList[arr.length * 2];
for (int i = 0; i < arr.length; i++) {
if (arr[i] == null || arr[i].head == null) {
continue;
}
int hash = hashCode(arr[i].head.item.key, arr.length * 2);
newArr[hash] = arr[i];
}
arr = newArr;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
class MyLinkedList<K, V> {
private Node<K, V> head;
public MyLinkedList() {
head = null;
}
public int add(Item<K, V> item) {
// In this scheme, data always inserted at the head. But we can also keep probing
// until reach the end of the list after which we append the new item.
// Node node = new Node(item);
// node.next = head;
// head = node;
Node<K, V> preHead = new Node(null);
preHead.next = head;
while (preHead.next != null) {
if (!preHead.next.item.key.equals(item.key)) {
preHead = preHead.next;
continue;
}
preHead.next.item.obj = item.obj;
// returning 0 means key exists, update the binding value
return 0;
}
preHead.next = new Node(item);
// Don't forget to update the head
head = preHead.next;
// returning 0 means key does not exist, add a new node
return 1;
}
public Item<K, V> get(K key) {
Node<K, V> ptr = head;
while (ptr != null) {
if (ptr.item.key.equals(key)) {
return ptr.item;
}
ptr = ptr.next;
}
return null;
}
public Item<K, V> delete(K key) {
Node<K, V> preHead = new Node(null);
preHead.next = head;
Node<K, V> ptr1 = preHead;
Node<K, V> ptr2 = ptr1.next;
while (ptr2 != null) {
if (!ptr2.item.key.equals(key)) {
ptr1 = ptr2;
ptr2 = ptr1.next;
continue;
}
ptr1.next = ptr2.next;
// There are good chance the deleted node is the head
head = preHead.next;
return ptr2.item;
}
return null;
}
}
class Item<K, V> {
K key;
V obj;
public Item(K key, V obj) {
this.key = key;
this.obj = obj;
}
}
class Node<K, V> {
Item<K, V> item;
Node<K, V> next;
public Node(Item item) {
this.item = item;
}
}
}