哈希函数介绍
什么是哈希
在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。
哈希函数就是一种映射,是从关键字到存储地址的映射。
通常,包含哈希函数的算法的算法复杂度都假设为 O(1),这就是为什么在哈希表中搜索数据的时间复杂度会被认为是"平均为 O(1) 的复杂度".
基本概念
在讲解具体内容前,首先我们要清楚以下几个概念:
1. 冲突(碰撞)
对于不同的关键字 ki、kj,若 ki != kj,但 H(ki) = H(kj) 的现象叫冲突(collision) ,即不同的输入却有相同的输出。我们应该尽量避免冲突,因为冲突不仅会使我们在查找的时候效率变慢,还甚至会被攻击者利用从而大量消耗系统资源。
至于冲突的解决方案有很多种,具体可以参考这篇哈希表针对冲突的两种方式优缺点是什么?。
哈希函数的应用
哈希算法广泛应用于很多场景,例如安全加密和数据结构中哈希表的查找,布隆过滤器和负载均衡(一致性哈希)等等。
下面介绍几个常用的哈希算法。