HashMap.java

package 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());
        }
      }
    }

    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;
    }
  }
}