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
80
81
82
83
84
85
86
| '''
散列表（哈希表）
已知的几种查找：
顺序查找 O(N)
二分查找（静态查找） O(logN)
二叉搜索树 O(h) h是树的高度
平衡二叉树 O(logN)
以上几种方法都不适合用在长字符串的查找。
例如，比较变量名，可以把变量名转为数字，再比较这个数字，这样比两个字符串一个字符一个字符比较要方便。
例子：
十亿 10^9 ≈ 2^30客户，二分法查找需要30次。
十亿 客户 如果一个人用1000b空间，10^9 ≈ 2^30客户就是 1024G，1T。
但是qq号大小有序存储，在连续存储空间中，插入和删除一个qq号需要有大量的数据移动。
所以，二分法查找不是一个好的方法。
如果关键词不方便比较怎么办？
查找的本质：已知对象找位置。
一类：有序安排对象：全序（二分法）、半序（查找树）。
二类：直接 "算出" 对象位置：散列。
·····························································
散列查找法两项基本工作：
一：计算位置：构造散列函数确定关键词的存储位置；
二：解决冲突：应用某种策略解决多个关键词位置相同的问题。
·····························································
散列查找的时间复杂度几乎是O(1),即 查找时间与问题规模无关！！！
'''
'''
散列表（哈希表）
类型名称： 符号表（SymbolTable）
数据对象集： 名字和属性的集合
操作集： 创建长度为tablesize的符号表；
查找特定名字是否在符号表table中；
获取table中指定名字name对应的属性；
修改table中指定名字name对应的属性；
向table中插入一个新的名字name及其属性；
从table中删除一个名字name及其属性。
一个例子：
n=11个元素{18,23,11,20,2,7,27,30,42,15,34},
符号表的大小用tablesize=17，
散列函数h为：h = key mod tablesize 取余
----------------------------------------------------------
地址 0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，16
key 34 18 2 20 23 7 42 27 11 30 15
----------------------------------------------------------
存放：存放 h（18）=1，再存h（35）=1时，该位置已经有对象，冲突。
查找：h（22）=5，该地址为空，不在表中。
h（30）=13，该地址存放的是30，找到。
装填因子：
设散列表空间为m，填入个数为n，
装填因子 a = n/m
一个例子：
acos\define\float\exp\char\char\atan\ceil\floor\clock\ctime
顺次存入一张散列表中，
上一个例子用一维数组，一旦存放冲突了就没地方放，所以这里用二维数组来存放，
存放时如果第一个有元素了，就放到第二个备用的位置。
如何设计散列函数 h（key）？
按首字母顺序存放
h（key）= key[0] - 'a'
--------------------------------------------------------
槽0 槽1
0
1
2
...
25
--------------------------------------------------------
这样的存储，如 c 开头的 超过两个元素依然会溢出。
如果不溢出，仅需算出位置直接进行操作，
T查询 = T插入 = T删除 = O(1)
这里我们回顾一下 连续存储结构（数组） 和 非连续存储（链表）的查找区别。
比如下标 2，就可以计算得到这个数据在内存中的位置 1008，
从而对这个位置的数据 进行快速读写访问，时间复杂度为 O(1)
而链表遍历查询时间复杂度为O(N)。
'''
|