JAVA   66

HashTable

Guest on 3rd July 2022 05:35:38 AM

  1. public class Lab6 {
  2.  
  3.   final static int TABLE_SIZE = 7;
  4.  
  5.   public static void main(String[] args) {
  6.    
  7.     HashTable T = new HashTable(TABLE_SIZE);
  8.    
  9.     T.initializeTable();
  10.     T.insert('J');
  11.     T.insert('N');
  12.     T.insert('S');
  13.     T.insert('X');
  14.     T.insert('B');
  15.     T.insert('W');
  16.    
  17.     T.printTable();
  18.    
  19.     System.out.println("Table printed above.");
  20.     System.out.println();
  21.    
  22.     T.searchAndPrint('W');
  23.     T.searchAndPrint('N');      
  24.     T.searchAndPrint('A');      
  25.    
  26.   }     // end main
  27.  
  28. }       // end Lab6
  29.  
  30. /* ------------------------------------------------------------------------------------------ */
  31.  
  32. class HashTableNode {
  33.   char key;
  34.   HashTableNode link;
  35. }       //end class
  36.  
  37. /* ------------------------------------------------------------------------------------------ */
  38.  
  39. class HashTable {
  40.  
  41.   HashTableNode[] entryArray;
  42.  
  43.   int tableSize;
  44.  
  45.   // a single argument constructor is included
  46.  
  47.   HashTable(int sizeOfTable) {
  48.    
  49.     tableSize = sizeOfTable;
  50.     entryArray = new HashTableNode[sizeOfTable];
  51.    
  52.   }
  53.  
  54.   /* the HashTable methods follow */  
  55.   /* ------------------------------------------------------------------------------------- */
  56.  
  57.   // h1(K) is the hash function that maps a character key K into the index of a table entry
  58.  
  59.   int h1(char K) {     // the hash function
  60.     return (1+ (int)(K) - (int)('A')) % tableSize;
  61.   }     // end h1
  62.  
  63.   /* ------------------------------------------------------------------------------------- */
  64.  
  65.   void initializeTable() {
  66.    
  67.     int i;
  68.    
  69.     for ( i= 0; i < tableSize; i++) entryArray[i] = null;
  70.    
  71.   }     //end initializeTable
  72.  
  73.   /* --------------------------------------------------------------------------------------- */
  74.   /* refine the following Program Strategy into executable Java code   */
  75.  
  76.   HashTableNode insert1(char K, HashTableNode L) {
  77.    
  78.     HashTableNode N;
  79.    
  80.     (Insert a new HashTableNode with key K in the sorted list L)
  81.    
  82.   }       //end insert1
  83.  
  84. /* ------------------------------------------------------------------------------------- */
  85.  
  86. void insert(char K) {
  87.  
  88.   // Call a recursive auxiliary insert1 function to insert key K on the
  89.   // list pointed to by entryArray[h1(K)] in alphabetical order of the keys
  90.  
  91.   // update entryArray[h1(K)] to point to new list
  92.   entryArray[h1(K)] = insert1(K,entryArray[h1(K)]);  
  93.  
  94. }       //end insert
  95.  
  96. /* ------------------------------------------------------------------------------------- */
  97.  
  98. HashTableNode find1(char K, HashTableNode L) {
  99.  
  100.   (Walk through the sorted list L)
  101.   (    Return null if K is not on the list)
  102.   (    Otherwise return the HashTableNode that contains K)
  103.  
  104. } //end find1
  105.  
  106. /* ------------------------------------------------------------------------------------- */
  107.  
  108. HashTableNode find(char K) {
  109.  
  110.   // use the recursive auxiliary function find1(K,L) to search for and  
  111.   // return a pointer to the node of list L containing key K, or return
  112.   // null if there was no node on list L containing a key K
  113.  
  114.   return find1(K, entryArray[h1(K)]);  // returns null if K was not on list
  115.  
  116. }       //end find
  117.  
  118. /* ------------------------------------------------------------------------------------- */
  119.  
  120. void printTable() {
  121.  
  122.   int i;  HashTableNode L;
  123.  
  124.   for (i = 0; i < tableSize; i++) {
  125.     L = entryArray[i];
  126.     System.out.print("T[" + i + "] = (");
  127.     while (L != null) {
  128.       System.out.print(L.key);
  129.       System.out.print("-"+ (1 + (int)(L.key) - (int) ('A')));
  130.       if (L.link != null) System.out.print(',');
  131.       L= L.link;
  132.     }
  133.     System.out.println(")");  
  134.   }
  135.   System.out.println();
  136.  
  137. }       //end printTable
  138.  
  139. /* ------------------------------------------------------------------------------------- */
  140.  
  141. void searchAndPrint(char K) {
  142.  
  143.   HashTableNode N;
  144.  
  145.   System.out.println("Searching for key '" + K + "' in Table T");
  146.   N = find(K);
  147.  
  148.   if (N != null) {
  149.     System.out.println("   Found " + N.key);
  150.   } else {
  151.     System.out.println("   key '" + K + "' not Found in Table T");
  152.   }
  153. }       //end searchAndPrint
  154.  
  155. /* ------------------------------------------------------------------------------------- */
  156.  
  157. }       //end class Lab6

Raw Paste

Login or Register to edit or fork this paste. It's free.