m9 code

 avatar
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