JavaAlgorithms/DataStructures/HashMap/Hashing/HashMapLinearProbing.java

package DataStructures.HashMap.Hashing;

import java.util.*;

/**
 * This class is an implementation of a hash table using linear probing It uses a dynamic array to
 * lengthen the size of the hash table when load factor > .7
 */
public class HashMapLinearProbing {
  private int hsize; // size of the hash table
  private Integer[] buckets; // array representing the table
  private Integer AVAILABLE;
  private int size; // amount of elements in the hash table

  /**
   * Constructor initializes buckets array, hsize, and creates dummy object for AVAILABLE
   *
   * @param hsize the desired size of the hash map
   */
  public HashMapLinearProbing(int hsize) {
    this.buckets = new Integer[hsize];
    this.hsize = hsize;
    this.AVAILABLE = new Integer(Integer.MIN_VALUE);
    this.size = 0;
  }

  /**
   * The Hash Function takes a given key and finds an index based on its data
   *
   * @param key the desired key to be converted
   * @return int an index corresponding to the key
   */
  public int hashing(int key) {
    int hash = key % hsize;
    if (hash < 0) {
      hash += hsize;
    }
    return hash;
  }

  /**
   * inserts the key into the hash map by wrapping it as an Integer object
   *
   * @param key the desired key to be inserted in the hash map
   */
  public void insertHash(int key) {
    Integer wrappedInt = new Integer(key);
    int hash = hashing(key);

    if (isFull()) {
      System.out.println("Hash table is full");
      return;
    }

    for (int i = 0; i < hsize; i++) {
      if (buckets[hash] == null || buckets[hash] == AVAILABLE) {
        buckets[hash] = wrappedInt;
        size++;
        return;
      }

      if (hash + 1 < hsize) {
        hash++;
      } else {
        hash = 0;
      }
    }
  }

  /**
   * deletes a key from the hash map and adds an available placeholder
   *
   * @param key the desired key to be deleted
   */
  public void deleteHash(int key) {
    Integer wrappedInt = new Integer(key);
    int hash = hashing(key);

    if (isEmpty()) {
      System.out.println("Table is empty");
      return;
    }

    for (int i = 0; i < hsize; i++) {
      if (buckets[hash] != null && buckets[hash].equals(wrappedInt)) {
        buckets[hash] = AVAILABLE;
        size--;
        return;
      }

      if (hash + 1 < hsize) {
        hash++;
      } else {
        hash = 0;
      }
    }
    System.out.println("Key " + key + " not found");
  }

  /** Displays the hash table line by line */
  public void displayHashtable() {
    for (int i = 0; i < hsize; i++) {
      if (buckets[i] == null || buckets[i] == AVAILABLE) {
        System.out.println("Bucket " + i + ": Empty");
      } else {
        System.out.println("Bucket " + i + ": " + buckets[i].toString());
      }
    }
  }

  /**
   * Finds the index of location based on an inputed key
   *
   * @param key the desired key to be found
   * @return int the index where the key is located
   */
  public int findHash(int key) {
    Integer wrappedInt = new Integer(key);
    int hash = hashing(key);

    if (isEmpty()) {
      System.out.println("Table is empty");
      return -1;
    }

    for (int i = 0; i < hsize; i++) {
      try {
        if (buckets[hash].equals(wrappedInt)) {
          buckets[hash] = AVAILABLE;
          return hash;
        }
      } catch (Exception E) {
      }

      if (hash + 1 < hsize) {
        hash++;
      } else {
        hash = 0;
      }
    }
    System.out.println("Key " + key + " not found");
    return -1;
  }

  private void lengthenTable() {
    buckets = Arrays.copyOf(buckets, hsize * 2);
    hsize *= 2;
    System.out.println("Table size is now: " + hsize);
  }

  /**
   * Checks the load factor of the hash table if greater than .7, automatically lengthens table to
   * prevent further collisions
   */
  public void checkLoadFactor() {
    double factor = (double) size / hsize;
    if (factor > .7) {
      System.out.println("Load factor is " + factor + ",  lengthening table");
      lengthenTable();
    } else {
      System.out.println("Load factor is " + factor);
    }
  }

  /**
   * isFull returns true if the hash map is full and false if not full
   *
   * @return boolean is Empty
   */
  public boolean isFull() {
    boolean response = true;
    for (int i = 0; i < hsize; i++) {
      if (buckets[i] == null || buckets[i] == AVAILABLE) {
        response = false;
        break;
      }
    }
    return response;
  }

  /**
   * isEmpty returns true if the hash map is empty and false if not empty
   *
   * @return boolean is Empty
   */
  public boolean isEmpty() {
    boolean response = true;
    for (int i = 0; i < hsize; i++) {
      if (buckets[i] != null) {
        response = false;
        break;
      }
    }
    return response;
  }
}