散列表

递哈希表

Posted by Jow on June 25, 2019

目录

  1. 散列表
  2. 散列函数

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是一个比较好的数字。

全域散列法

随机的选择散列函数。