09-哈希表

哈希表

通过哈希函数将数据转化成相应的数组索引，在将数据存入数组中，若对于不同数据通过哈希函数得到的索引若是相同的就是哈希冲突

通用哈希函数设计

在Java中可以通过Object类提供的hashCode()方法来得到相对于的整数，但是要注意该方法可能返回一个负数，可以通过取绝对值，或与0x7fffffff按位与（将符号位变为0，即正数），来获取正整数的哈希值

对于类对象来说返回的是与地址相关的哈希值，若想与属性做对应的一致性就需要覆写该方法，在使用标准库中的HashMap和HashSet时需要同时覆盖hashCode()和equals()方法，因为在引发哈希冲突时需要使用equals()方法来辨别两个对象是否相等

均匀性：尽量的避免哈希冲突，也就是说数据通过哈希函数得到的索引分布越均匀越好
一致性：若a和b相等，所得到的哈希值应该也是相等的
高效性：计算高效

整型

小范围正整数：直接使用
小范围负整数：向正整数偏移
大整数：取模，得到的值永远不会超过该模数，尽量模一个素数可以减少哈希冲突

浮点数

将浮点数所存储的二进制表示使用十进制整型方式解析，得到大整型索引，在通过取模方式

字符串

对于数字来说 $123=1*10^2+1*10^1+1*10^0$ ，这串数字也可以看作是字符串，所以对于字符串来说 $abc=a*26^2+b*26^1+c*26^0$ ，但是字符串中的字符也不一定只有26个，进制应该是用户所指定的，假设用户指定的进制是 $B$ 该公式就成了 $abc=a*B^2+b*B^1+c*B^0$ ，所得到的结果就是大整数，在通过取模方式

从公式中可以看出，若字符串过长，进制的指数部分就会越大，计算就会越慢，所以优化公式就得到了 $abc=(((a*B)+b)*B+c)$

还有一个问题，就是若字符串过长，该大整型在取模前就可能产生整型溢出，在乘进制数之前就取模最后的取模值是不变的，继续优化公式 $hash(abc)=(((a \ \% \ M*B)+b)\ \% \ M *B+c)\ \% \ M$

这就很容易使用循环来处理字符串得到哈希值

int hash = 0;
for(int i = 0; i < string.length(); i++){
  hash = (hash * B + string.charAt(i)) % M;
}

符合类型

对于自定义的类对象来说，同样的可以使用向字符串那样的方式来转化，字符串对应的字符，对象对应的是各个属性

链地址法解决哈希冲突

当发生哈希冲突时，将数组中对应的位置存放成一个链表（也可以是任意数据结构，比如树）将所有哈希冲突的数据存放在这个链表中，对于Java标准库中的HashMap和HashSet来说，在Java8以前哈希表中所对应的就是一个链表，在Java8及以后时，初始依然是一个链表，当哈希冲突到达一定程度（平均来讲每个位置存储的哈希冲突元素数多余某个程度）时就会从链表转化成红黑树，前提是存入元素有可比较性（实现Comparable接口）

import java.util.ArrayList;

/**
 * @ClassName: HashTable
 * @Description: 基于动态数组的自定义哈希表
 */
public class HashTable<E> {
  private static final int upperTol = 10; //平均哈希冲突上界
  private static final int lowerTol = 2;  //平均哈希冲突下界
  private static final int[] capacity = {53, 97, 193, 389, 769, 1543, 3079,
      6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869,
      6291469, 12582917, 25165843, 100663319, 201326611, 402653189,
      805306457, 1610612741}; //扩容素数表

  private int capacityIndex = 0;  //扩容素数表上的指针
  private ArrayList<E>[] hashTable; //哈希表数组
  private int M;  //哈希表的大小，也是取余运算的模
  private int size; //哈希表中已存储的元素个数

  /**
   * @MethodName: HashTable
   * @Description: 创建哈希表，初始大小为最小容量
   */
  public HashTable() {
    this.M = capacity[this.capacityIndex];
    this.size = 0;
    this.hashTable = new ArrayList[this.M]; //声明哈希表数组
    for (int i = 0; i < this.M; i++) {  //声明哈希表数组中的每个动态数组
      hashTable[i] = new ArrayList<>();
    }
  }

  /**
   * @MethodName: hash
   * @Description: 将元素转化成对应的正整数的哈希值
   * @Param element: 对应的元素
   * @Return int
   */
  private int hash(E element) {
    return element.hashCode() & 0x7fffffff % this.M;
  }

  /**
   * @MethodName: resize
   * @Description: 使用指定M修改容量容
   * @Param newM: 指定的哈希表大小（也是取余运算的模）
   * @Return void
   */
  private void resize(int newM) {
    ArrayList<E>[] newHashTable = new ArrayList[newM];  //创建新存储哈希表的数组
    for (int i = 0; i < newM; i++) {  //初始化哈希表数组内的每个动态数组对象
      newHashTable[i] = new ArrayList<>();
    }

    this.M = newM;  //修改取模运算的
    for (int i = 0; i < this.hashTable.length; i++) {  //遍历原来哈希表中的每个动态数组
      for (E element : this.hashTable[i]) { //遍历动态数组中的每个元素
        newHashTable[this.hash(element)].add(element);  //将原来哈希表元素添加到新的哈希表中
      }
    }
    this.hashTable = newHashTable;  //修改为新的哈希表
  }

  /**
   * @MethodName: add
   * @Description: 向哈希表中添加元素
   * @Param element: 要添加的元素
   * @Return void
   */
  public void add(E element) {
    ArrayList arrayList = this.hashTable[this.hash(element)];
    if (arrayList.contains(element)) {
      //若当前哈希表中的动态数组中已经存储了该元素，直接返回什么也不用做
      return;
    }
    arrayList.add(element);  //否则添加
    this.size++;  //添加元素后存储元素个数加1
    if (this.size >= upperTol * M && this.capacityIndex < capacity.length) {  //由于除法需要向浮点数转化，所以写成乘法
      //若当前哈希表中哈希冲突等于或超过了上界限，并且素数未越界
      this.capacityIndex++; //容量指针后移
      this.resize(capacity[this.capacityIndex]);  //扩容
    }
  }

  /**
   * @MethodName: remove
   * @Description: 从哈希表中删除元素
   * @Param element: 要删除的元素
   * @Return void
   */
  public void remove(E element) {
    ArrayList arrayList = this.hashTable[this.hash(element)];
    if (!arrayList.contains(element)) {
      //若当前哈希表中的动态数组中没有存储了该元素，直接返回什么也不用做
      return;
    }
    arrayList.remove(element);  //否则删除
    this.size--;  //删除元素后存储元素个数减1
    if (this.size < lowerTol * this.M && this.capacityIndex > 0) {  //由于除法需要向浮点数转化，所以写成乘法
      //若当前哈希表中哈希冲突等于或低于了下界限，并且素数未越界
      this.capacityIndex--; //容量指针前移
      this.resize(capacity[this.capacityIndex]);  //缩容
    }
  }

  /**
   * @MethodName: contains
   * @Description: 判断哈希表中是否有该元素
   * @Param element: 要判断的元素
   * @Return boolean
   */
  public boolean contains(E element) {
    return this.hashTable[this.hash(element)].contains(element);
    //若当前哈希表中的动态数组中是否存储了该元素
  }

  public int getSize() {
    return this.size;
  }

  public boolean isEmpty() {
    return this.size == 0;
  }

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < this.M; i++) {
      sb.append("[" + i + "]: ");
      for (E element : hashTable[i]) {
        sb.append(element + "->");
      }
      sb.append("\n");
    }
    return sb.toString();
  }
}