哈希表原理

灰太狼 2022-03-19 12:10 239阅读 0赞

<table style="width: 677px;"> 
 <tbody> 
  <tr> 
   <td><span style="color: rgb(51, 51, 51);">&nbsp;设想一下，你有一个包含约一千条记录的数据文件,比如一个小企业的客户记录,还有一个程序，它把记录读到内存中进行处理。每个记录包含一个唯一的五位数的客户ID号、客户名字、地址、帐户结余等等。假设记录不是按客户ID号顺序分类的，所以，如果程序要将客户ID号作为“key”&nbsp;来查找一个特殊的客户记录，唯一的查找方法就是连续地搜索每个记录。有时侯，它会很快找到你需要的记录；但有时侯，在程序找到你需要的记录前，它几乎已搜索到了最后一条记录。如果要在1,000条记录中搜索，那么查找任何一条记录都需要程序平均查核500.5&nbsp;((1000&nbsp;+&nbsp;1&nbsp;)/2)条记录。如果你常需要查找数据，你应该需要一个更快的方法来找到一条记录。</span></td> 
   <td align="center"><br></td> 
  </tr> 
 </tbody> 
</table>

一种加快搜索的方法就是把记录分成几段，这样，你就不用搜索一个很大的列表了，而是搜索几个短的列表。对于我们数字式的客户ID号，你可以建10个列表,以0开头的ID号组成一个列表，以1开头的ID号组成一个列表，依此类推。那么要查找客户ID号38016，你只需要搜索以3开头的列表就行了。如果有1,000条记录，每个列表的平均长度为100（1,000条记录被分成10个列表），那么搜索一条记录的平均比较次数就降到了约50。   
当然，如果约十分之一的客户号是以0开头的，另外十分之一是以1开头的，等等，那么这种方法会很适合。如果90%的客户号以0开头，那么那个列表就会有900条记录，每次查找平均需要进行450次比较。另外，程序需要执行的搜索有90%都是针对以0开头的号码的。因此，平均比较数就大大超过简单数学运算的范围了。   
   如果我们可以按这样一种方式在我们的列表中分配记录，情况就会好一些，即每个列表约有相同条目的记录，而不管键值中数字的分布。我们需要一种方法能够把客户号码混合到一起并更好地分布结果。例如，我们可以取号码中的每位数，乘以某个大的数（随着数字位置的不同而不同）， 然后将结果相加产生一个总数，把这个数除以10，并将余数作为索引值（index）(除数相同的分到一组)。当读入记录时，程序在客户号码上运行这个哈希（hash) 函数来确定记录属于哪个列表。当用户需要查询时，将同一个哈希函数作为一个“key”用于客户号码，这样就可以搜索正确的列表了。 像这样的一个数据结构就称为一个哈希表（hashtable)。