「大数据」(一百四十四)常用算法及数据结构之Cuckoo Hash
【导读:数据是二十一世纪的石油,蕴含巨大价值,这是·情报通·大数据技术系列第[144]篇文章,欢迎阅读收藏】
1 基本概念
CuckooHash (布谷鸟散列),最早于 2001 年由 Rasmus Pagh 和 Flemming Friche Rodler 提出。是为了解决哈希冲突问题,利用较少的计算换取较大的空间。
特点: 占用空间少,查询速度快。
来源: 之所以起这个名字是因为布谷鸟生性贪婪,不自己筑巢,而是在别的鸟巢里面鸟蛋孵化,先成长的幼鸟会将别的鸟蛋挤出,这样独享 “ 母爱 ” ,类似于哈希冲突处理过程。
2 术语解释
cuckoo hashing 有什么特点,它的哈希函数是成对的(具体的实现可以根据需求设计),每一个元素都是两个,分别映射到两个位置,一个是记录的位置,另一个是 备用位置。这个备用位置是处理碰撞时用的,这就要说到 cuckoo 这个名词的典故了,中文名叫布谷鸟,这种鸟有一种即狡猾又贪婪的习性,它不肯自己筑巢, 而是把蛋下到别的鸟巢里,而且它的幼鸟又会比别的鸟早出生,布谷幼鸟天生有一种残忍的动作,幼鸟会拼命把未出生的其它鸟蛋挤出窝巢,今后以便独享 “ 养父 母 ” 的食物。借助生物学上这一典故, cuckoo hashing 处理碰撞的方法,就是把原来占用位置的这个元素踢走,不过被踢出去的元素还要比鸟蛋幸运,因为它还有一个备用位置可以安置,如果备用位置上 还有人,再把它踢走,如此往复。直到被踢的次数达到一个上限,才确认哈希表已满,并执行 rehash 操作。
3 详细说明
3.1 算法步骤
分别使用 hashA 、 hashB 计算对应的 key 位置:
1. 两个位置均为空,则任选一个插入;
2. 两个位置中一个为空,则插入到空的那个位置
3. 两个位置均不为空,则随机踢出一个位置上的 keyx ,被踢出的 keyx 再执行该算法找其另一个位置,循环直到插入成功。
4. 如果被踢出的次数达到一定的阈值,则认为 hash 表已满,并进行重新哈希 rehash
3.2 其他
Cockoo hash 有两种变形。一种通过增加哈希函数进一步提高空间利用率;另一种是增加哈希表,每个哈希函数对应一个哈希表,每次选择多个张表中空余位置进行放置。三个哈希表可以达到 80% 的空间利用率。
Cockoo hash 的过程可能因为反复踢出无限循环下去,这时候就需要进行一次循环踢出的限制,超过限制则认为需要添加新的哈希函数。
Cockoo hash 的应用, Cuckoo Filter 。
3.3 算法实现
我们知道实现布谷鸟散列是需要一个散列函数的集合。因此,我们要定义一个接口来获取到这样的一个集合。
public interface HashFamily <AnyType>{
//根据which来选择散列函数,并返回hash值
int hash(AnyType x, int which);
//返回集合中散列函数的个数
int getNumberOfFunctions();
//获取到新的散列函数
void generateNewFunctions();
}