定义

哈希表可以存储各种类型的数据，当我们从哈希表中查找所需要的数据时，理想情况是不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使每个关键字和结构中一个唯一的存储位置相对应。(关键字就是所要存储的数据，存储位置相当于数组的索引)

哈希冲突

通过哈希函数计算出的索引，即使关键字不同，索引也会有可能相同。就是哈希冲突

空间换时间

哈希表充分体现了空间换时间这种经典的算法思想。
关键字是大整数时，比如上面我们举的身份证号例子，411697199702076425
假如我们能开辟一个 999999999999999999 大的空间，这样就能直接把身份证号作为关键字存储到数组中，这样可以用O(1)时间完成各项操作
假如我们只有 1 的空间，我们需要把所有信息存储到这个空间中(也就是所有数据都会产生哈希冲突)，我们只能用O(n)时间完成各项操作
事实上，我们不可能开辟一个如此大的空间，也不可会开辟如此小的空间
无限空间时，时间为O(1)
1的空间时，时间为O(n)
而哈希表就是在二者之间产生一个平衡，即空间和时间的平

常见的hash算法

哈希表的组成取决于哈希算法，也就是哈希函数的构成，下面列举几种常见的哈希算法。
1） 直接定址法

  • 取关键字或关键字的某个线性函数值为散列地址。
  • 即 f(key) = key 或 f(key) = a*key + b，其中a和b为常数。

2） 除留余数法

  • 取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
  • 即 f(key) = key % p, p < m。这是最为常见的一种哈希算法。

3） 数字分析法

  • 当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。
  • 仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。

4） 平方取中法

  • 先计算出关键字值的平方，然后取平方值中间几位作为散列地址。
  • 随机分布的关键字，得到的散列地址也是随机分布的。

5） 随机数法

  • 选择一个随机函数，把关键字的随机函数值作为它的哈希值。
  • 通常当关键字的长度不等时用这种方法。

    哈希冲突的解决办法

    开放定址法（再散列法）
    这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
    再哈希法
    这种方法是同时构造多个不同的哈希函数：
    Hi=RH1（key） i=1，2，…，k
    当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间
    链地址法
    这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
    建立公共溢出区
    这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

来自：https://www.jianshu.com/p/4e64fce04a38