Extend your implementation from Question 1 to include map resizing, doubling the
ID: 3740684 • Letter: E
Question
Extend your implementation from Question 1 to include map resizing, doubling the number of buckets, M, whenever the number of keys in the map is greater than 2M. Note: some care is needed in coding the resizing routine. If you do it wrong you will find that inserting 106 (or perhaps 107 ) entries into the map in Q4 will take a very long time. With care re-sizing can be made quite efficient.
Code
Code
public class MyHashMap<K, V> implements IKVStore<K, V>
{
private static final int DEFAULT_NUM_BUCKETS = 13;
// an array of list of key-value pairs
private LinkedList<KVP<K, V>>[] 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<KVP<K, V>> bucket = buckets[b];
// scan the b-th bucket for the key
for (KVP<K, V> 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 * this.factor ];
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<KVP<K, V>> bucket = buckets[b];
// scan the b-th bucket for the key
for (KVP<K, V> 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<KVP<K, V>> bucket = buckets[b];
// Check each key value pair in the bucket
for(KVP<K, V> 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<KVP<K, V>> bucket = buckets[b];
// For each key value pair in th bucket
for(KVP<K, V> pair : bucket){
// If the key found
if(pair.key.equals(key)){
// Make it as null
key=null;
}
}
}
}
Explanation / Answer
public class MyHashMap<K, V> implements IKVStore<K, V>
{
private static final int DEFAULT_NUM_BUCKETS = 13;
// an array of list of key-value pairs
private LinkedList<KVP<K, V>>[] 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<KVP<K, V>> bucket = buckets[b];
// scan the b-th bucket for the key
for (KVP<K, V> 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 * this.factor ];
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<KVP<K, V>> bucket = buckets[b];
// scan the b-th bucket for the key
for (KVP<K, V> 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<KVP<K, V>> bucket = buckets[b];
// Check each key value pair in the bucket
for(KVP<K, V> 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<KVP<K, V>> bucket = buckets[b];
// For each key value pair in th bucket
for(KVP<K, V> pair : bucket){
// If the key found
if(pair.key.equals(key)){
// Make it as null
key=null;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.