m9 code
unknown
javascript
20 days ago
2.2 kB
7
Indexable
package hash; import java.util.LinkedList; public class StringTable { private LinkedList<Record>[] buckets; private int nBuckets; public int size; @SuppressWarnings("unchecked") public StringTable(int nBuckets) { this.nBuckets = nBuckets; buckets = new LinkedList[nBuckets]; for (int i = 0; i < nBuckets; i++) { buckets[i] = new LinkedList<Record>(); } size = 0; } public boolean insert(Record r) { int index = toIndex(stringToHashCode(r.key)); LinkedList<Record> bucket = buckets[index]; for (Record existing : bucket) { if (existing.key.equals(r.key)) { return false; } } bucket.add(r); size++; return true; } public Record find(String key) { int index = toIndex(stringToHashCode(key)); LinkedList<Record> bucket = buckets[index]; for (Record r : bucket) { if (r.key.equals(key)) { return r; } } return null; } public void remove(String key) { int index = toIndex(stringToHashCode(key)); LinkedList<Record> bucket = buckets[index]; for (Record r : bucket) { if (r.key.equals(key)) { bucket.remove(r); size--; break; } } } private int toIndex(int hashcode) { return Math.abs(hashcode) % nBuckets; } int stringToHashCode(String key) { int A = 1952786893; int v = A; for (int j = 0; j < key.length(); j++) { char c = key.charAt(j); v = A * (v + (int) c + j) >> 16; } return v; } public String toString() { StringBuilder sb = new StringBuilder(); for(int i = 0; i < nBuckets; i++) { sb.append(i+ " "); if (buckets[i] == null) { sb.append("\n"); continue; } for (Record r : buckets[i]) { sb.append(r.key + " "); } sb.append("\n"); } return sb.toString(); } }
Editor is loading...
Leave a Comment