public class LinearStringHash extends StringHash { private int N; private Entry[] table; public LinearStringHash(int n) { N = firstPrimeBiggerThan((int)1.5 * n); table = new Entry[N]; for (int i = 0; i < N; i++) { table[i] = new Entry(); } //System.out.println("N = "+N); } private int h(String s) { int k = 0; for (int i = 0; i < s.length(); i++) { k = (k*256 + s.charAt(i))%N; } return k; } public void clear(int nKeysExpected) { N = firstPrimeBiggerThan((int)1.5 * nKeysExpected); table = new Entry[N]; for (int i = 0; i < N; i++) { table[i] = new Entry(); } //System.out.println("N = "+N); } public void insert(String key) throws Error { //System.out.println(" *** inserting ["+key+"]"); if (!contains(key)) { int i; int loc = h(key); for (i = 0; i < N && table[loc].isOccupied(); i++) { loc = (loc+1)%N; } if (i < N) { //System.out.println(" ** after "+i+" searches, will insert at location "+loc+", current contents: ["+table[loc].string()+"]"); table[loc].insertEntry(key); //System.out.println(" * inserted ["+table[loc].string()+"]"); } else { //System.out.println(" * could not insert ["+key+"], table full"); //throw new Error("table is full!"); } } else { //System.out.println(" * could not insert ["+key+"], already inserted"); } } public boolean contains(String key) { int loc = h(key); //System.out.println(" *** looking for ["+key+"]"); for (int i = 0; i < N && !table[loc].isEmpty(); i++) { if (table[loc].isOccupied()) { nComparisons++; if (table[loc].equals(key)) { //System.out.println(" * found ["+table[loc].string()+"]"); return true; } } loc = (loc+1)%N; } //System.out.println(" * ["+key+"] not found"); return false; } public String delete(String key) { int loc = h(key); for (int i = 0; i < N && !table[loc].isEmpty(); i++) { if (table[loc].isOccupied()) { nComparisons++; if (table[loc].equals(key)) { //System.out.println(" *** deleting ["+table[loc].string()+"]"); return table[loc].deleteEntry(); } } loc = (loc+1)%N; } return null; }