哈希表原理 灰太狼 2022-03-19 12:10 191阅读 0赞 <table style="width: 677px;"> <tbody> <tr> <td><span style="color: rgb(51, 51, 51);"> 设想一下,你有一个包含约一千条记录的数据文件,比如一个小企业的客户记录,还有一个程序,它把记录读到内存中进行处理。每个记录包含一个唯一的五位数的客户ID号、客户名字、地址、帐户结余等等。假设记录不是按客户ID号顺序分类的,所以,如果程序要将客户ID号作为“key” 来查找一个特殊的客户记录,唯一的查找方法就是连续地搜索每个记录。有时侯,它会很快找到你需要的记录;但有时侯,在程序找到你需要的记录前,它几乎已搜索到了最后一条记录。如果要在1,000条记录中搜索,那么查找任何一条记录都需要程序平均查核500.5 ((1000 + 1 )/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)。
相关 哈希表的原理 哈希概念 线性表、树结构的查找方式都是以关键字的比较为基础,查找效率比较低,顺序表的时间复杂度是O(n),平衡树中为树的高度,即O(logn),搜素的效率取决于搜索过程的 冷不防/ 2024年03月17日 19:28/ 0 赞/ 37 阅读
相关 哈希表原理 什么是哈希表? 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来 叁歲伎倆/ 2022年07月11日 13:28/ 0 赞/ 160 阅读
相关 哈希原理 google搜索到的头条:散列表(也叫哈希表),是根据关键码值直接进行访问的数据结构,也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。 刺骨的言语ヽ痛彻心扉/ 2022年06月13日 12:10/ 0 赞/ 154 阅读
相关 哈希表 我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个数组,为每个可能的关键 快来打我*/ 2022年06月05日 02:20/ 0 赞/ 332 阅读
相关 哈希表 1. 什么是哈希表 我们先来做个题(leetCode上387题) ![70][] public class Solution_387 { 朱雀/ 2022年05月16日 10:11/ 0 赞/ 274 阅读
相关 哈希表基本原理详解 这篇文章是参考视频 思胜 ASP.Net C#培训-7-3-下午-1-哈希表基本原理.wmv http://v.youku.com/v\_show/id\_XMj 短命女/ 2022年03月19日 13:21/ 0 赞/ 232 阅读
相关 哈希表原理 <table style="width: 677px;"> <tbody> <tr> <td><span style="color: rgb(51, 51, 灰太狼/ 2022年03月19日 12:10/ 0 赞/ 192 阅读
相关 哈希表 哈希表是种数据结构,它可以提供快速的插入操作和查找操作。第一次接触哈希表时,它的优点多得让人难以置信。不论哈希表中有多少数据,插入和删除(有时包括侧除)只需要接近常量的时间即0 今天药忘吃喽~/ 2022年02月01日 14:36/ 0 赞/ 378 阅读
相关 【哈希表】 char FirstNotRepeatingChar(char pString) { // invalid input if(! r囧r小猫/ 2022年01月06日 11:33/ 0 赞/ 302 阅读
相关 哈希表 【一】哈希表 > 他通过把关键码值映射到表中的一个位置来访问记录,以加快查找的速度。这个映射函数就是散列函数。 ![watermark_type_ZmFuZ3poZW5na 傷城~/ 2021年08月11日 17:13/ 0 赞/ 529 阅读
还没有评论,来说两句吧...