Question

This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally.

1. Theory.

A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps.

• You can test if a key has a value in the map.

• You can add a new key-value pair to the map.

• You can get the value that is associated with a given key.

• You can change the value that is associated with a given key.

For example, the keys might be String’s that are the English words for numbers. The values might be Integer’s that are the numbers corresponding to those words. If you give the map an English word (like "ten") then you can get back its corresponding number (like 10).
      The maps for this assignment use arrays, and they work by doing linear search on those arrays. As a result, if a map has n pairs, then its operations may need at most O(n) key comparisons. However, there are better ways to implement maps, using data structures that we have not yet discussed in this course. These require only O(log n) or even O(1) key comparisons.

2. Implementation.

You must write a Java class called Map that implements a map. To simplify grading, your class must use the same names for things that are given here. Your class Map must have two generic class parameters, Key and Value, so it looks like this. Here Key is the type of the map’s keys, and Value is the type of the map’s values.

class Map<Key, Value>
{
  ⋮
}

Within the class Map, you must have two private arrays called keys and values. The array keys must be an array whose base type is the class parameter Key. The array values must be an array whose base type is the class parameter Value. Suppose that a key k is found at the index i in the array keys. Then the value associated with k is found at the same index i in the array values. Do not try to use only one array, because that will not work.
      You must also have a private integer variable called count that records how many elements of the arrays are being used. You may also need other private variables that are not mentioned here.
      Your class must have the following methods. Most of them use count, keys, and values somehow. Some methods are public and others are private. The private methods are helpers for the public methods; they may make your code easier to write. Also, any key may be null, and any value may be null. This will affect how you test if keys are equal.

public Map(int length)

Constructor. If length is less than 0 then you must throw an IllegalArgumentException. Otherwise, initialize an empty Map whose keys and values arrays have length elements. (Recall that you must make arrays of Object’s, then cast them to the appropriate types.)

public Value get(Key key)

Search the array keys for an element that is equal to key. If that element is at some index in keys, then return the element at the same index in the array values. If there is no element equal to key in keys, then throw an IllegalArgumentException.

private boolean isEqual(Key leftKey, Key rightKey)

Test if leftKey is equal to rightKey. Either or both may be null. This method is necessary because you must use == when leftKey or rightKey are null, but you must use the equals method when both are not null. (Recall that null has no methods.)

public boolean isIn(Key key)

Test if there is an element in keys that is equal to key.

public void put(Key key, Value value)

Search the array keys for an element that is equal to key. If that element is at some index in keys, then change the element at the same index in values to value. If there is no element in keys that is equal to key, then add key to keys, and add value at the same index in values. If keys and values are full, so you cannot add key and value, then throw an IllegalStateException.

private int where(Key key)

Search the array keys for an element that is equal to key. Return the index of that element. If there is no element equal to key in keys, then return −1.

When you compile your program, you may see the following ‘‘warning’’ messages from javac. Ignore them. As discussed in the lectures, these messages appear because Java does not implement class parameters (the names between < and >) correctly.

Note: your file name.java uses unchecked or unsafe operations.
Note: recompile with -Xlint:unchecked for details.

Answer 1

Implementation in JAVA:

// Class mapnode---------------------------------------------

class Mapnode<K,V> {
   K key;
   V value;
   Mapnode<K,V> next;
   public Mapnode(K key,V value) {
       this.key=key;
       this.value=value;
   }
  
   }

// class Map<K,V>--------------------------------------------------

import java.util.ArrayList;
import java.util.NoSuchElementException;

class Map<K,V> {
     
   ArrayList<Mapnode<K,V>> buckets;
   int size;
   int numbuckets;
     
//   constructer
//   I use ArrayList here to store keys and values so there
//   is no need to give any parameter to constructor regarding size of Array
   public Map()
   {
       numbuckets=20;
       buckets= new ArrayList<Mapnode<K,V>>();
       for(int i=0;i<numbuckets;i++) {
           buckets.add(null);
       }
   }
  
//   will return the index of argumented key

// for simple index of key yor can simply iterate over arraylist and search the key ,

// if find then return the index of that key
   public int getbucketindex(K key) {
       int hashcode=key.hashCode();
       return hashcode % numbuckets;
   }
  
