dsa

Data Structures & Algorithms - Spring 2018
Log | Files | Refs | README

HashTable.java (3778B)

      1 package lab12;
      2 // ********************************************************
      3 // Hash table implementation.
      4 // Assumption: A table contains unique items(at most one
      5 //             item with a given search key at any time)
      6 // *********************************************************
      7 
      8 public class HashTable<K, V> implements HashTableInterface<K,V> {
      9     private ChainNode[] table;     // hash table
     10     private int size = 0;          // size of table, i.e. number of entries ((key,value) associations)
     11 
     12     public HashTable() {
     13         table = new ChainNode[3];
     14     }  // end default constructor
     15 
     16     // table operations
     17     public boolean tableIsEmpty() {
     18         return size==0;
     19     }  // end tableIsEmpty
     20 
     21     public int tableLength() {
     22         return size;
     23     }  // end tableLength
     24 
     25 
     26 //implement the following 4 methods
     27 
     28     public boolean tableInsert(K key, V value) //inserts  association (key,value) only if key is not already in HashTable and returns true; returns false if the key already has an associated value in HashTable and does not insert
     29     {
     30         int index;
     31         boolean duplicate = false;
     32         boolean nullValue = false;
     33         index = hashIndex(key);
     34 
     35         ChainNode<K, V> curr = table[index];
     36         ChainNode<K, V> newNode = new ChainNode<>(key, value, null);
     37         if (curr != null) {
     38            while (!nullValue && !duplicate) {
     39                 if (curr.getKey().equals(key)) {
     40                     duplicate = true;
     41                 }
     42                 else if (curr.getNext() == null) {
     43                     nullValue = true;
     44                 }
     45                 else {
     46                     curr = curr.getNext();
     47                 }
     48            }
     49         }
     50         else {
     51             table[index] = newNode;
     52             size++;
     53             return true;
     54         }
     55         if (!duplicate) {
     56             System.out.println("COLLISION");
     57             curr.setNext(newNode);
     58             System.out.println("COLLISION RESOLVED");
     59             size++;
     60             return true;
     61         }
     62         return false;
     63     }
     64 
     65     public boolean tableDelete(K searchKey) //deletes the key and its association from the HashTable if it is in the table and returns true; returns false if key is not in the HashTable
     66     {
     67         int index;
     68         index = hashIndex(searchKey);
     69         ChainNode<K, V> node = table[index];
     70 
     71         if (node.getKey().equals(searchKey)) {
     72             table[index] = node.getNext();
     73             size--;
     74             return true;
     75         }
     76         while (node.getNext() != null) {
     77             if (node.getNext().getKey().equals(searchKey)) {
     78                 node.setNext(node.getNext().getNext());
     79                 size --;
     80                 return true;
     81             }
     82             node = node.getNext();
     83         }
     84         return false;
     85     }
     86 
     87     public V tableRetrieve(K searchKey) //returns the value associated with searchkey in HashTable or null if there is no association
     88     {
     89         int index;
     90         index = hashIndex(searchKey);
     91         ChainNode<K, V> node = table[index];
     92 
     93         while (node != null) {
     94             if (searchKey.toString().equals(node.getKey())) {
     95                 return node.getValue();
     96             }
     97             else {
     98                 node = node.getNext();
     99             }
    100         }
    101         return null;
    102     }
    103 
    104     public int hashIndex(K key) {
    105         int horner = 0;
    106         int mapKey;
    107         int resultKey;
    108         int length = key.toString().length();
    109         int [] characters = new int[length];
    110 
    111         for(int i = 0; i < length; i++) {
    112             mapKey = key.toString().charAt(i) - ('A') + 1;
    113             characters[i] = mapKey;
    114             horner += characters[i] << ((length - 1 - i) * 5);
    115         }
    116         resultKey = horner % table.length;
    117         return resultKey;
    118     }
    119 }  // end HashTable
    120 
    121