Standard Bloom Filter

没有用标准做法，而是调用的Python的hash函数再利用过滤器本身size来模

class StandardBloomFilter:

    # @param {int} k an integer
    def __init__(self, k):
        # initialize your data structure here
        self.size = 10 ** 5
        self.array = [False] * self.size
        self.k = k

    # @param {str} word a string
    def add(self, word):
        # Write your code here
        for i in xrange(self.k):
            self.array[hash(word) % (self.size + i)] = True

    # @param {str} word a string
    # @return {bool} True if word is exists in bllom filter or false
    def contains(self, word):
        # Write your code here
        for i in xrange(self.k):
            if not self.array[hash(word) % (self.size + i)]:
                return False

        return True

Counting Bloom Filter

加了一个计数的元素就行了

class CountingBloomFilter:

    # @param {int} k an integer
    def __init__(self, k):
        # initialize your data structure here
        self.size = 10 ** 5
        self.array = [[False, 0] for _ in xrange(self.size)]
        self.k = k

    # @param {str} word a string
    def add(self, word):
        # Write your code here
        for i in xrange(self.k):
            handle = hash(word) % (self.size + i)
            self.array[handle] = [True, self.array[handle][1] + 1]

    # @param {str} word a string
    def remove(self, word):
        # Write your code here
        for i in xrange(self.k):
            handle = hash(word) % (self.size + i)
            self.array[handle][1] -= 1
            if not self.array[handle][1]:
                self.array[handle][0] = False

    # @param {str} word a string
    # @return {bool} True if word is exists in bllom filter or false
    def contains(self, word):
        # Write your code here
        for i in xrange(self.k):
            if not self.array[hash(word) % (self.size + i)][0]:
                return False
        return True