python手刃lintcode(128) ：哈希函数【简单题】

朱雀 2022-05-16 09:06 106阅读 0赞

### python手刃lintcode(128) ：哈希函数【简单题】 ###

这道题没有什么算法难点，公式已经给出了，重点是一些函数的使用和时间复杂度的问题。

字符串转换函数：

*  ord©:参数是长度为1的字符串，简称字符。当参数为统一对象时（unicode object），返回能代表该字符的统一编码，当参数为8比特的字符串时，返回该字节的值。例如，ord(‘a’)返回整形数值97，ord(u’\\u2020’)返回8224。
 *  chr(i)：返回一个字符，字符的ascii码等于参数中的整形数值。例如chr(97)返回字符’a’，该方法是ord()的反方法。参数必须是0-255的整形数值，否则会抛出valueError错误。

注意这里不能用`int()` 函数进行转化，因为该函数的输入值只是时数字。

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
            n = len(key)
            num = 0
            for i in range(n):
                num += ord(key[i])*(33**(n-i-1))
            num = num % HASH_SIZE
            return num

但是上边这个程序会报超时的错误，接下来考虑怎么降低时间复杂度。因为本身的转换公式已经给定了，所以能降低复杂度的方法也就是从计算顺序等方面着手。

降低时间复杂度方法：

1.  如果从前往后顺次转化，那么可以发现要从  3 3 n − 1 33^\{n-1\} 33n−1 算到  3 3 0 33^\{0\} 330 ，即需要计算 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2 次,所以我们可以改变一下顺序，从后往前进行转换，并保留每次计算的33次方的值，在下一次计算时再乘以33即可,这样只需要计算  n − 1 n-1 n−1 次即可，可以降低时间复杂度。
2.  对于转换公式：

来说，其实完全可以对每一项先取余再相加（能除就尽量先除），这样可以减少内存占用和计算量。

改进后的程序：

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
            n = len(key)
            num = 0
            temp = 1
            for i in range(n-1,-1,-1):
                num += ord(key[i])*temp%HASH_SIZE   
                temp = temp*33 % HASH_SIZE
            num = num % HASH_SIZE
            return num