原题
在数据结构中，哈希函数是用来将一个字符串（或任何其他类型）转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数算法是使用数值33，假设任何字符串都是基于33的一个大整数。给出一个字符串作为key和一个哈希表的大小，返回这个字符串的哈希值。
对于key="abcd" 并且 size=100， 返回 78
解题思路：
关于哈希表：
哈希表在内存中是一个事先开辟好的数组，通过hash function把一个key转化为某一个index，来实现O(1)的查找
理想状态下，每次算出的index都是唯一的，而实际上会有Collision
hash function设计标准是越乱越没有规则越好，以避免Collision，一般是通过某种方式将key转化为一个integer然后对hash table size取模
哈希表的size最好要是所要存的数字数量的10倍，当size不够时，需要rehashing。
如何处理冲突 - Collision
Open hashing - 冲突的话，index下面采用linked list
Closed hashing - 如果有冲突，则向前或者向后位移。致命缺点，不支持删除，所以几乎没人采用
将key转化为整数的方式有：
MD5, 但是耗费较大
APR hash function - magic number 33(只是经验值)
Python中char和integer之间的转换
>>>ord("a")
97
>>>chr(97)
'a'
- 小技巧，如何计算a * 33^3 + b * 33^2 + c * 33 + d
sum = a * 33
sum = (a * 33 + b) * 33
sum = (a * 33^2 + b * 33 + c) * 33
sum = (a * 33^3 + b * 33^2 + c * 33 + d) * 33
...
完整代码
class Solution:
"""
@param key: A String you should hash
@param HASH_SIZE: An integer
@return an integer
"""
def hashCode(self, key, HASH_SIZE):
sum = 0
for char in key:
sum = sum * 33 + ord(char)
sum = sum % HASH_SIZE
return sum
