python之哈希函数不正确 Math.pow 不处理任意大的数字

我正在尝试解决这个问题 easy problem在 LintCode 上，我有我的解决方案:

import math 
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 
        ret=0 
        for i in range(0,len(key)): 
            multiplier=int(math.pow(33,len(key)-i-1)) 
            ret += (multiplier* ord(key[i])) 
        return ret%HASH_SIZE 

但它只适用于 length <= 11 的键否则不起作用(错误答案)。 Python 默认处理任意大的数字，那么问题是什么？这太简单了，弄错会让我发疯。

问题描述如下:

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

更新:Rob 的答案解决了答案不正确的问题，但现在速度是个问题。

更新 2: 以下两种技术都有效:

        ret=0 
        ## technique 1 
        for i in range(0,len(key)): 
            multiplier= pow(33,(len(key)-i-1),HASH_SIZE) 
            ret += (multiplier * ord(key[i])) 
        return ret%HASH_SIZE 
        # technique 2 
        ret=0 
        multiplier = 1 
        for ch in key[::-1]: 
            ret = (ret + ord(ch) * multiplier) % HASH_SIZE 
            multiplier = (multiplier * 33) % HASH_SIZE 
        return ret % HASH_SIZE 

请您参考如下方法:

将引导您找到解决方案的一对事实:

1. pow(x, y, [z]) 内置函数将准确计算 (x ** y) % z 而无需涉及任意长度的整数.

2. (a + b + …) % x 与 (a%x + b%x + …) % x 相同。 (也就是说，您可以在求和内执行模运算而不影响结果。)