DS08:哈希表

哈希表

哈希表可以理解为是通过一个映射函数（哈希函数）直接得到存储地址的数据结构，通常基于数组实现（容量通常采用质数）。

存储地址 = f(关键字)	// f为哈希函数

根据这一基本特征可以看出，哈希表可以提供非常快速的插入-删除操作，理想状况下时间复杂度为0(1)级别。

哈希函数

哈希函数可以简单理解为是对需要存储的元素本身——>存储下标的映射。

如对字符串可以分别取其符号进行运算（整型则通常使用取模得到），而对于相关类，也可以自己定义hashcode函数，来获取坐标方式。

哈希函数的设计：

一致性：如果a==b,则hash(a)==hash(b)

高效性：计算高效简便

均匀性：哈希值均匀分布

哈希冲突

比如我们的哈希函数是对7取余，那么元素14和元素77通过哈希函数得到的索引就是相同的，这种情况就叫哈希冲突。

解决哈希冲突的方法有很多，具体有：链地址法（数组中存链表、平衡二叉树等元素）、开放地址法（向下找没存元素的位置，个人认为很麻烦不适用）等方法。

也可以将实现哈希表的数组直接保存一个平衡二叉树，总之就是为了解决冲突问题。

哈希表扩容

如果哈希函数设计的不好，很多元素都重叠在了一个地址，那么理论上O(1)的时间复杂度在以平衡二叉树为数组元素的哈希表中就会达到O(log n/m)，因此遇到这种时候，就应该对哈希表进行扩容。

平均每个地址承载的元素多过一定程度，就进行扩容，通常这个值是0.75。缩容同理。

由于哈希表的实现方法很多，而且并不算太难，所以不进行代码记录，主要思想就是以空间换时间

参考链接：

https://www.jianshu.com/p/6e88d63061f2

Donate