// HashTable: using linear probing and deletion
public class HashTable {
   private String[] h;  // hash table
   private String[] hs; // saved table (illust.)
   private int n = 0;   // # of occupied array elts
   private int m;       // size of hash table
   private int p = 13;  // multiplier in hash

   // HashTable: constructor
   public HashTable(int mIn) {
      m = mIn;
      h  = new String[m];
      hs = new String[m];
      // initialize table to empty entries
      for (int i = 0; i < h.length; i++)
         h[i] = "";
   }

   // lookUpAndInsert: insert if new, return index
   public int lookUpAndInsert(String s) {
      if (n == (m - 1)) { // hash table is full
         System.out.println("Hash table overflow");
         System.exit(1);
      }
      int i = hash(s);
      while (true) {
         if (h[i].length() == 0) { // empty, insert
            h[i] = s;
            n++;
            return i;
         }
         else if (h[i].compareTo(s) == 0) {// found
            return i;
         }
         // look upward for empty entry
         i--; if (i < 0) i += m;
      }
   }

   // hash: simple hash function
   public int hash(String s) {
      int result = 0;
      for (int i = 0; i < s.length(); i++)
         result = (result + s.charAt(i)*p)%m;
      return result;
   }
   
   // delete: very tricky delete
   public void delete(int i) {
      int r, j;
      for (;;) {
         h[i] = "";
         j = i;
         do {
            i--; if (i < 0) i += m;
            if (h[i].compareTo("") == 0) return;
            r = hash(h[i]);
         } while ( (i <= r && r <  j) ||
                   (r <  j && j <  i) ||
                   (j <  i && i <= r) );
         h[j] = h[i];
      }
   }

   public void printTable() {
     System.out.println("\nIndex\tNew\tNewHash\n");
     for (int i = 0; i < h.length; i++) {
         System.out.print(i + "\t" + h[i] + "\t");
         if (h[i].compareTo("") != 0) {
            System.out.print(hash(h[i]));
            if (hash(h[i]) != i)
               System.out.println("*");
            else System.out.println();
         }
         else System.out.println();
      }
   }
   
   public void saveTable() {
      for (int i = 0; i < h.length; i++)
         hs[i] = h[i];
   }
      
   public void printBothTables() {
      System.out.println
         ("\nIndex\tOld\tOldHash\tNew\tNewHash\n");
      for (int i = 0; i < h.length; i++) {
         System.out.print(i + "\t" + hs[i] + "\t");
         if (hs[i].compareTo("") != 0) {
            System.out.print(hash(hs[i]));
            if (hash(hs[i]) != i)
               System.out.print("*");
         }
         System.out.print("\t" + h[i] + "\t");
         if (h[i].compareTo("") != 0) {
            System.out.print(hash(h[i]));
            if (hash(h[i]) != i)
               System.out.println("*");
            else System.out.println();
         }
         else System.out.println();
      }
   }
}

// HashTableTest: test the hash table
public class HashTableTest {
   public static void main(String[] argv) {
      String[] months = 
       {"Jan","Feb","Mar","Apr","May","Jun",
        "Jul","Aug","Sep","Oct","Nov","Dec",
        "Mon","Tue","Wed","Thu","Fri","Sat","Sun"};
      HashTable hashTable = new HashTable(23);
      for (int i = 0; i < months.length; i++)
         hashTable.lookUpAndInsert(months[i]);
      hashTable.printTable();
      hashTable.saveTable();
      hashTable.delete(11);
      hashTable.printBothTables();
   }
}

Here is the output of a runs, first showing
the table after the inserts, and showing the before
and after of a single delete of item 11:

Index   New     NewHash

0       Jul     0
1       Feb     1
2       Aug     2
3       Jun     3
4       Oct     4
5       Sat     7*
6       Fri     8*
7       Sep     7
8       Thu     9*
9       Mon     10*
10      Dec     11*
11      Apr     11
12      Nov     12
13
14
15      Wed     18*
16      Tue     16
17      May     17
18      Mar     18
19      Jan     19
20
21
22      Sun     5*

Index   Old     OldHash New     NewHash

0       Jul     0       Jul     0
1       Feb     1       Feb     1
2       Aug     2       Aug     2
3       Jun     3       Jun     3
4       Oct     4       Oct     4
5       Sat     7*      Sun     5
6       Fri     8*      Sat     7*
7       Sep     7       Sep     7
8       Thu     9*      Fri     8
9       Mon     10*     Thu     9
10      Dec     11*     Mon     10
11      Apr     11      Dec     11
12      Nov     12      Nov     12
13
14
15      Wed     18*     Wed     18*
16      Tue     16      Tue     16
17      May     17      May     17
18      Mar     18      Mar     18
19      Jan     19      Jan     19
20
21
22      Sun     5*

Finally, here is the before and after of a
delete of item 7:

Index   Old     OldHash New     NewHash

0       Jul     0       Jul     0
1       Feb     1       Feb     1
2       Aug     2       Aug     2
3       Jun     3       Jun     3
4       Oct     4       Oct     4
5       Sat     7*      Sun     5
6       Fri     8*      Sat     7*
7       Sep     7       Fri     8*
8       Thu     9*      Thu     9*
9       Mon     10*     Mon     10*
10      Dec     11*     Dec     11*
11      Apr     11      Apr     11
12      Nov     12      Nov     12
13
14
15      Wed     18*     Wed     18*
16      Tue     16      Tue     16
17      May     17      May     17
18      Mar     18      Mar     18
19      Jan     19      Jan     19
20
21
22      Sun     5*