0%
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| '''
散列函数的构造：
一：计算简单，以便高速转换；
二：关键词对应的地址空间分布均匀，尽量减少冲突。
如果关键词是数字，
经典的几种方法有：
1、直接定值法
取key的某个线性函数值为散列的地址。
h（key）= a * key + b
2、除留余数法
h（key）= key mod p
p 一般取一个素数（质数） # 一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；
因为质数 容易除出余数
3、数字分析法
关键字由很多位组成，每一位在对象里面变化情况不一样。我们选取变化比较多的部分作key输入函数。
比如：
取11位手机号码key的后4位作为地址；
散列函数为：h(key) = atoi(key+7)
这里key是一个指针，指向的是一个字符串的左边第一个位置，
比如：
18位身份证上数字变化较为多的是第6、10、14、16、17 五个位置。
我们用这五个位置的数字 组合成一个5位数来存放，
h(key) = key[6]*10^4 + key[10]*10^3 + key[14]*10^2 + key[16]*10^1 + key[17]
考虑到最后一位校验位
h(key) = h(key)*10 + key[18] or h(key) = h(key)*10 + 10 # 校验位是x。
4、折叠法
把关键词分割成位数相同的几个部分，然后叠加
比如：
56793542 每三位取成一组，不够的左边补0。形成：056、793、542三个数；
对这三个数求和，从右取，取三位作为存放地址。
5、平方取中法
和折叠法的思路一样，都是为了让散列方法的结果被尽可能多的位影响，
如果仅仅取后几位，则只会被后面几位影响，取中可以相对兼顾了头尾。
比如：
56793542 平方 ，取中间三位641作存放地址。
'''
'''
如果关键词是字符串，
散列函数经典构造方法：
1、ASCII码 加和法
h(key) = (Σkey[i]) mod TableSize
但是这样的散列方法有一个潜在的问题，
ASCII 码用到的是7位，实际变化范围就是0～127，
例如一个关键词有10位，每一位变化范围是0～127，
h(key)一共就是0～1270个位置，远远小于实际可能出现的变量名组合，
容易出现聚集效应，冲突严重。
2、ASCII码 加和法改进，前3字符位移法
h(key) = (key[0]*27^2+key[1]*27+key[2]) mod TableSize
因为有26个字母，加一个空格，所以选27进制 运用到前三位来扩充范围。
但是这样仍然可能冲突，比如前三位是一样的str、str、str、str。
除此之外，还会浪费空间，加入字符串前三位都是字符组成，一共的可能性是26^3种，
但是英文字母实际前三位大约3000种，3000/26^3 造成大量空间浪费。
3、位移法
这是好的散列函数，涉及关键词所有字符一共n个，分布很好。
h(key) = (Σkey[i]*32^i) mod TableSize
h('abcde') = 'a'*32^4 + 'b'*32^3 + 'c'*32^2 + 'd'*32 + e
级数求和
可以用 秦九韶算法 减少级数求和中乘法的使用次数。
更好的做法是在秦九韶算法的基础上，用左移代替乘法：
在二进制中左移1位就是翻2^1倍，左移5位就是翻32倍。
def Hash(A,TableSize):
h = 0
i = 0
while i < len(A): # 没到字符串结尾。
h = (h<<5) + ord(A[i])
i += 1
return h % TableSize
'''
|