BloomFilter/hash_function.py at master · Mark-THU/BloomFilter · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
# -*- coding: utf-8 -*-


class HashFunction(object):
    def __init__(self):
        self.functions = []
        self.functions.append(self.rs_hash)
        self.functions.append(self.js_hash)
        self.functions.append(self.pjw_hash)
        self.functions.append(self.elf_hash)
        self.functions.append(self.bkdr_hash)
        self.functions.append(self.sdbm_hash)
        self.functions.append(self.djb_hash)
        self.functions.append(self.dek_hash)
        self.functions.append(self.bp_hash)
        self.functions.append(self.fnv_hash)
        self.functions.append(self.ap_hash)

    def get_hash_function(self, number):
        if number > 11 or number <0:
            print('函数数目不得超过11，且不得小于0')
        else:
            return self.functions[0:number]

    def rs_hash(self, key):
        a = 378551
        b = 63689
        hash_value = 0
        for i in range(len(key)):
            hash_value = hash_value * a + ord(key[i])
            a = a * b
        return hash_value

    def js_hash(self, key):
        hash_value = 1315423911
        for i in range(len(key)):
            hash_value ^= ((hash_value << 5) + ord(key[i]) + (hash_value >> 2))
        return hash_value

    def pjw_hash(self, key):
        bits_in_unsigned_int = 4 * 8
        three_quarters = (bits_in_unsigned_int * 3) / 4
        one_eighth = bits_in_unsigned_int / 8
        high_bits = 0xFFFFFFFF << int(bits_in_unsigned_int - one_eighth)
        hash_value = 0
        test = 0

        for i in range(len(key)):
            hash_value = (hash_value << int(one_eighth)) + ord(key[i])
            test = hash_value & high_bits
        if test != 0:
            hash_value = ((hash_value ^ (test >> int(three_quarters))) & (~high_bits))
        return hash_value & 0x7FFFFFFF

    def elf_hash(self, key):
        hash_value = 0
        for i in range(len(key)):
            hash_value = (hash_value << 4) + ord(key[i])
            x = hash_value & 0xF0000000
            if x != 0:
                hash_value ^= (x >> 24)
            hash_value &= ~x
        return hash_value

    def bkdr_hash(self, key):
        seed = 131  # 31 131 1313 13131 131313 etc..
        hash_value = 0
        for i in range(len(key)):
            hash_value = (hash_value * seed) + ord(key[i])
        return hash_value

    def sdbm_hash(self, key):
        hash_value = 0
        for i in range(len(key)):
            hash_value = ord(key[i]) + (hash_value << 6) + (hash_value << 16) - hash_value
        return hash_value

    def djb_hash(self, key):
        hash_value = 5381
        for i in range(len(key)):
            hash_value = ((hash_value << 5) + hash_value) + ord(key[i])
        return hash_value

    def dek_hash(self, key):
        hash_value = len(key)
        for i in range(len(key)):
            hash_value = ((hash_value << 5) ^ (hash_value >> 27)) ^ ord(key[i])
        return hash_value

    def bp_hash(self, key):
        hash_value = 0
        for i in range(len(key)):
            hash_value = hash_value << 7 ^ ord(key[i])
        return hash_value

    def fnv_hash(self, key):
        fnv_prime = 0x811C9DC5
        hash_value = 0
        for i in range(len(key)):
            hash_value *= fnv_prime
            hash_value ^= ord(key[i])
        return hash_value

    def ap_hash(self, key):
        hash_value = 0xAAAAAAAA
        for i in range(len(key)):
            if (i & 1) == 0:
                hash_value ^= ((hash_value << 7) ^ ord(key[i]) * (hash_value >> 3))
            else:
                hash_value ^= (~((hash_value << 11) + ord(key[i]) ^ (hash_value >> 5)))
        return hash_value