【LintCode 简单】128. 哈希函数

一时失言乱红尘 2022-11-26 09:56 82阅读 0赞

1.问题描述：

在数据结构中，哈希函数是用来将一个字符串（或任何其他类型）转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数算法是使用数值33，假设任何字符串都是基于33的一个大整数，比如：

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

其中HASH\_SIZE表示哈希表的大小(可以假设一个哈希表就是一个索引0 ~ HASH\_SIZE-1的数组)。

给出一个字符串作为key和一个哈希表的大小，返回这个字符串的哈希值。

2.样例：

> 样例 1:
> 
> 输入:  key = "abcd", size = 1000  
> 输出: 978      
> 样例解释：(97 \* 33^3 + 98\*33^2 + 99\*33 + 100\*1)%1000 = 978  
> 样例 2:
> 
> 输入:  key = "abcd", size = 100  
> 输出: 78      
> 样例解释：(97 \* 33^3 + 98\*33^2 + 99\*33 + 100\*1)%100 = 78

3.代码：

class Solution:
        """
        @param key: A string you should hash
        @param HASH_SIZE: An integer
        @return: An integer
        """
    
        def hashCode(self, key, HASH_SIZE):
            # write your code here
            # Method 1
            # length = len(key)
            # sum = 0
            # for i in range(len(key)):
            #     sum += ord(key[i]) * pow(33,length-i-1)
            # print(sum)
            # return sum % HASH_SIZE
            # Method 2
            value = 0
            for i in key:
                value = (ord(i) + value * 33) % HASH_SIZE
            return value

本题直接使用Method1会出现超时错误，需要使用更加巧妙的方法。这里引出一个定理：同余定理。记住以下三大定理：  
1 (a + b) % c = (a % c + b % c) % c  
2 (a \* b) % c = (a % c \* b % c) % c  
3 mk % m = 0, b % m = 0, (mk + b) % m = 0

> 这里对于这种都乘一个数的次方时，可以根据下面的式子进行化简：
> 
> a \* 33 ^ 4 + b \* 33 ^ 3 + c \* 33 ^ 2 + d \* 33 ^ 1 + e  
> =  
> (((a \* 33 + b) \* 33 + c) \* 33 + d) \* 33 + e

参考资料：

1. [https://baike.baidu.com/item/同余定理/1212360?fr=aladdin][https_baike.baidu.com_item_1212360_fr_aladdin]

[https_baike.baidu.com_item_1212360_fr_aladdin]: https://baike.baidu.com/item/%E5%90%8C%E4%BD%99%E5%AE%9A%E7%90%86/1212360?fr=aladdin