HashTableChaining

                Never    
Java
       
/*
 * Implements hashtable that resolves collision by chaining;
 * Here, we do not allow resizing of table, all tables will be of size 97;
 * Methods available for this class as per methods in Symbol Table in lecture
 */

import java.util.LinkedList;

public class HashTable <K, V> {

    private LinkedList<Pair<K,V>>[] table;
    private int size;

    //resizing not allowed
    HashTable() {
        this.table = new LinkedList[97];
        this.size = 0;
    }

    //calculates where the pair is to be inserted in the table
    private int hash(K key) {
        return key.hashCode() % 97;
    }

    //insert here is no longer O(1) as we check for duplicate keys
    void insert(K key, V value) {
        //TODO
        Pair<K,V> toInsert = new Pair<>(key,value);
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }
        if (!contains(key)) {
            table[index].add(toInsert);
            size++;
        } else {
            //pair is equal if they have same key
            table[index].remove(new Pair(key, null));
            table[index].add(toInsert);
        }
    }

    //returns null if key is not inside
    V search(K key) {
        //TODO
        int index = hash(key);
        if (table[index] == null) return null;
        V value = null;
        for (int i = table[index].size() - 1; i >= 0; i--) {
            if (table[index].get(i).key.equals(key)) {
                value = table[index].get(i).value;
                break;
            }
        }
        return value;
    }

    //delete the key
    void delete(K key) {
        //TODO
        int index = hash(key);
        if (table[index] != null) {
            if (contains(key)) {
                table[index].remove(new Pair(key,null));
                size --;
            }
        }
    }

    boolean contains(K key) {
        //TODO
        int index = hash(key);
        return table[index].contains(new Pair(key,null));
    }

    //returns number of distinct (k,v) pairs
    int size() {
        return size;
    }

    public static void main(String[] args) {
        HashTable<Integer, Integer> hi = new HashTable<>();
        hi.insert(5,5);
        hi.insert(5,7);
        hi.insert(5,9);
        hi.insert(9,9);
        System.out.println(hi.size());
        System.out.println(hi.search(5));
        hi.delete(5);
        System.out.println(hi.search(5));
        System.out.println(hi.search(9));
    }

}

Raw Text