Analysis of Algorithms in Java. Please approach this problem using a hash table

Question

Analysis of Algorithms in Java. Please approach this problem using a hash table and pseudo code.

Like a map, a multi-map stores entries that are key-value pair (k, v), where k is the key and v is the value. Whereas a map insists that entries have unique keys, a multi-map allows multiple entries to have the same key, much like an English dictionary, which allows multiple definitions for the same word. That is we will allow a multi-map to contain entries (k, v) and (k, v') having the same key.

Now, design an efficient multi-map data structure for storing n entries whose m distinct keys having distinct hash code, and m < n. Your data structure should perform the following operation in O(1) time.

get(k) : return a collection of all values associated with key k

put(k, v) add a new entry to your multi-map

remove(k, v) remove an entry

removeAll(k)

Explanation / Answer

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;

public class MultiMap
{
  
Map multiMap = null;

public MultiMap()
{
// here each key is associated with List having multiple values
multiMap = new Hashtable<Object, List<Object>>();
}
// Update the list object for corresponding key
public void putObjects(Object key, Object value)
{
List<Object> myKeyList = (List<Object>) multiMap.get(key);
if (myKeyList == null)
{
myKeyList = new ArrayList<Object>();
multiMap.put(key, myKeyList);
}
myKeyList.add(value);
}
//fetch list of values from hash table based on key
public List<Object> get(Object key)
{
List<Object> myKeyList = (List<Object>) multiMap.get(key);
if (myKeyList == null)
{
return null;
}
return myKeyList;
}
//Remove key from hashtable
public boolean removeAll(Object key)
{
boolean isSuccess = false;
List<Object> myKeyList = (List<Object>) multiMap.get(key);
if (myKeyList == null)
{
return isSuccess;
}
  
Object removed = multiMap.remove(key);
if(removed!=null)
{
isSuccess = true;
}
return isSuccess;
}
//Remove corresponding value from key
public boolean remove(Object key,Object value)
{
boolean isSuccess = false;
List<Object> myKeyList = (List<Object>) multiMap.get(key);
if (myKeyList == null)
{
return isSuccess;
}
  
Object removed = myKeyList.remove(myKeyList.indexOf(value));
if(removed!=null)
{
isSuccess = true;
}
return isSuccess;
}

}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.