【数据结构】哈希表—C/C++实现

1. 哈希表

哈希表类似：

比如python中的字典用到的就是哈希表

2. 基本思路

哈希表（Hash Table），也称为散列表。基本思路是，设存储元素个数为n，设置长度为m（m>=n）的连续内存单元，以每个元素的关键字ki为自变量，通过哈希函数把 k 映射为内存单元的哈希地址h（ki）,把该元素存储在此地址。

3. 哈希冲突

哈希冲突是指当两个关键字 ki 和 kj（i≠j）有ki≠kj，但h（ki）=h（kj）。

4. 哈希冲突的解决办法

开放寻址法：当发生哈希冲突时，在哈希表中找一个新的空闲位置存放元素。常见的探测序列包括线性探测法、平方探测法。 线性探测法：从发生冲突的位置D开始，依次探测D的下一空闲地址（哈希表末尾的下 一个地址是表首地址 —mod 实现）

平方探测法：从发生冲突的位置D开始，来回探测D的前后空闲地址

拉链法：每个桶（槽位）都包含一个链表，用于存储所有映射到该桶的键-值对。当发生哈希冲突时，新的键-值对被添加到相应桶的数据结构中，而不会覆盖旧值。

参考链接：哈希讲解

参考链接：哈希讲解

致读者

非知之难，行之为难；非行之难，终之斯难