LintCodeInPython/hash_function.py at master · MrFatt/LintCodeInPython · 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
# -*- coding: utf-8 -*-

classSolution:
"""
 @param key: A String you should hash
 @param HASH_SIZE: An integer
 @return an integer
 """
defhashCode(self, key, HASH_SIZE):
# write your code here
x=0
foriinxrange(len(key)):
x+=ord(key[i]) *self.fastPower(33, HASH_SIZE, len(key) -1-i)
returnx%HASH_SIZE

deffastPower(self, a, b, n): # 参考fast_power.py实现快速取模
# write your code here
ifn==0:
return1%b
if1==n:
returna%b
x=self.fastPower(a, b, n/2)
ifn%2==1:
return (((x*x) %b) *a) %b
else:
return (x*x) %b