第1个回答 2022-07-06
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。
Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte，而且用于记录规则的表大小会根据规则，大小可能是不定的。
通过哈希函数，我们可以将键转换为数组的索引(0-M-1)，但是对于两个或者多个键具有相同索引值的情况，我们需要有一种方法来处理这种冲突。
一种比较直接的办法就是，将大小为M 的数组的每一个元素指向一个链表，链表中的每一个节点都存储散列值为该索引的键值对，这就是拉链法。下图很清楚的描述了什么是拉链法。
“John Smith”和“Sandra Dee” 通过哈希函数都指向了152 这个索引，该索引又指向了一个链表， 在链表中依次存储了这两个字符串。
单独链表法：将散列到同一个存储位置的所有元素保存在一个链表中（聚集），该方法的基本思想就是选择足够大的M，使得所有的链表都尽可能的短小，以保证查找的效率。当链表过长、大量的键都会映射到相同的索引上，哈希表的顺序查找会转变为链表的查找，查找时间将会变大。对于开放寻址会造成性能的灾难性损失。
实现基于拉链表的散列表，目标是选择适当的数组大小M，使得既不会因为空链表而浪费内存空间，也不会因为链表太而在查找上浪费太多时间。拉链表的优点在于，这种数组大小M的选择不是关键性的，如果存入的键多于预期，那么查找的时间只会比选择更大的数组稍长。另外，我们也可以使用更高效的结构来代替链表存储。如果存入的键少于预期，索然有些浪费空间，但是查找速度就会很快。所以当内存不紧张时，我们可以选择足够大的M，可以使得查找时间变为常数，如果内存紧张时，选择尽量大的M仍能够将性能提高M倍。
线性探测法是开放寻址法解决哈希冲突的一种方法，基本原理为，使用大小为M的数组来保存N个键值对，其中M>N，我们需要使用数组中的空位解决碰撞冲突。如下图所示：
对照前面的拉链法，在该图中，“Ted Baker” 是有唯一的哈希值153的，但是由于153被“Sandra Dee”占用了。而原先“Snadra Dee”和“John Smith”的哈希值都是152的，但是在对“Sandra Dee”进行哈希的时候发现152已经被占用了，所以往下找发现153没有被占用，所以索引加1 把“Sandra Dee”存放在没有被占用的153上，然后想把“Ted Baker”哈希到153上，发现已经被占用了，所以往下找，发现154没有被占用，所以值存到了154上。
单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)。
原文： 哈希查找 - 卖贾笔的小男孩 - 博客园 (cnblogs.com)