Hash Table

In this section, we will implement naive simple HashMap here which utilised java default array (bucket) and linked list.

We first define the buckets and linked list (ArrayList). The linked list is almost similar with our previous implementation of ArrayList using single linked list but this has less functionality. In here we only define 10 buckets but the real implementation will have the number as variable and can be extended.

class SSEHashMap{

    private SSELinkedList[] buckets = new SSELinkedList[10];
    int bucketHash = 10;

    private class SSELinkedList{
        private SSELinkedListInternal head;
        private SSELinkedListInternal tail;

        private class SSELinkedListInternal{
            private String key;
            private String val;
            private SSELinkedListInternal next;
            public SSELinkedListInternal(String key, String val){
                this.key = key;
                this.val = val;
                this.next = null;
            }
        }

        public SSELinkedList(String key, String val){
            SSELinkedListInternal sseLinkedListInternal = new SSELinkedListInternal(key, val);
            head = sseLinkedListInternal;
            tail = sseLinkedListInternal;
        }

        public void add(String key, String val){
            SSELinkedListInternal sseLinkedListInternal = head;
            boolean found = false;
            while(sseLinkedListInternal != null){
                if (sseLinkedListInternal.key.equals(key)){
                    sseLinkedListInternal.val = val;
                    found = true;
                }
                sseLinkedListInternal = sseLinkedListInternal.next;
            }
            if (!found) {
                SSELinkedListInternal newSseLinkedListInternal = new SSELinkedListInternal(key, val);
                tail.next = newSseLinkedListInternal;
                tail = newSseLinkedListInternal;
            }
        }

        public String get(String key) {

            SSELinkedListInternal sseLinkedListInternal = head;
            while(sseLinkedListInternal != null){
                if (sseLinkedListInternal.key.equals(key)){
                    return sseLinkedListInternal.val;
                }
                sseLinkedListInternal = sseLinkedListInternal.next;
            }

            return null;

        }
    }
}

Next we will implement add function. this function should be O(1) on average but if there is collision then it could be O(n).

     public void add(String key, String value){

        if (buckets[Math.abs(key.hashCode()) % bucketHash] != null){
            buckets[Math.abs(key.hashCode()) % bucketHash].add(key, value);
        }else{
            SSELinkedList sseLinkedList = new SSELinkedList(key, value);
            buckets[Math.abs(key.hashCode()) % bucketHash]= sseLinkedList;
        }
    }

Next we will implement find function. this function should be O(1) on average but if there is collision then it could be O(n).

     public String find(String key){
        if ( buckets[Math.abs(key.hashCode()) % bucketHash] == null){
            return null;
        }

        return buckets[Math.abs(key.hashCode()) % bucketHash].get(key);
    }

The usefulness of Hash table is that on average it is O(1) if there isnt much collision.

Note: This implementation is naive and simple, haven't been thoroughly tested, please do not use in production, it is meant for simple explanation only. And also there can be better implementation.

You can try to run the code here:

Run on jdoodle