The Algorithms logo
The Algorithms
AboutDonate

Hash Map

R
R
k
L
and 6 more contributors
package com.thealgorithms.datastructures.hashmap.hashing;

public class HashMap {

    private int hsize;
    private LinkedList[] buckets;

    public HashMap(int hsize) {
        buckets = new LinkedList[hsize];
        for (int i = 0; i < hsize; i++) {
            buckets[i] = new LinkedList();
            // Java requires explicit initialisaton of each object
        }
        this.hsize = hsize;
    }

    public int hashing(int key) {
        int hash = key % hsize;
        if (hash < 0) {
            hash += hsize;
        }
        return hash;
    }

    public void insertHash(int key) {
        int hash = hashing(key);
        buckets[hash].insert(key);
    }

    public void deleteHash(int key) {
        int hash = hashing(key);

        buckets[hash].delete(key);
    }

    public void displayHashtable() {
        for (int i = 0; i < hsize; i++) {
            System.out.printf("Bucket %d :", i);
            System.out.println(buckets[i].display());
        }
    }

    public static class LinkedList {

        private Node first;

        public LinkedList() {
            first = null;
        }

        public void insert(int key) {
            if (isEmpty()) {
                first = new Node(key);
                return;
            }

            Node temp = findEnd(first);
            temp.setNext(new Node(key));
        }

        private Node findEnd(Node n) {
            if (n.getNext() == null) {
                return n;
            } else {
                return findEnd(n.getNext());
            }
        }

        public Node findKey(int key) {
            if (!isEmpty()) {
                return findKey(first, key);
            } else {
                System.out.println("List is empty");
                return null;
            }
        }

        private Node findKey(Node n, int key) {
            if (n.getKey() == key) {
                return n;
            } else if (n.getNext() == null) {
                System.out.println("Key not found");
                return null;
            } else {
                return findKey(n.getNext(), key);
            }
        }

        public void delete(int key) {
            if (!isEmpty()) {
                if (first.getKey() == key) {
                    first = null;
                } else {
                    delete(first, key);
                }
            } else {
                System.out.println("List is empty");
            }
        }

        private void delete(Node n, int key) {
            if (n.getNext().getKey() == key) {
                if (n.getNext().getNext() == null) {
                    n.setNext(null);
                } else {
                    n.setNext(n.getNext().getNext());
                }
            } else {
                delete(n.getNext(), key);
            }
        }

        public String display() {
            return display(first);
        }

        private String display(Node n) {
            if (n == null) {
                return "null";
            } else {
                return n.getKey() + "->" + display(n.getNext());
            }
        }

        public boolean isEmpty() {
            return first == null;
        }
    }

    public static class Node {

        private Node next;
        private int key;

        public Node(int key) {
            next = null;
            this.key = key;
        }

        public Node getNext() {
            return next;
        }

        public int getKey() {
            return key;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }
}