/**
 * 双散列散列表：解决了聚集的问题，但是要求表的大小一定是素数，并且在hash值的计算较复杂
 * 的时候（如串）效率相对线性和平方散列较慢
 */
public class DoubleHashProbingHashTable<AnyType> {
  public DoubleHashProbingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public DoubleHashProbingHashTable(int size) {
    allocateArray(size);
    makeEmpty();
  }

  public void makeEmpty() {
    currentSize = 0;
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  public boolean contains(AnyType x) {
    int currentPos = findPos(x);
    return isActive(currentPos);
  }

  public void insert(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      return;
    }

    array[currentPos] = new HashEntry<>(x, true);
    if (++currentSize > array.length / 2) {
      rehash();
    }
  }

  // 这里需要注意的是currentSize存放的是表中实际元素个数，而不是有效元素个数
  public void remove(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      array[currentPos].isActive = false;
    }
  }

  private static class HashEntry<AnyType> {
    AnyType element;
    boolean isActive;

    HashEntry(AnyType e) {
      this(e, true);
    }

    HashEntry(AnyType e, boolean i) {
      element = e;
      isActive = i;
    }
  }

  private static final int DEFAULT_TABLE_SIZE = 11;

  private HashEntry<AnyType> [] array;  // The array of elements
  private int currentSize;  // The number of occupied cells

  private void allocateArray(int arraySize) {
    array = new HashEntry[arraySize];
  }

  private boolean isActive(int currentPos) {
    return array[currentPos] != null && array[currentPos].isActive;
  }

  private int findPos(AnyType x) {
    int offset = 1;
    int currentPos = myhash(x);

    while (array[currentPos] != null && !array[currentPos].element.equals(x)) {
      currentPos += offset++ * hash2(x);
      if (currentPos >= array.length) {
        currentPos -= array.length;
      }
    }

    return currentPos;
  }

  private int hash2(AnyType x) {
    return  7 - (x.hashCode() % 7);
  }

  private void rehash() {
    HashEntry<AnyType> [] oldArray = array;

    allocateArray(nextPrime(oldArray.length * 2));
    currentSize = 0;

    for (int i = 0; i < oldArray.length; i++) {
      if (null != oldArray[i] && oldArray[i].isActive) {
        insert(oldArray[i].element);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= array.length;
    if (hashVal < 0) {
      hashVal += array.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }

    int sqrtMax = ((int) Math.sqrt(n));
    for (int i = 2; i < sqrtMax; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

/**
 * 平方探测散列表：解决了一次聚集，但是当散列到同一位置的元素二次散列的位置也是一样的，这叫二次聚集
 * （相对最优的算法）
 */
public class QuadraticProbingHashTable<AnyType> {
  public QuadraticProbingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public QuadraticProbingHashTable(int size) {
    allocateArray(size);
    makeEmpty();
  }

  public void makeEmpty() {
    currentSize = 0;
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  public boolean contains(AnyType x) {
    int currentPos = findPos(x);
    return isActive(currentPos);
  }

  public void insert(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      return;
    }

    array[currentPos] = new HashEntry<>(x, true);

    if (++currentSize > array.length / 2) {
      rehash();
    }
  }

  // 这里需要注意的是currentSize存放的是表中实际元素个数，而不是有效元素个数
  public void remove(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      array[currentPos].isActive = false;
    }
  }

  private static class HashEntry<AnyType> {
    AnyType element;
    boolean isActive;

    HashEntry(AnyType e) {

    }

    HashEntry(AnyType e, boolean i) {
      element = e;
      isActive = i;
    }
  }


  private static final int DEFAULT_TABLE_SIZE = 11;

  private HashEntry<AnyType> [] array;
  private int currentSize;

  private void allocateArray(int arraySize) {
    array = new HashEntry[arraySize];
  }

  private boolean isActive(int currentPos) {
    return array[currentPos] != null && array[currentPos].isActive;
  }

  private int findPos(AnyType x) {
    int offset = 1;
    int currentPos = myhash(x);

    while (array[currentPos] != null && !array[currentPos].element.equals(x)) {
      currentPos += offset;
      offset += 2;
      if (currentPos >= array.length) {
        currentPos -= array.length;
      }
    }
    return currentPos;
  }

  private void rehash() {
    HashEntry<AnyType> [] oldArray = array;

    allocateArray(nextPrime(oldArray.length * 2));
    currentSize = 0;

    for (int i = 0; i < oldArray.length; i++) {
      if (null != oldArray[i] && oldArray[i].isActive) {
        insert(oldArray[i].element);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= array.length;
    if (hashVal < 0) {
      hashVal += array.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }

    int sqrtMax = ((int) Math.sqrt(n));
    for (int i = 2; i < sqrtMax; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

/**
 * 线性探测法：缺点是产生冲突的元素会聚集在某一块位置，这叫一次聚集
 */
public class ChainingProbingHashTable<AnyType> {
  public ChainingProbingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public ChainingProbingHashTable(int size) {
    allocateArray(size);
    makeEmpty();
  }

  public void makeEmpty() {
    currentSize = 0;
    for (int i = 0; i < array.length; i++) {
      array[i] = null;
    }
  }

  public boolean contains(AnyType x) {
    int currentPos = findPos(x);
    return isActive(currentPos);
  }

  public void insert(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      return;
    }

    array[currentPos] = new HashEntry<>(x, true);
    if (++currentSize > array.length / 2) {
      rehash();
    }
  }

  // 这里需要注意的是currentSize存放的是表中实际元素个数，而不是有效元素个数
  public void remove(AnyType x) {
    int currentPos = findPos(x);
    if (isActive(currentPos)) {
      array[currentPos].isActive = false;
    }
  }

  private static class HashEntry<AnyType> {
    AnyType element;
    boolean isActive;

    HashEntry(AnyType e) {
      this(e, true);
    }

    HashEntry(AnyType e, boolean i) {
      element = e;
      isActive = i;
    }
  }

  private static final int DEFAULT_TABLE_SIZE = 11;

  private HashEntry<AnyType> [] array;  // The array of elements
  private int currentSize;  // The number of occupied cells

  private void allocateArray(int arraySize) {
    array = new HashEntry[arraySize];
  }

  private boolean isActive(int currentPos) {
    return array[currentPos] != null && array[currentPos].isActive;
  }

  private int findPos(AnyType x) {
    int offset = 1;
    int currentPos = myhash(x);

    while (array[currentPos] != null && !array[currentPos].element.equals(x)) {
      currentPos += offset;
      if (currentPos >= array.length) {
        currentPos -= array.length;
      }
    }

    return currentPos;
  }

  private void rehash() {
    HashEntry<AnyType> [] oldArray = array;

    allocateArray(nextPrime(oldArray.length * 2));
    currentSize = 0;

    for (int i = 0; i < oldArray.length; i++) {
      if (null != oldArray[i] && oldArray[i].isActive) {
        insert(oldArray[i].element);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= array.length;
    if (hashVal < 0) {
      hashVal += array.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }

    int sqrtMax = ((int) Math.sqrt(n));
    for (int i = 2; i < sqrtMax; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}

import java.util.LinkedList;
import java.util.List;

/**
 * 分离链接散列法
 */
public class SeparateChainingHashTable<AnyType> {
  public SeparateChainingHashTable() {
    this(DEFAULT_TABLE_SIZE);
  }

  public  SeparateChainingHashTable(int size) {
    theLists = new LinkedList[nextPrime(size)];
    for (int i = 0; i < theLists.length; i++) {
      theLists[i] = new LinkedList<>();
    }
  }

  public void insert(AnyType x) {
    List<AnyType> whichList = theLists[myhash(x)];
    if (!whichList.contains(x)) {
      whichList.add(x);
      if (++theSize > theLists.length) {
        rehash();
      }
    }
  }

  public void remove(AnyType x) {
    List<AnyType> whichList = theLists[myhash(x)];
    if (whichList.contains(x)) {
      whichList.remove(x);
      theSize--;
    }
  }

  public boolean contains(AnyType x) {
    List<AnyType> whichList = theLists[myhash(x)];
    return whichList.contains(x);
  }

  public void makeEmpty() {
    for (int i = 0; i < theLists.length; i++) {
      theLists[i].clear();
    }
    theSize = 0;
  }

  private static final int DEFAULT_TABLE_SIZE = 101;
  private List<AnyType>[] theLists;
  private int theSize;

  private void rehash() {
    List<AnyType>[] oldLists = theLists;

    theLists = new List[nextPrime(2 * theLists.length)];
    for (int j = 0; j < theLists.length; j++) {
      theLists[j] = new LinkedList<>();
    }

    theSize = 0;
    for (int i = 0; i < oldLists.length; i++) {
      for (AnyType item : oldLists[i]) {
        insert(item);
      }
    }
  }

  private int myhash(AnyType x) {
    int hashVal = x.hashCode();

    hashVal %= theLists.length;
    if (hashVal < 0) {
      hashVal += theLists.length;
    }
    return hashVal;
  }

  private static int nextPrime(int n) {
    while (!isPrime(n)) {
      n++;
    }
    return n;
  }

  private static boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }
    int sqrt = (int) Math.sqrt(n);
    for (int i = 0; i < sqrt; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }
}