Implement HashMap in Java

private class HMNode{
K key;
V value;
HMNode(K key, V value){
this.key=key;
this.value=value;
}
}
public static class HashMap<K,V>{
private class HMNode{
K key;
V value;
HMNode(K key, V value){
this.key=key;
this.value=value;
}
}
private int size=n;
private LinkedList<HMNode>[] buckets; //--> length of bucket= N
public HashMap(){
size=0;
initbuckets(8);
}
private initbuckets(int N){
buckets= new LinkedList[N];
for(int i=0;i<N;i++){
buckets[i] =new LinkedList();
}
}
}
private int hashfn(K key){
int hc= key.hashcode();
return Math.abs(hc)%buckets.length;
}
public int getIndexWithinBucket(K key, int bi){
int di=0;
for(HMNode node: buckets[bi]){
if(node.key.equals(key){
return di;
}
di++;
}
return -1;
}
public void put(K key, V value){
int bi = hashfn(key);
int idx = getIndexWithinBucket(key,bi);
if(di!=-1){
HMNode node = buckets[bi].get(idx);
node.value= value;
}
else{
HMNode node = new HMNode(key,value);
buckets[bi].add(node);
size++;
}
double lambada = size*1.0/buckets.length;
if (lambda>2.0) {
rehash();
//here 2.0 is threshold;
}

}
public void rehash(){
LinkedList<HMNode> temp[] = buckets;
buckets= initbuckets(2*buckets.length);
int size=0;
for(int i=0;i<temp.length;i++){
for(HMNode node: temp[i]){
put(node.key,node.value);
}
}
}
public V getKey(K key) throws Exception{
int bi = hashfn(key);
int idx = getIndexWithinBucket(key,bi);
if(idx!=-1){
HMNode node = buckets[bi].get(idx);
return node.value
}
else return null;
}
public boolean containsKey(K key) throws Exception{
int bi = hashfn(key);
int idx = getIndexWithinBucket(key,bi);
if(idx==-1) return false;
else return true;
}
public V remove(K key) throws Exception{
int bi = hashfn(key);
int idx = getIndexWithinBucket(key,bi);
if(idx!=-1){
HMNode node = buckets[bi].remove(idx);
size--;
return node.value
}
else return null;
}
public int size(){
return size;
}
public ArrayList<K> keySet(){
ArrayList<K> keys= new ArrayList();
for(int i=0;i<buckets.length;i++){
for(HMNode node: buckets[i]){
keys.add(node.key);
}
}
return keys;
}

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Strategic Success with Microservices

AWS — basics

How to get accepted into the AWS Community Builders Program

Learn some Sorting Algorithms

Common coding mistakes you should avoid in the exam.

In a Jam About JAMStack

Implementing a Trie in Python (in less than 100 lines of code)

Thoughts on building software models

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abhinay Gupta

Abhinay Gupta

More from Medium

CWE-248: Uncaught Exception in Java

Install Minikube in Ubuntu

Add, Verify or Remove Digital Signature in PowerPoint in Java

How to Set Up Real-Time SDK Java Application with Maven on the Eclipse IDE