社区导航

 

搜索
查看: 4042|回复: 9

[讨论] 闲聊哈希表 (上)

[复制链接]

1752

TA的帖子

0

TA的资源

裸片初长成(初级)

Rank: 10Rank: 10Rank: 10

发表于 2010-3-4 20:49 | 显示全部楼层 |阅读模式
经典数据结构教科书中,“表”是数据结构的一个大家族。其中,有顺序表(数组)、单向链表、双向链表、循环链表等等。我们今天聊的不是这些,而是“表”中的异类——哈希表(Hash Table)

为什么会有哈希表这种数据结构呢?让我们用一个通俗的例子来理解:
大家一定都查过字典吧,我们知道,《新华字典》是按照读音排序的,可以理解为一个以读音为key,按升序排列的数据库。对于读音已知的字,可以通过“二分查找法”,很快地查找到要找的字,其时间复杂度为O(log2n)。但是,对于不知道读音的字怎么办呢?如果使用“顺序查找”,一页一页地翻字典,假设一本新华字典600页,每翻查一页的时间开销为0.5分钟,那么,每查到一个字耗费的时间t的数学期望值E(t) = 600 * 0.5min / 2 =150min,也就是查一个字需要两个半小时!当然,这是难以接受的!
为了解决这个问题,《新华字典》的编辑们,很快就想出了解决办法,那就是在字典的前面加入一个“检字表”,如“四角号码检字表”“部首检字表”等,其特点是以每个字的字形为依据,计算出一个索引值,并映射到对应的页数。比如“法”字,按四角号码检字法,其索引值为34131,再根据这个数值,就可以找到相应的字了。在这种情况下,查找算法的时间复杂度接近于O(1)。换句话说,字典再厚,也不会明显地影响到查字典的效率了。

好,让我们回到计算机的世界中来。
哈希表的最大特点,是数据存储位置(偏移量)和数据记录的内容相关,存在着一个函数换算关系:
Offset = Hash (Key)
其中,Offset为数据存储的偏移量,Hash为散列函数(Hash Function)Content为数据记录内容的关键字(Hash Key)。假设,我们要建立一张EEWorld全球访问量统计表,每条记录包含下面的数据结构:
struct access_record_t {

unsigned index_i; /* Index*/

charcountry_name[MAX_COUNTRY_NAME_LEN]; /* 国家/地区名 */

unsigned long long access_count;/* 访问量 */
};

我们可以用一个一维数组access_record存储这张表,其中access_record[index_i]为编号为index_i的国家的记录,也就是说,数据的存储位置由index_i值唯一确定。例如,中国大陆的index_i值为86,那么,access_record[86].access_count即为EEWorld在中国大陆地区的访问量。
然而,我们知道,“China”比起数字86来,明显更接近自然语言,对于人脑的记忆来说更方便,所以,我们能不能想一个办法,做一个从国家/地区名到数字索引的映射呢?这就涉及到散列函数(Hash Function)了。

评分

2

查看全部评分



1916

TA的帖子

0

TA的资源

五彩晶圆(中级)

Rank: 8Rank: 8

发表于 2010-3-4 21:15 | 显示全部楼层
呵呵,见到这个词汇的时候,是在大二的软件工程课程上,还真忘记了啥子事哈希表了,只知道是一种查找方法,呵呵!
有目的的学习是最有效的学习!


回复

使用道具 举报

1752

TA的帖子

0

TA的资源

裸片初长成(初级)

Rank: 10Rank: 10Rank: 10

 楼主| 发表于 2010-3-4 21:21 | 显示全部楼层

回复 沙发 zqzq501311 的帖子

如果你以后从事通讯设备的开发,或者数据库开发,对Hash函数和Hash Table的掌握是一项基本功。
建议你好好看看这一块,再自己写一些小程序练习练习。
我会给大家出一个Hash表的练习题,是从我的实际工作中提取的。如果想深入理解Hash表,不妨做一做。


回复

使用道具 举报

4

TA的帖子

0

TA的资源

一粒金砂(初级)

Rank: 1

发表于 2010-3-5 12:42 | 显示全部楼层
介绍的不错


回复

使用道具 举报

580

TA的帖子

0

TA的资源

五彩晶圆(初级)

Rank: 7Rank: 7Rank: 7

发表于 2010-3-5 21:47 | 显示全部楼层
hash的确应用比较多,做数据库这块也hash、hash的不少,开发OPC的时候也遇到了hash,呵呵,可惜对hash的理解不够深入,向楼主学习了!!!


回复

使用道具 举报

768

TA的帖子

0

TA的资源

纯净的硅(中级)

Rank: 5Rank: 5

发表于 2010-3-6 14:14 | 显示全部楼层
看来要学的知识还真是太多啦,自己为自己加加油!


回复

使用道具 举报

324

TA的帖子

0

TA的资源

一粒金砂(中级)

Rank: 2

发表于 2010-3-6 16:40 | 显示全部楼层
路过,看看热闹


回复

使用道具 举报

2万

TA的帖子

74

TA的资源

管理员

Rank: 13Rank: 13Rank: 13Rank: 13

发表于 2010-3-6 23:05 | 显示全部楼层
呵呵 多跟richie学学
2018,加油!继续为中国电子行业做出小小的贡献吧!
QQ 1206973913


回复

使用道具 举报

3196

TA的帖子

0

TA的资源

纯净的硅(初级)

Rank: 4

发表于 2010-4-9 16:44 | 显示全部楼层
受教于hash表 上
不断地学习,才会有创新!
淘宝小店:手机、qq点卡、游戏点卡自动充值 http://shop63727265.taobao.com/


回复

使用道具 举报

2

TA的帖子

0

TA的资源

一粒金砂(初级)

Rank: 1

发表于 2010-4-9 21:05 | 显示全部楼层
好东西 这几天在看数据结构 来得正好:D


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

  • 论坛活动 E手掌握

    扫码关注
    EEWORLD 官方微信

  • EE福利  唾手可得

    扫码关注
    EE福利 唾手可得

Archiver|手机版|小黑屋|电子工程世界 ( 京ICP证 060456 )

GMT+8, 2019-4-19 22:14 , Processed in 0.284499 second(s), 18 queries , Gzip On, MemCache On.

快速回复 返回顶部 返回列表