Task 9.1 - Associative Array

An associative array (sometimes called map or dictionary) is an abstract data structure which stores a collection of (key,value) pairs, where each key is unique. Implement such a data structure using a hash table. You may assume the keys and values are only strings, but you do not know which kind of strings are added nor in which sequence they are added, accessed or modified. You are free to select how to deal with collisions in the hash table: any chaining or open addressing strategy is fine for your own implementation. Your data structure should provide the following operations:

  • add a key-value pair to the collection,
  • remove a key-value pair from the collection,
  • modify the value of an existing key,
  • look up the value of a given key.
  • As there are two basic types of implementations for this we will cover the chaining as well as open addressing (with linear probing).

    To get you started consider this null-functionality class:

    class Hash {
      public Hash () {
      }
      private int hash (String k) {
        return 0;
      }
      public boolean add (String k, String v) {
        return false;
      }
      public boolean modify (String k, String v) {
        return false;
      }
      public boolean del (String k) {
        return false;
      }
      public String get (String k) {
        return null;
      }
      public void print_all () {
        return;
      }
      public static void main (String[] args) {
        Hash h = new Hash ();
        if (!h.add("First", "1")) {
          System.out.println ("Failed 1");
        }
        if (!h.add("Second", "2")) {
          System.out.println ("Failed 2");
        }
        h.modify ("Second", "22");
        h.print_all ();
        h.del ("First");
        if (!h.add("First", "3")) {
          System.out.println ("Failed 3");
        }
        h.print_all ();
        h.del ("Second");
        h.del ("Third");
      }
    }