1.hash table

哈希表，也叫散列表，是通过键（KEY）来直接访问【内存存储位置】的一种线性数据结构

2.hash函数的本质——映射

哈希函数可以将大范围的消息M映射成为一个小范围的值Hash(M)，Hash(M)称为哈希值、散列值或者消息摘要（Message Digest）。哈希函数是可公开的，因为它是单向的从明文到密文的不可逆映射，只能加密不能解密

例如，hash(num) = num % 10，也就是哈希值等于原始值除以10的余数。那么，即使我们知道这个余数，我们也推不出原始值究竟是多少

3.解决哈希冲突

由于hash是一种映射，它将大范围消息映射到一个小范围上，如上面提到的例子，hash(num) = num % 10，将所有数字映射到0到9的范围内，必然会产生冲突
通过构造性能良好的哈希函数，可以减少冲突。如：

/* BKDR Hash Function */
unsigned int BKDR_hash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*str)
    {
        hash = hash * seed + (*str++);  //【通过seed减少hash冲突】，但具体原理尚未理解清楚
    }
    return (hash & 0x7FFFFFFF); // 最终结果mod 2的31次方
}

但需要注意的是，哈希函数不能完全避免冲突，冲突一定会存在。那么如何解决这些冲突？
主要有4种方法（4哈希）：

• 1.开放寻址法
  当发生哈希冲突时，按照一定的规则（如线性寻址、平方寻址法）找到能够空闲的内存单元来存放冲突的值
• 2.拉链法
  通过同义词链表来存储产生哈希值相同的元素，每产生一次哈希冲突，就在对应的链表头新增一个节点存放
• 3.再哈希法（多次哈希法）
  有多个hash函数，如果冲突了就换一个hash函数重新计算，直到不冲突为止，缺点也容易理解，计算次数多耗时长
• 4.公共溢出区法
  hash表分为基本表和溢出表，冲突的数据全部丢到溢出表去。当查找过程中发现冲突时，就在溢出表中进行顺序查找。显然，使用公共溢出区时，需要限制溢出区的规模以避免大规模的顺序查找。这就需要性能足够好的hash函数和空间足够的基本表

可以参考：
https://www.jianshu.com/p/f20fb1a44dca
https://mp.weixin.qq.com/s/B126kU8EFlghjRjz4dZPYg