   // to return size of map
   public int size() {
       return size;
   }
  
//   to add new key to value
   public void put (K key, V value) {
       int bucketindex=getbucketindex( key);
       Mapnode<K,V> head=buckets.get(bucketindex);
      
//       first check if key is already present in map
       while(head!=null) {
       if(head.key.equals(key)) {
           head.value=value;
           return;
       }
//       if not present then add it
       head=head.next;
       }
       head=buckets.get(bucketindex);
       Mapnode<K,V> newnode=new Mapnode<K,V>(key,value);
       newnode.next=head;
       buckets.set(bucketindex, newnode);
       size++;
       }
  
   public boolean isIn(K key) {
      
       int bucketindex=getbucketindex( key);
       Mapnode<K,V> head=buckets.get(bucketindex);
      
//       first check if key is already present in map
       while(head!=null) {
       if(head.key.equals(key)) {
//           if present then return true
           return true;
       }
      
    }
//       otherwise return false
       return false;
       }
  
  
   public boolean isEqual(K leftKey, K rightKey) {
      
       if(leftKey==null && rightKey==null ) {
           return leftKey==rightKey;
       }
      
       return leftKey.equals(rightKey);
      
      
   }
  
//   to get value for argumented key
   public V getvalue(K key) throws NoSuchElementException {
       int bucketindex=getbucketindex(key);
       Mapnode<K,V> head=buckets.get(bucketindex);
      
//       traverse and return value for key
       while(head!=null) {
       if(head.key.equals(key)) {
           return head.value;
       }
       head=head.next;
       }
      
       NoSuchElementException e= new NoSuchElementException();
       throw e;
      
              
   }
  
//   to remove key and return value for that key
   public V removekey(K key) {
       int bucketindex=getbucketindex(key);
       Mapnode<K,V> head=buckets.get(bucketindex);
       Mapnode<K,V> prev=null;
       while(head!=null) {
           if(head.key.equals(key)) {
               if(prev==null) {
                   buckets.set(bucketindex, head.next);
               }
               else
               {
                   prev.next=head.next;
               }
               return head.value;
           }
           prev=head;
           head=head.next;
       }
       return null;
   }
  
//   to clear map
   public void clear() {
      
       buckets.clear();
   }

      
  
   }

//-----class Map_Implementation---------------------------------------

public class Map_Implementation {

public static void main(String[] args) {
      
//       implements map class by making object of map class
       Map<String,Integer> map= new Map<>();
      
//       put in map
      
       System.out.println("Put some keys and values in map : ");
       System.out.println("Put Key as New Delhi and value as 2");
      
       map.put("New Delhi", 2);
      
System.out.println("Put Key as Berlin and value as 8");
      
map.put("Berlin", 8);
      
System.out.println("Put Key as WashingtonDC and value as 4");
      
       map.put("WashingtonDC", 4);
      
System.out.println("Put Key as Tokyo and value as 5");
      
       map.put("Tokyo", 5);
      
       System.out.println();
      

System.out.println(" Size of map is : "+ map.size);
      
System.out.println();
      
       System.out.println("Now get values: ");
      
  
       System.out.println("Get value of Tokyo : "+map.getvalue("Tokyo"));
       System.out.println("Get value of Berlin : "+map.getvalue("Berlin"));
      
       System.out.println();
      
       System.out.println("Get Bucket_index of Keys : ");
       System.out.println("will return the index of argumented key not theindex of element");
       System.out.println("Bucket_Index of Tokyo : "+map.getbucketindex("Tokyo"));
       System.out.println("Bucket_Index of WashingtonDC : "+map.getbucketindex("WashingtonDC"));
      
      
  

   }
}

SAMPLE OUTPUT:

If you have any doubt regarding this question please ask me in comments

// THANK YOU:-)