Write a main program that inserts N random int keys (so the type of the keys in Integer and the type of the values is also Integer) into a separate chaining hash map and then finds the shortest, longest and average bucket lengths, for N = 10^2, 10^3, 10^4, and 10^5 (you may not be able to do 10^5 it might take too long to run).

Tabulate and explain your new results are they as you expect?

Note: the values are not important here so just make the value for a key equal to 1.

Code:

public class KVP< K, V>

{

public K key;

public V value;

public KVP(K key, V value)

{

this.key = key;

this.value = value;

}

@Override

public String toString()

{

return "KVP{" + "key=" + key + ", value=" + value + '}';

}

}

Code:

public interface IKVStore

{

void put(K key, V value);

V get(K key);

}

Code:

public class MyHashMap implements IKVStore

{

private static final int DEFAULT_NUM_BUCKETS = 13;

// an array of list of key-value pairs

private LinkedList>[] buckets;

private int N;

private int factor;

public MyHashMap(int M, int factor)

{

this.factor = factor;

this.buckets = new LinkedList[ M ];

for (int i = 0; i < buckets.length; i++)

{

buckets[i] = new LinkedList<>();

}

N = 0;

}

public MyHashMap()

{

this(DEFAULT_NUM_BUCKETS, 2);

}

private int chooseBucket(K key)

{

int h = key.hashCode();

return Math.abs(h) % buckets.length;

}

public V get(K key)

{

// choose the bucket for the key

int b = chooseBucket(key);

LinkedList> bucket = buckets[b];

// scan the b-th bucket for the key

for (KVP pair : bucket)

{

if (pair.key.equals(key))

{

return pair.value;

}

}

// the key is not in the bucket

return null;

}

public void put(K key, V value)

{

if (N > this.factor * buckets.length)

{

// THIS CODE DOES THE WRONG THING

System.out.println("RESIZING");

// need more buckets

LinkedList[] newBuckets = new LinkedList[ buckets.length * 2 ];

for (int i = 0; i < newBuckets.length; i++)

{

newBuckets[i] = new LinkedList<>();

}

for (int i = 0; i < buckets.length; i++)

{

newBuckets[i] = buckets[i];

}

this.buckets = newBuckets;

}

// choose the bucket for the key

int b = chooseBucket(key);

LinkedList> bucket = buckets[b];

// scan the b-th bucket for the key

for (KVP pair : bucket)

{

if (pair.key.equals(key))

{

// change the value

pair.value = value;

return;

}

}

// the key is not in the bucket

N++;

bucket.add(new KVP<>(key, value));

}

public void printListLengths()

{

for (int i = 0; i < buckets.length; i++)

{

System.out.println(i + " = " + buckets[i].size());

}

}

public boolean containsKey(K key){

// Choose the corresponding bucket

int b = chooseBucket(key);

LinkedList> bucket = buckets[b];

// Check each key value pair in the bucket

for(KVP pair : bucket){

// If required key is found

if(pair.key.equals(key)){

// Return true

return true;

}

}

return false;

}

// Function to delete the key

public void delete(K key){

// Choose the corresponding bucket

int b = chooseBucket(key);

LinkedList> bucket = buckets[b];

// For each key value pair in th bucket

for(KVP pair : bucket){

// If the key found

if(pair.key.equals(key)){

// Make it as null

key=null;

}

}

}

public static void main(String[] args)

{

}

}