用哈希表搜索对象

2016-01-29 13:26 8 1 收藏

用哈希表搜索对象,用哈希表搜索对象

【 tulaoshi.com - ASP.NET 】

下载本文代码
下载本期杂志代码
见资源
.NET中的System.Collections.HashTable类存储了对象,因此你可以很快地找到它们。 by Bill Wagner .NET Framework中的大多数容器都是序列式容器(sequence containers):它们按顺序存储对象。这种类型的容器功能很多——你可以以任何特殊的顺序来存储任意数量的对象。然而,这种多功能性是以一定的性能为代价的。在一个序列中查找一个特殊的对象所需要的时间取决于容器中对象的数量。如果我们没有对容器中元素进行排序,那么随着元素数量的增加,你所需要的查找时间也就直线增加了:如果容器中元素的数量增加了一倍,那么你用来查找一个特殊元素的时间也就增加了一倍。然而,如果我们对容器中的元素进行了排序,那么查找时间就是随着元素数量的对数而增加的了:要使查找一个元素的时间增加一倍,你必须使集合中的元素数量增加四倍。如果你用一个key来搜索对象,你可以用比序列式容器更好的方法来存储你的对象。你可以用哈希表(hash table)。哈希表根据一个叫做hash的数字关键字(key)将对象存储在buckets中。hash value是从对象中的值计算得来的一个数字。每个不同的hash value都会创建一个新的bucket。要查找一个对象,你只需要计算这个对象的hash value并搜索相应的bucket就行了。通过快速地找到相应的bucket,就可以减少你需要搜索的对象数量了。例如,设想在一个数据结构中有一些客户记录,你想通过信用卡号来搜索那些记录。一个简单的哈希函数将运用信用卡号的后两位数字,这会形成100个buckets——从00到99的每个两位数的数字都会创建一个bucket。(同样,运用后三位数字会创建1000个buckets。)只需要查询一个bucket,你就可以找到任何记录了,而不需要查询所有的buckets。然而,同任何事情一样,并不是一切都这么简单的。如果你用信用卡号创建了一个哈希函数,而你想通过姓名来查找客户,你就需要查询整个哈希表,这样会花很多时间。这是因为哈希表是用一个不同的字段作为key的。而且,如果你查询整个哈希表,那么元素就没有必要按你期望的顺序来排列了。元素是根据hash value来排列的,而不是根据keys排列的。在本篇文章中,我将详述我在前面的文章中的样例,让你修改一条员工记录。假设有一个很大的公司,公司里有上千位员工,你想用最快的方法来找到一条记录。所有员工的一个哈希表可以使搜索在最短的时间完成。一个哈希函数需要有一定的属性。对于初学者来说,哈希函数必须是不变的。这就是说相同的key必须生成相同的hash value,一旦创建了对象,hash value就不能改变了。如果hash value改变了,你在哈希表中就再也找不到相应的对象了。哈希函数需要的第二个属性就是能够平均分配buckets。如果所有的对象都生成相同的hash value,那么就需要更多的时间来查找一个特殊的对象。实际上,这两个原则是很容易遵循的。在.NET Framework中有178个类重载了GetHashCode(),从而更好地发挥它们的作用。所有的.NET FCL(Framework Class Library)中类的实现都确保了hash value的更好的分配,并遵循了唯一性的原则。你应该确定你自己的类和结构是否需要重载GetHashCode()方法。最简单的(通常也是最好的)方法就是在key中选取一个不变的成员,并运用那个成员所生成的hash value。员工数据库的一个明显的hash key就是社会保险号(Social Security Number)。它不仅不会改变,而且九位数的这个号码也可以让你任意运用以得到你期望的性能。你可以下载样例,看看运用hash keys进行搜索和运用序列式容器进行搜索有什么不同。要把员工添加到一个哈希表中,你可以创建一个九位数的号码并把它作为key: int hash = 111223333;for (int i = 0; i < 100; i++){ string lastname = "Person" + i.ToString(); e = new Employee ("Employee", lastname, (200-i)*200); members.Add(hash++, e);}社会保险号满足了一个好的hash key的要求:它不会改变,它可以合理地分配、value取决于号码而不是reference。(你需要运用基于value的hash key而不是基于reference的hash key以避免我以前提到过的问题。)运用这个hash key来查找对象也很简单: int ssn = Int32.Parse(this.SSN.Text);currentEmp = (Employee)members[ssn];if (currentEmp != null){ LastName.Text = currentEmp.LastName; FirstName.Text = currentEmp.FirstName; Salary.Text = currentEmp.Salary.ToString ();} else LastName.Text = "Not Found";在C#中,你可以用数组语法在哈希表中查找对象。该语法强调了恒定时间搜索的概念:你可以把数组访问看做是一个快速的操作,而不是一个代价很高的函数调用。关于哈希表最后的一个重点是,同所有的集合一样,它们也存储引用(references)。你不需要任何额外的工作来更新哈希表中的对象。一旦你引用了哈希表中的一个对象,你可以随意修改它。记住,同样的原则不适用于keys。你可以编写代码来改变keys,但如果那个代码修改了hash value,你就会丢失你的集合中的对象。哈希表是很有用的、有效的容器。但是,要有效地运用它们,你需要了解容器和容器中对

来源:http://www.tulaoshi.com/n/20160129/1490166.html

延伸阅读
标签: ASP
      假如你拥有一个庞大的网站,内容又多,那么来访者往往很难找到自己所需要的东东,这时候你就需要一个站内搜索来帮助来访者更快的找到索要的资料了!现在你就可以用asp轻易的实现这种功能,何况现在支持asp的站点这么多,利用这个搜索引擎可以搜索到你的主页里面任何一个文件或者软件资料,它可以精确到每个字!...
标签: flash教程
   在我们构造Google 搜索程序之前我们还需要Google Web APIs Developer's Kit,你可以从http ://www.google.com/apis/download.html下截直接解压缩就可以了。里面已经含了所需要的文件和已经编译好的文件,官方地址是http ://www.google.com/apis。不过实际上对我们有用的只是GoogleSearch.wsdl这个文件,把这个文件和SWF文件放在同...
360搜索拍题怎么用?   360搜索APP于6月初上线不久,近日宣布对产品进行首次升级,发布全新1.1版。新版本最大的亮点在于推出了拍题功能,用户使用该功能拍下考卷、作业上的试题照片,就能搜索获得答题结果,瞬间化身学霸轻松解题。 此次360在移动搜索APP添加的这一新的拍题功能,旨在为学生群体提供一个自学、写作业时的学习...
在本篇文章中,我们将讨论下面的问题: 使用C#创建一个简单的COM对象(使用COM的Interop特性)。 从VC++客户端软件中访问COM。客户端软件使用了TypeLibrary(.TLB文件)。 为了简单和方便开发人员使用、测试起见,我们使用了SQLSERVER数据库软件的缺省安装中的Northwind数据库。 修改COM对象中SQLServer的名字,与SQLSe...
什么是数据透视表 大体来说数据透视表就是类似一种图标结合的统计数据方式,相对于死板的数据统计表格或者图像结果来说,数据透视表能够根据用户的一个条件的调整来进行来改变。它算是一个高级的excel功能,只要设定了一定的条件,数据透视表的初始数据变动就会变得更加灵活,方便用户做一些预测性的数据统计。 数据透视表是用来从EXCEL数据...

经验教程

132

收藏

85
微博分享 QQ分享 QQ空间 手机页面 收藏网站 回到头部