Question

Hash Tables. (Hint: Diagrams might be helpful for parts a) and b). )

1. When inserting into hash table we insert at an index calculated by the key modulo the array size, what would happen if we instead did key mod (array_size*2), or key mod (array_size/2)? (Describe both cases).
   
   

Theory answer Here

2. Change your hashtable from the labs/assignments to be an array of linkedlists – so now insertion is done into a linkedlist at that index. Implement insertion and search. This dramatically simplifies the implementation because there is no collision resolution, you just add to the linkedlist, and search now goes to the index and then does a linear search. ( my submission is below,, feel free to make changes or create something new!)

   
   public class hashtable
   {

   //inner class hash entry to be added to hash table
   class hashentry
   {
   int key;
   string data;

   //setters and getters
   public hashentry(int key, string data)
   {
   this.key = key;
   this.data = data;
   }
   public int getkey()
   {
   return key;
   }
   public string getdata()
   {
   return data;
   }
   }

   
   int maxSize; // table length
   hashentry[] table; //create array of hash entries

   /*
   *
   *Hash table constructor given size paramter to set the length of the array
   
   *set table to null
   */

   public hashtable(int size)
   {
   maxSize = size;
   table = new hashentry[size];
   for (int i = 0; i < size; i++)
   {
   table[i] = null;
   }
   }

   /*
   * using key, get element at given key parameter, return key to string
   */
   public string retrieve(int key)
   {
   int hash = key % maxSize;
   while (table[hash] != null && table[hash].getkey() != key)
   {
   hash = (hash + 1) % maxSize;
   }
   if (table[hash] == null)
   {
   return "nothing found!";
   }
   else
   {
   return table[hash].getdata();
   }
   }

   /*
   * using string data, get element at given string if it is exact, return hash entry to console
   */
   public void retrievedata(string data)
   {
   for (int i = 1; i <= table.Length; i++)
   {
   try
   {
   if (table[i].getdata().Equals(data) && table[i].getdata() != null && table != null && i <= maxSize)//if we have null entries
   {

   Console.WriteLine("Key value :{0} , Data Value :{1}, Length of Data : {2}", table[i].getkey(), table[i].getdata(), table[i].getdata().Length);
   }
   else
   {
   continue;
   }
   }
   catch { }
   }
   }

   /*
   * checks for open spaces in the table for insertion method
   */

   private bool checkOpenSpace()//checks for open spaces in the table for insertion
   {
   bool isOpen = false;
   for (int i = 0; i < maxSize; i++)
   {
   if (table[i] == null)
   {
   isOpen = true;
   }
   }
   return isOpen;
   }

   
   /*
   * Method to print all elements of the hash array
   * Print all iterates over all the n elements in the container, so it is o(n) operation.
   */

   public void print()
   {
   for (int i = 0; i < table.Length; i++)
   {
   if (table[i] == null && i <= maxSize)//if we have null entries
   {
   continue;//dont print them, continue looping
   }
   else
   {
   Console.WriteLine("Key value :{0} , Data Value :{1}, Length of Data : {2}", table[i].getkey(), table[i].getdata(), table[i].getdata().Length);
   }
   }
   }

   /*
   *Quadratic probe insert is in best case o(1) when location of the hash is empty and in worst
   * case o(n) when it is not empty, so you must loop until you find one that is.
   * if quadratic probe insert is not necessary, it needs to change the pointer to the hash so it is o(1)
   */

   public void quadraticHashInsert(int key, string data)
   {
   // quadratic probing method
   if (!checkOpenSpace())//if no open spaces available
   {
   Console.WriteLine("table is at full capacity!");
   return;
   }

   int j = 0;
   int hash = hash1(key);
   if (hash >= 0)
   {
   while (table[hash] != null && table[hash].getkey() != key && hash>=0)
   {
   j++;
   hash = (hash + j * j) % maxSize;

   // hash = (hash + j * j) % maxSize;
   }

   if (table[hash] == null)
   {
   table[hash] = new hashentry(key, data);
   return;
   }
   }

   }
   private int hash1(int key)
   {
   return key % maxSize;
   }
   private int hash2(int key)
   {
   //must be non-zero, less than array size, ideally odd
   return 5 - key % 5;
   }
   }
   }
   )

Code and Testing here

3. Theory discussion: Don’t try and derive a formal maths answer here, but when should you “grow” on a hashtable like the one in B, given that you no longer really have a load factor as in a regular hash table?

Theory here

Answer 1

Usually we insert into the hash table using key% array_size, however if we insert the values using:

key%array_size*2. there would be less collision since our bucket size now become doubles and thus, there are less chances of collision.

But if we insert using key%array_size/2, the bucket size reduced to half and thus as the size decreases, there would be more collision, Hence more time would be required to fetch the value during retrieval.

For example:

lets take the numbers : 5 , 20, 16, 10, 4

The hash table will be if we insert using key%array_size ( 0,1,2,3,4 in the leftmost side are the index of array of size 5)

0 --> 5 --- 20 --- 10

1 --> 16

2 -->

3 -->

4 --> 4

The hash table will be if we insert using key%array_size*2

0 --> 20 --- 10

1 -->

2 -->

3 -->

4 --> 4

5 --> 5

6 --> 16

7 -->

8 -->

9 -->

The hash table will be if we insert using key%array_size/2 ( since array_size= 5 , therefore 5/2=2 (taking floor value)

0 --> 20 ---16 ---10 --- 4

1 --> 5