Scribd
Upload
2 views4 pages

HashMap Implementation

The document provides a Java implementation of a HashMap class using generics, which includes methods for adding, retrieving, removing key-value pairs, and checking for keys. It features a rehashing mechanism to manage bucket overflow and maintains an array of linked lists for storing nodes. The main method demonstrates the usage of the HashMap with example key-value pairs.

Uploaded by

rahulkrdeep1289
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views4 pages

HashMap Implementation

The document provides a Java implementation of a HashMap class using generics, which includes methods for adding, retrieving, removing key-value pairs, and checking for keys. It features a rehashing mechanism to manage bucket overflow and maintains an array of linked lists for storing nodes. The main method demonstrates the usage of the HashMap with example key-value pairs.

Uploaded by

rahulkrdeep1289
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

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"));
}
}

You might also like