CS1103 Exercise Unit 5 - Implement hash tables from scratch

Questions

Write an implementation of hash tables from scratch. Define the following methods: get(key), put(key,value), remove(key), containsKey(key), and size().

1. Codes

HashTable.java

/**
 * This program is an implementation of hash tables from scratch,
 * It includes the following methods: get(key), put(key,value), remove(key), containsKey(key), and size()
 */
public class HashTable {
    /**
     * HashMap is implemented as an HashTable
     * HashTable is implemented as arrays of linked lists
     * Create a Node a hold the key and value
     */
    private static class LinkedListNode {
        String key;
        String value;
        LinkedListNode next;
    }

    /**
     * HashTable is implemented as arrays of linked lists
     */
    private LinkedListNode[] hashTableArray;


    /**
     * The size of the hashTable
     */
    private int count;


    /**
     * A constructor that initializes the hashTable with a size of 128.
     */
    public HashTable() {
        hashTableArray = new LinkedListNode[128];
    }

    /**
     * A constructor with a initialSize parameter
     */
    public HashTable(int initialSize) {
        hashTableArray = new LinkedListNode[initialSize];
    }

    /**
     * Compute the hashCode for the key
     *
     * @param key
     * @return hashCode
     */
    private int hashCode(Object key) {
        return (Math.abs(key.hashCode())) % hashTableArray.length;
    }

    /**
     * get() method
     *
     * @param key
     * @return the value corresponding to the key
     */
    public String get(String key) {
        int bucket = hashCode(key);

        LinkedListNode linkedListNode = hashTableArray[bucket];
        while (linkedListNode != null) {
            if (linkedListNode.key.equals(key))
                return linkedListNode.value;
            linkedListNode = linkedListNode.next;
        }

        // if the hashmap doesn't has the key, return null
        return null;
    }

    /**
     * put() method
     *
     * @param key
     * @param value
     */
    public void put(String key, String value) {

        if (key == null) {
            throw new AssertionError("The key cannot be null");
        }
        int bucket = hashCode(key);

        LinkedListNode linkedListNode = hashTableArray[bucket];

        while (linkedListNode != null) {
            if (linkedListNode.key.equals(key)) {
                break; // If the map contains the key, don't add the key-value pairs
            }
            linkedListNode = linkedListNode.next;
        }

        if (linkedListNode != null) {
            linkedListNode.value = value; // add the value if the key is not null
        } else {
            // The LinkedListis null and add a new node at the head of the LinkedList, which stores the key and value
            LinkedListNode newLinkedListNode = new LinkedListNode();
            newLinkedListNode.key = key;
            newLinkedListNode.value = value;
            newLinkedListNode.next = hashTableArray[bucket];
            hashTableArray[bucket] = newLinkedListNode;
            count++;
        }
    }


    /**
     * remove() method, remove the kay and value in the hashTable
     *
     * @param key
     */
    public void remove(String key) {

        int bucket = hashCode(key);

        if (hashTableArray[bucket] == null) {
            // there is no this key, do nothing
            return;
        }

        // remove the first node
        if (hashTableArray[bucket].key.equals(key)) {
            hashTableArray[bucket] = hashTableArray[bucket].next;
            count--;
            return;
        }

        // the node is not the first node, and traverse the linkedList to remove the node
        LinkedListNode previous = hashTableArray[bucket];
        LinkedListNode current = previous.next;
        //traverse the linkedList from the second node.
        while (current != null && !current.key.equals(key)) {
            current = current.next;
            previous = current;
        }

        // Remove current from the list
        if (current != null) {
            previous.next = current.next;
            count--;
        }
    }


    /**
     * containsKey() method
     *
     * @param key
     * @return true or false
     */
    public boolean containsKey(String key) {

        int bucket = hashCode(key);

        LinkedListNode linkedListNode = hashTableArray[bucket];
        while (linkedListNode != null) {
            if (linkedListNode.key.equals(key))
                return true;
            linkedListNode = linkedListNode.next;
        }

        // the key in not in the hashTable
        return false;
    }


    /**
     * The size of the hashTable,
     *
     * @return count the the key-value pairs in the hashTable
     */
    public int size() {
        return count;
    }
}

TestHashTable.java

import java.util.Scanner;

public class TestHashTable {
    public static void main(String[] args) {
        HashTable table = new HashTable(128);
        String key,value;
        Scanner in = new Scanner(System.in);

        // test the put(key, value)
        System.out.println("------>Test the put(key, value):");
        System.out.print("Please enter the key: ");
        key = in.next();
        System.out.print("Please enter the value: ");
        value = in.next();
        table.put(key, value);

        System.out.println();

        // test the get(key)
        System.out.println("------>Test the get(key):");
        System.out.print("Please enter the key: ");
        key = in.next();
        System.out.println("The value is: " + table.get(key));

        System.out.println();

        // test the remove(key)
        System.out.println("------>Test the remove(key):");
        System.out.print("Please enter the key: ");
        key = in.next();
        table.remove(key);
        System.out.println("The value is removed");

        System.out.println();

        // test the containsKey(key)
        System.out.println("------>Test the containsKey(key):");
        System.out.print("Please enter the key: ");
        key = in.next();
        System.out.println("The result is " + table.containsKey(key));

        System.out.println();

        // test the size()
        System.out.println("------>Test the size():");
        System.out.println("The size is " + table.size());

    }
}

2. Outputs

------>Test the put(key, value):
Please enter the key: a
Please enter the value: 1

------>Test the get(key):
Please enter the key: a
The value is: 1

------>Test the remove(key):
Please enter the key: a
The value is removed

------>Test the containsKey(key):
Please enter the key: a
The result is false

------>Test the size():
The size is 0

Process finished with exit code 0

​

---

This is the ending, thanks for reading.

---