哈希表-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

哈希表

简介: 参考: http://www.cnblogs.com/dolphin0520/archive/2012/09/28/2700000.html    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。
参考: http://www.cnblogs.com/dolphin0520/archive/2012/09/28/2700000.html   

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表
给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数

Hash表的设计思想

  对于一般的线性表,比如链表,如果要存储联系人信息: 

张三 13980593357
李四 15828662334
王五 13409821234
张帅 13890583472

  那么可能会设计一个结构体包含姓名,手机号码这些信息,然后把4个联系人的信息存到一张链表中。当要查找”李四 15828662334“这条记录是否在这张链表中或者想要得到李四的手机号码时,可能会从链表的头结点开始遍历,依次将每个结点中的姓名同”李四“进行比较,直到查找成功或者失败为止,这种做法的时间复杂度为O(n)。即使采用二叉排序树进行存储,也最多为O(logn)。假设能够通过”李四“这个信息直接获取到该记录在表中的存储位置,就能省掉中间关键字比较的这个环节,复杂度直接降到O(1)。Hash表就能够达到这样的效果。

  Hash表采用一个映射函数 f : key —> address 将关键字映射到该记录在表中的存储位置,从而在想要查找该记录时,可以直接根据关键字和映射关系计算出该记录在表中的存储位置,通常情况下,这种映射关系称作为Hash函数,而通过Hash函数和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置,并不是实际的物理地址)称作为Hash地址。比如上述例子中,假如联系人信息采用Hash表存储,则当想要找到“李四”的信息时,直接根据“李四”和Hash函数计算出Hash地址即可。


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章