Trancy

hash表

 

如何存表

1)直接定址法

  取关键字或者关键字的某个线性函数为Hash地址,即address(key)=a*key+b;如知道学生的学号从2000开始,最大为4000,则可以将address(key)=key-2000作为Hash地址。

  2)平方取中法

  对关键字进行平方运算,然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421,423,436},平方之后的结果为{177241,178929,190096},那么可以取{72,89,00}作为Hash地址。

  3)折叠法

  将关键字拆分成几部分,然后将这几部分组合在一起,以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23,可以将address(key)=89+03+24+12+3作为Hash地址。

  4)除留取余法

  如果知道Hash表的最大长度为m,可以取不大于m的最大质数p,然后对关键字进行取余运算,address(key)=key%p。

  在这里p的选取非常关键,p选择的好的话,能够最大程度地减少冲突,p一般取不大于m的最大质数。

 

冲突的解决

  1)开放定址法

  即当发生冲突时,向下找到第一个为空的放进去。//Q:这怎么查啊,要是还有未插入但属于这个单元的怎么办?

  2)链地址法

   采用数组和链表相结合的办法,将Hash地址相同的记录存储在一张线性表中,而每张表的表头的序号即为计算得到的Hash地址。就是链表,但要是函数选不好复杂度也没减少太多。//即使如此,也比上面那个靠谱太多。。。。

评论