目录
- 散列表
- 散列函数
I don’t know how to control myself to fall in study, someday i tell myself what i want, then i fall in it with my mind, then then it seems just end. Remind yourself everyone, is there sometime you tell yourself you can have a day what in your dream.
散列表
在三列的方式下，该元素放在槽h(k)中，即利用散列函数h，由于关键字k计算出槽位。这样可能会产生冲突，所以要利用一些原理来解决冲突，一般使用链接法，像链表那样，将冲突的元素放在后面。一般查找成功的时间为θ（1 + n/m)。
散列函数
散列表的冲突大小是由散列函数决定的，所以一个好的散列函数直接影响散列表的存取效率。
散列表一般运用启发式方法来构造。
除法散列法
取k除以m的余数，将关键字k映射到m个槽中的某一个。一般在选择m的时候选择不太进阶2的整数幂的素数比较好。
乘法散列法
用关键字k乘以常数A(0<A<1)，然后提取小数部分，乘以m，向下取整。这个时候选择m为2的整数幂，因为比较容易实现散列函数，k可以使用一个单字表示。
A为根号5加一除以2是一个比较好的数字。
全域散列法
随机的选择散列函数。
