Hash table (94/100)

class SolutionHashTable {
  public Entry[] table;
  public int capacity;

  /**
   * Constructs a new HashTable.
   *
   * Capacity of the hash table can not be 0 or negative.
   *
   * @param capacity
   *     to be used as capacity of the table.
   * @throws IllegalArgumentException
   *     if the input capacity is invalid.
   */
  public SolutionHashTable(int capacity) {
    if (capacity < 1)
      throw new IllegalArgumentException();

    this.table = new Entry[capacity];
    this.capacity = capacity;
  }

  /**
   * Add a new Entry to the hash table,
   * uses linear probing to deal with collisions.
   *
   * Returns false, if the key is null or the table is full.
   *
   * @param key
   *     String representing the key of the entry.
   * @param value
   *     String representing the value of the entry.
   * @return true iff entry has been added successfully, else false.
   */
  public boolean put(String key, String value) {
    // No null keys allowed
    if (null == key)
      return false;

    int hash = hash(key);

    // If key exists, replace value
    if (!isEmpty(hash) && table[hash].getKey() == key) {
      this.table[hash] = new Entry(key, value);
      return true;
    }

    // Otherwise, return false if table is full
    if (this.capacity < 1)
      return false;

    // Otherwise start at entry hash(key)
    // and probe until empty spot is found
    for(int i = 0; i < this.table.length; i++) {
      int idx = (hash + i) % this.table.length;

      if (isEmpty(idx)) {
        this.table[idx] = new Entry(key, value);
        capacity--; // Reduce capacity
        return true;
      }
    }

    return false;
  }

  /**
   * Retrieve the value of the entry associated with this key.
   *
   * Returns null, if the key is null.
   *
   * @param key
   *     String representing the key of the entry to look for.
   * @return value of the entry as String iff the entry with this key is found in the hash table, else null.
   */
  public String get(String key) {
    if (null == key)
      return null;

    String result = null;
    int hash = hash(key);

    // Start at entry hash(key) and probe until..
    for(int i = 0; i < this.table.length; i++) {
      int idx = (hash + i) % this.table.length;

      // empty cell is found
      if (isEmpty(idx))
        break;

      // entry with key is found
      if (this.table[idx].getKey() == key) {
        result = this.table[idx].getValue();
        break;
      }
    }

    return result;
  }

  /**
   * Remove the entry associated with this key from the hash table.
   *
   * Returns false, if the key is null.
   *
   * @param key
   *     String representing the key of the entry to remove.
   * @return true iff the entry has been successfully removed, else false.
   */
  public boolean remove(String key) {
    if (null == key)
      return false;

    int hash = hash(key);

    // Search for entry with hash(key) and replace with DEFUNCT
    for(int i = 0; i < this.table.length; i++) {
      int idx = (hash + i) % this.table.length;

      // entry with key is found
      if (!isEmpty(idx) && this.table[idx].getKey() == key) {
        setDefunct(idx);
        capacity++;
        return true;
      }
    }

    return false;
  }

  /**
   * Takes as input an index and sets the entry in that location as defunct.
   *
   * @param index
   *     The index of the spot that is defunct.
   */
  public void setDefunct(int index) {
    this.table[index] = new Entry(null, null);
  }

    /**
   * Takes as input an index and checks if that location is either null or set as defunct.
   *
   * @param index
   *     The index of the spot that is defunct.
   * @return true iff there is no entry at the given location.
   */
  public boolean isEmpty(int index) {
    return (null == this.table[index] || this.table[index].getKey() == null);
  }

  /**
   * Hashes a string representing a key.
   *
   * @param key
   *     String that needs to be hashed.
   * @return the hashcode of the string, modulo the capacity of the HashTable.
   */
  public int hash(String key) {
    return Math.abs(key.hashCode()) % this.table.length;
  }
}