Hashmap Implementation
Java Code
import [Link].*;
public class HashMapCode {
static class HashMap<K,V> { //generics
private class Node {
K key;
V value;
public Node(K key, V value) {
[Link] = key;
[Link] = value;
}
}
private int n; //n - nodes
private int N; //N - buckets
private LinkedList<Node> buckets[]; //N = [Link]
@SuppressWarnings("unchecked")
public HashMap() {
this.N = 4;
[Link] = new LinkedList[4];
for(int i=0; i<4; i++) {
[Link][i] = new LinkedList<>();
}
}
private int hashFunction(K key) {
int bi = [Link]();
return [Link](bi) % N;
}
private int searchInLL(K key, int bi) {
LinkedList<Node> ll = buckets[bi];
for(int i=0; i<[Link](); i++) {
if([Link](i).key == key) {
return i; //di
}
}
return -1;
}
@SuppressWarnings("unchecked")
private void rehash() {
LinkedList<Node> oldBucket[] = buckets;
buckets = new LinkedList[N*2];
for(int i=0; i<N*2; i++) {
buckets[i] = new LinkedList<>();
}
for(int i=0; i<[Link]; i++) {
LinkedList<Node> ll = oldBucket[i];
for(int j=0; j<[Link](); j++) {
Node node = [Link](j);
put([Link], [Link]);
}
}
}
public void put(K key, V value) {
int bi = hashFunction(key);
int di = searchInLL(key, bi); //di = -1
if(di == -1) { //key doesn't exist
buckets[bi].add(new Node(key, value));
n++;
} else { //key exists
Node node = buckets[bi].get(di);
[Link] = value;
}
double lambda = (double)n/N;
if(lambda > 2.0) {
rehash();
}
}
public boolean containsKey(K key) {
int bi = hashFunction(key);
int di = searchInLL(key, bi); //di = -1
if(di == -1) { //key doesn't exist
return false;
} else { //key exists
return true;
}
}
public V remove(K key) {
int bi = hashFunction(key);
int di = searchInLL(key, bi); //di = -1
if(di == -1) { //key doesn't exist
return null;
} else { //key exists
Node node = buckets[bi].remove(di);
n--;
return [Link];
}
}
public V get(K key) {
int bi = hashFunction(key);
int di = searchInLL(key, bi); //di = -1
if(di == -1) { //key doesn't exist
return null;
} else { //key exists
Node node = buckets[bi].get(di);
return [Link];
}
}
public ArrayList<K> keySet() {
ArrayList<K> keys = new ArrayList<>();
for(int i=0; i<[Link]; i++) { //bi
LinkedList<Node> ll = buckets[i];
for(int j=0; j<[Link](); j++) { //di
Node node = [Link](j);
[Link]([Link]);
}
}
return keys;
}
public boolean isEmpty() {
return n == 0;
}
}
public static void main(String args[]) {
HashMap<String, Integer> map = new HashMap<>();
[Link]("India", 190);
[Link]("China", 200);
[Link]("US", 50);
ArrayList<String> keys = [Link]();
for(int i=0; i<[Link](); i++) {
[Link]([Link](i)+" "+[Link]([Link](i)));
}
[Link]("India");
[Link]([Link]("India"));
}
}