wikipedia上的解释
http://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
下图示意了哈希表(Hash Table)这种数据结构。
如上图所示,首先分配一个指针数组,数组的每个元素是一个链表的头指针,每个链表称为一个槽(Slot)。哪个数据应该放入哪个槽中由哈希函数决定,在这个例子中我们简单地选取哈希函数h(x) = x % 11,这样任意数据x都可以映射成0~10之间的一个数,就是槽的编号,将数据放入某个槽的操作就是链表的插入操作。
如果每个槽里至多只有一个数据,可以想像这种情况下search
、insert
和delete
操作的时间复杂度都是O(1),但有时会有多个数据被哈希函数映射到同一个槽中,这称为碰撞(Collision),设计一个好的哈希函数可以把数据比较均匀地分布到各个槽中,尽量避免碰撞。如果能把n个数据比较均匀地分布到m个槽中,每个糟里约有n/m个数据,则search
、insert
和delete
和操作的时间复杂度都是O(n/m),如果n和m的比是常数,则时间复杂度仍然是O(1)。一般来说,要处理的数据越多,构造哈希表时分配的槽也应该越多,所以n和m成正比这个假设是成立的。
请读者自己编写程序构造这样一个哈希表,并实现search
、insert
和delete
操作。
如果用我们学过的各种数据结构来表示n个数据的集合,下表是search
、insert
和delete
操作在平均情况下的时间复杂度比较。
各种数据结构的search、insert和delete操作在平均情况下的时间复杂度比较
数据结构
search
insert
delete
数组 |
O(n),有序数组折半查找是O(lgn) |
O(n) |
O(n) |
双向链表 |
O(n) |
O(1) |
O(1) |
排序二叉树 |
O(lgn) |
O(lgn) |
O(lgn) |
哈希表(n与槽数m成正比) |
O(1) |
O(1) |
O(1) |
根据以上算法,抽象数据结构如下:
/*哈希表*/
struct obj_container {
obj_hash_fn *hash_fn;//哈希函数
obj_callback_fn *cmp_fn;
int n_buckets; //分配多少个slot ?
int elements; //哈希表中元素数目
int version;
/*!variable size */
struct bucket buckets[0]; /*! lengthen tailq, each bucket is a linkedlist */
};
// 每个slot 为一个链表
struct bucket_entry {
SPD_LIST_ENTRY(bucket_entry)entry;
int version;
struct obj *pobj; /* pointer to internal data */
}bucket;
接下来实现 search, link , unlink函数。
分享到:
相关推荐
数据结构之哈希表.pdf
严蔚敏 数据结构 ppt 哈希表 数 图 严蔚敏 数据结构 ppt 哈希表 数 图 严蔚敏 数据结构 ppt 哈希表 数 图
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过R,完成相应的建表和查表程序。 假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2...
Java数据结构 线性表,链表,哈希表是常用的数据结构,在进行Java开发时,JDK已经为我们提供了一系列相应的类来实现基本的数据结构
数据结构课设 哈希表 C++源码 需要的拿去
这是我们数据结构哈希表的实验报告,是严格按照实验报告格式来的,自己做的,希望能帮到你
数据结构试验 哈希表的设计及实现 C语言 源代码
这是数据结构中关于哈希表这个知识的实现,是使用C++实现的,那么希望能够对学校数据结构的哈希表这个知识点的朋友能有帮助
数据结构里哈希表的实验报告 构造二叉树,构造哈希表等 c语言版
数据结构中的哈希表详细解析,有力与对数据结构的理解,更有利于对哈希表的理解,其中的是C语言
哈希表的代码,可以用于数据结构试验交作业或者用于写实验报告
数据结构 (课程设计)哈希表实现数据结构 (课程设计)哈希表实现
这是关于哈希表设计的一种程序,在数据结构设计中的一个重要方面
数据结构中的哈希表查找,代码有注释,理解算法后理解代码非常容易看懂
这是数据结构中哈希表的实现代码,请大家在需要的时候尽量的下载。
哈希表的设计与实现——链地址法 问题描述: 设计哈希表实现电话号码查找系统。 基本要求: (1)设每个记录有下列数据项:电话号码、用户名、地址; (2)从文件中读取各记录,分别以电话号码和用户名为关键字建立...
数据结构哈希表的实现,很值得初学者的学习与应用,看完代买能够掌握基本哈希表的应用
问题描述:针对某个集体中人名设计哈希表,并完成相应的建表和查表程序。 要求: (1)假设人名为中国人姓名的汉语拼音形式。名称的长度不少于3个字符、不多于10个字符; (2)随机生成人名列表,个数不少于3000个,...
设计哈希表实现电话号码查询系统 数据结构课程设计