`
gaofen100
  • 浏览: 1179928 次
文章分类
社区版块
存档分类
最新评论

数据结构 查找 哈希表

 
阅读更多

哈希表

查找、插入均为O(1)。

注意两点:

(1)对于静态集,可以构造没有冲突的hash函数;对于动态集合(可以插入、删除),则很难。

(2)尽量找到一个好的hash函数,例如:md5等。

(3)在产生collsion之后,要解决冲突,比如链地址法(拉链,插入时插在表头)。

(4)装载因子(load factor):

a. 在Java中的HashMap中是这样写的:

Asageneralrule,thedefaultloadfactor(.75)offersagoodtradeoffbetweentimeandspacecosts.Highervaluesdecreasethespaceoverheadbutincreasethelookupcost(reflectedinmostoftheoperationsoftheHashMapclass,includinggetandput).Theexpectednumberofentriesinthemapanditsloadfactorshouldbetakenintoaccountwhensettingitsinitialcapacity,soastominimizethenumberofrehashoperations.Iftheinitialcapacityisgreaterthanthemaximumnumberofentriesdividedbytheloadfactor,norehashoperationswilleveroccur.

当LF > 0.75时,要进行rehash。

b. 在Java的编译器GJC1.4中,当LF > 2/3时,进行dble,代码如下:

/***//**
*@(#)Hashtable.java1.1303/01/23
*
*Copyright2003SunMicrosystems,Inc.Allrightsreserved.
*SUNPROPRIETARY/CONFIDENTIAL.Useissubjecttolicenseterms.
*/

packagecom.sun.tools.javac.v8.util;

/***//**
*Agenericsimplifiedversionofjava.util.Hashtable.
*/

publicclassHashtable...{

...

privatevoiddble()...{
hashSize
=hashSize<<1;
hashMask
=hashSize-1;
limit
=limit<<1;
Entry[]oldtable
=table;
table
=newEntry[hashSize];
for(inti=0;i<oldtable.length;i++)...{
for(Entrye=oldtable[i],next=null;e!=null;e=next)...{
next
=e.next;
intix=e.hash&hashMask;
e.next
=table[ix];
table[ix]
=e;
}

}

}


...
}

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics