Hash Function

秒速五厘米 2021-12-17 10:37 195阅读 0赞

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to "hash" the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:

hashcode("abcd") = (ascii(a) \* 333 + ascii(b) \* 332 + ascii(c) \*33 + ascii(d)) % HASH\_SIZE

= (97\* 333 + 98 \* 332 + 99 \* 33 +100) % HASH\_SIZE

= 3595978 % HASH\_SIZE

here HASH\_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH\_SIZE-1).

Given a string as a key and the size of hash table, return the hash value of this key.f

Lintcode上的一道题，没有什么技术含量，就是根据公式求hash值。但是这种straight forward的方法最后超时了，所以其实取余运算可以进行优化，也即是不在最后进行取余运算，而是在每一步的运算中都取余。代码如下：

class Solution:
        """
        @param key: A String you should hash
        @param HASH_SIZE: An integer
        @return an integer
        """
        def hashCode(self, key, HASH_SIZE):
            if not key:
                return 0
            hashcode = 0
            for s in key:
                hashcode = (hashcode*33 + ord(s))%HASH_SIZE
            return hashcode

这种操作的正确性可以证明，即 (a+b)%c = (a%c+b)%c 从性质（1）可以推出。

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p) % p （2）

(a \* b) % p = (a % p \* b % p) % p （3）

(a^b) % p = ((a % p)^b) % p （4）

推论：

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）

若a≡b (% p)，则对于任意的c，都有(a \* c) ≡ (b \* c) (%p)；（11）

若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

(a \* c) ≡ (b \* d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

费马定理：若p是素数，a是正整数且不能被p整除，则：a^(p-1) mod p = 1 mod p  
推论：若p是素数，a是正整数且不能被p整除，则：a^p mod p = a mod p

转载于:https://www.cnblogs.com/sherylwang/p/5589223.html