布谷鸟过滤器 Cuckoo Filter

概念

Bloom Filter 可能存在误报，并且无法删除元素，而Cuckoo哈希就是解决这两个问题的。Cuckoo的哈希函数是成对的（具体的实现可以根据需求设计），每一个元素都是两个，分别映射到两个位置，一个是记录的位置，另一个是备用位置，这个备用位置是处理碰撞时用的。

如下图，使用hashA 和hashB 计算对应key x的位置a和b ：

• 当两个哈希位置有一个为空时，则插入该空位置；
• 当两个哈希位置均不为空时，随机选择两者之一的位置上key y 踢出，并计算踢出的key y在另一个哈希值对应的位置，若为空直接插入，不为空踢出原元素插入，再对被踢出的元素重新计算，重复该过程，直到有空位置为止。

布谷鸟?

cuckoo中文名叫布谷鸟，这种鸟有一种即狡猾又贪婪的习性，它不肯自己筑巢，而是把蛋下到别的鸟巢里，而且它的幼鸟又会比别的鸟早出生，布谷幼鸟天生有一种残忍的动作，幼鸟会拼命把未出生的其它鸟蛋挤出窝巢，今后以便独享“养父母”的食物。借助生物学上这一典故，cuckoo hashing处理碰撞的方法，就是把原来占用位置的这个元素踢走，不过被踢出去的元素还要比鸟蛋幸运，因为它还有一个备用位置可以安置，如果备用位置上还有人，再把它踢走，如此往复。直到被踢的次数达到一个上限，才确认哈希表已满，并执行rehash操作。

基本流程

    插入元素
    计算的元素的哈希值
    使用第一哈希函数获取哈希k1 和位置l1。
    如果第一个桶是空的
            放在第一个桶中。
    如果第一个bucket不为空
              使用第二个哈希函数获取 哈希 k2
                使用k2 与 k1 进行亦或运算 获取第二个位置l2
    若l2没有元素,放入l2中,如果有元素就进行布谷鸟哈希(循环踢出)

注意

Cockoo hashing 有两种变形：一种通过增加哈希函数进一步提高空间利用率；另一种是增加哈希表，每个哈希函数对应一个哈希表，每次选择多个张表中空余位置进行放置，三个哈希表可以达到80% 的空间利用率。

Cockoo hashing 的过程可能因为反复踢出无限循环下去，这时候就需要进行一次循环踢出的限制，超过限制则认为需要添加新的哈希函数

应用

网页URL的去重，垃圾邮件的判别，集合重复元素的判别，查询加速（比如基于key-value的存储系统）等。

Python代码

布谷鸟哈希表:

import random
import hashlib


class CuckooTable(object):
    def __init__(self, capacity):
        self.capacity = capacity
        self.buckets = []

    def insert(self, figer_print):
        if len(self.buckets) < self.capacity:
            self.buckets.append(figer_print)
            return True
        return False

    def remove(self, figer_print):
        idx = self.buckets.index(figer_print)
        if idx > -1:
            del self.buckets[idx]
            return True

    def swapFiger(self, figer_print):
        idx = random.randint(0, len(self.buckets))  # ?
        val, self.buckets[idx] = self.buckets[idx], figer_print
        return val

    def __contains__(self, figer_print):
        if figer_print in self.buckets:
            return True
        return False

过滤器:

def has(data):
    d1 = hashlib.sha256(data)
    return hash(d1.digest().encode('base64'))


def has2(data):
    d2 = hashlib.md5(data)
    return hash(d2.digest().encode('base64'))


class CuckooFilter(object):
    def __init__(self, filter_capacity, item_figerprint_size, num_swaps=500, buketsize=4):
        self.filter_capacity = filter_capacity
        self.item_figerprint_size = item_figerprint_size
        self.num_swaps = num_swaps
        self.buketsize = buketsize
        self.cuckoo_size = 0
        self.table = []
        for i in range(self.filter_capacity):
            self.table.append(CuckooTable(self.buketsize))

    def obtain_figerprint(self, item):
        has_val = has(item)
        return has_val

    def obtain_figerprint2(self,item):
        has_val = has2(item)
        return has_val

    def obtain_index_from_hash(self, item):
        idex =  has(item)
        idex = idex % self.filter_capacity
        return idex

    def obtain_index_from_item(self, item):
        idex_1 = self.obtain_index_from_hash(item)
        figerprint = self.obtain_figerprint2(item)
        idex_2 = idex_1 ^ figerprint
        idex_2 = idex_2 % self.filter_capacity
        return idex_1, idex_2

    def add(self, item):
        assert isinstance(item, str)
        if item in self:
            return
        idx1, idx2 = self.obtain_index_from_item(item)
        figerprint = self.obtain_figerprint(item)
        if self.table[idx1].insert(figerprint):
            self.cuckoo_size += 1
            return idx1
        if self.table[idx2].insert(figerprint):
            self.cuckoo_size += 1
            return idx2
        random_idex = random.choice((idx1, idx2))
        for i in range(self.num_swaps):
            figerprint = self.table[random_idex].swapFiger(figerprint)
            random_idex = random_idex ^ self.obtain_index_from_hash(
                str(figerprint))
            random_idex = random_idex % self.filter_capacity
            if self.table[random_idex].insert(figerprint):
                self.cuckoo_size += 1
                return random_idex

    def remove(self, item):
        figerprint = self.obtain_figerprint(item)
        idx, idx2 = self.obtain_index_from_item(item)
        if self.table[idx].remove(figerprint):
            self.cuckoo_size -= 1
            return True
        if self.table[idx2].remove(figerprint):
            self.cuckoo_size -= 1
            return True
        return False

    def __contains__(self, item):
        figerprint =  self.obtain_figerprint(item)
        idx, idx2 = self.obtain_index_from_item(item)
        contain = (figerprint in self.table[idx]
                   or figerprint in self.table[idx2])
        return contain

测试代码

def main():
    cuck = CuckooFilter(10, 2)
    cuck.add('Jame')
    cuck.add('Hello')
    cuck.add('World')
    cuck.add('Hello')
    print('Hello' in cuck)
    print('World' in cuck)
    print('jame'in cuck)
    print('Jame' in cuck)
    print('Done')
    for ele in cuck.table:
        print(ele)
    cuck.remove('Hello')
    print('----------------------->')
    print('Hello' in cuck)
    for ele in cuck.table:
        print(ele)


if __name__ == '__main__':
    main()