README
¶
散列表（Hash table）
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
构造散列函数
散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。
-
直接定址法：
取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k或hash(k)=a*k+b，其中a, b为常数（这种散列函数叫做自身函数）
-
数字分析法：
假设关键字是以r为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
-
平方取中法：
取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
-
折叠法：
将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
-
随机数法
-
除留余数法：
取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即hash(k)=k mod p, p <= m。不仅可以对关键字直接取模，也可在折叠法、平方取中法等运算之后取模。对p的选择很重要，一般取素数或m，若p选择不好，容易产生冲突。
处理冲突
为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。
分离链表法（Separate chaining）
将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。
开放定址法（Open addressing hashing）
hash{i} = (hash(key)+d{i}) mod m, i = 1,2,...k(k<=m-1)，其中hash(key)为散列函数，m为散列表长，d{i}为增量序列，i为已发生冲突的次数。
Documentation
¶
Index ¶
Constants ¶
const ( // A = (sqrt(5) -1)/2，来自算法导论第三版 A = 0.6180339887 MinSize = 10 // Maximum average load of a bucket that triggers growth. LoadFactor = 0.65 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Source Files