黄埔做网站的公司,消防公司宣传册设计样本,国内最先做弹幕的网站,iphone app wordpresshash表原理与实战 专栏内容#xff1a; postgresql使用入门基础手写数据库toadb并发编程 个人主页#xff1a;我的主页 管理社区#xff1a;开源数据库 座右铭#xff1a;天行健#xff0c;君子以自强不息#xff1b;地势坤#xff0c;君子以厚德载物. 文章目录 hash表…hash表原理与实战 专栏内容 postgresql使用入门基础手写数据库toadb并发编程 个人主页我的主页 管理社区开源数据库 座右铭天行健君子以自强不息地势坤君子以厚德载物. 文章目录 hash表原理与实战一、概述 二、hash表整体介绍 2.1 hash表的应用场景 2.2 整体架构 三、hash算法选择 四、hash表操作 4.1 冲突处理 4.2 查找操作 4.3 插入操作 4.4 删除操作 五、总结 结尾 一、概述 hash表的应用非常广泛在网上也可以看到分享的各种hash表的实现都比较概念化。
本章节从实战的角度出发以数据库内核中的应用为例来看看hash表的原理与实现。
二、hash表整体介绍 哈希算法Hash又称摘要算法它的作用是对任意一组输入数据进行计算得到一个固定长度的输出摘要。
哈希算法最重要的特点就是
相同的输入一定得到相同的输出不同的输入大概率得到不同的输出
我们想利用hash算法的这一特性将输入的一组数据经过hash算法计算后输出唯一的 32位或64位的整形值key。
当我们需要找到存储的数据时通过这个key查找而查找整型值的效率就很高了可以用二分法进行查找。
这样一个存储数据的结构我们叫它hash表也就是通常说的key-value形式的存储它的查找效率与数据的类型无关。 2.1 hash表的应用场景
hash表一般用于存储大量的数据而数据的类型是字符串或者更复杂的复合类型结构体或者是更大的数据
直接通过原始数据进行查找时代价非常高将它们转换为hash 值后就可以通过恒定的效率进行查找。
在数据库中的应用有
数据块缓存某个数据块是否已经在缓存中通过对数据块编号的hash值进行查找系统字典的查找某个表是否已经创建了通过表的hash值进行查找hash索引记录数据的hash值查找时按hash值进行查找 2.2 整体架构
hash表的实现一般由几方面组成hash算法bucket计算冲突处理key-value对应形式以及三种操作。 既然是一个table那么内部基本存储结构是一个数组数组的最大元素个数就是capacity数组中的每个元索叫做bucket桶来存储key-value对数据bucket位置的计算一般会采用 hash值 % capacity 来计算hash值一般是一个32位64位或者128位的整数取余后得到数组中的下标这就是当前key-value要存储的位置
三、hash算法选择 查找主要依赖高效的hash值的计算一个高效碰撞少的算法能让hashtable的效率大大提升。
常见的hash算法有MD5, sha-256等这些常用于加密而hashtable并不需要对数据进行加密更看重计算的效率。
由此出现了一些快速hash算法比较有名的如
murmurhash3, 这是第三个版本速度公认的非常快开源了各种语言实现Spookyhash这个目前支持128位cityhash是google发布的会利用现代CPU的特性进行性能提升对于低于64位的输入处理比较复杂
建议使用murmurhash3算法简单高效对于较少的输入也能高效处理。
这些算法都可以在github上下载得到加入.c,.h文件后就可以直接调用使用。
类似如下调用
seed 123456789
data example data
hash_value murmur_hash(seed, data)四、hash表操作 hash表的操作一般有插入查找删除三类基本操作。
对于修改操作可以分解为这三项的组合先查找再删除然后插入因为修改后的键值发生变化对于它在hash表中的位置也会发生变化。 4.1 冲突处理
在开始操作之前需要注意一种情况因为我们数组元素个数有限在取余之后难免会出现多个key-value数据在相同位置的情况也就是key产生了冲突。
一般有两种处理方式
一是在冲突位置往后继续找空位置存储二是在当前桶内以链表的形式存储
两种不同的冲突处理对应了后面操作的不同。这里采用第二种方法如果有多个相同数据在同一桶中时以单链表的形式存储。 图中可以看到出现冲突时key4,key5直接追加到key1后面。
那么定义数组元素类型时就要定义为链表形式。
typedef unsigned long long HASHKEY; typedef struct HashElement
{struct HashElement *link;HASHKEY hashKey;char *value;
}HashElement;这里定义hash为64位的整形当然可以是其它位数。 4.2 查找操作
查找一个key-value值是否在hashtable中的步骤如下
调用hash算法接口计算value的hash值按找hash值计算bucket位置找到bucket查看是否为空如果bucket中有多个元素遍历链表进行比对hash值如果存在相同的hash值元素则找到否则没有找到。
获取hashkey函数
#define Hash_capacity 100
HashElement * hashtable[Hash_capacity];HASHKEY getHashKey(char *value, int valueSize)
{return spooky_hash64(value, valueSize, 0);
}获取bucket函数
int GetBucketIndex(HASHKEY key, PHashTableInfo hashTableInfo)
{int bucket key Hash_capacity;return bucket;
}
查找函数
HashElement* HashFindEntry(char *value)
{HashElement *entry NULL;int bucket 0;HASHKEY key 0;key getHashKey(value, strlen(value));bucket GetBucketIndex(key);entry GetHashEntryFromBucket(hashtable[bucket], key);return entry;
}
从bucket链中查找
HashElement* GetHashEntryFromBucket(HashElement* bucket, HASHKEY key)
{HashElement* element bucket;while(element ! NULL){if(element-hashKey key) {return element;}element element-link;}return NULL;
}当然这里除取比较key值外还可以对value定义比较函数这样避免hash值冲突的情况。 4.3 插入操作
插入操作就比较简单步骤如下
计算hash 值根据hash值获取bucket位置存储对应bucket如果已经有元素存到链到头部
HashElement* HashInsertEntry(char *value)
{HashElement *entry NULL;int bucket 0;HASHKEY key 0;key getHashKey(value, strlen(value));bucket GetBucketIndex(key);entry malloc(sizeof(HashElement));if(NULL entry){return NULL;}entry-link NULL;entry-hashKey key;entry-value value;if(NULL ! hashtable[bucket])entry-link hashtable[bucket];hashtable[bucket] entry;return entry;
}hash节点数量不确定故采用动态内存分配
在冲突时采用了头插法这样操作比较简单 4.4 删除操作
从hash表中找到并删除一个元素的步骤如下
计算value的hash值计算对应的bucket位置从bucket链中进行查找同时记录下它的前继将对应key的元素从链表中删除注意链表只有一个元素的情况将删除的元素返回由调用者释放内存空间
HashElement* DeleteHashEntry(char *value)
{HashElement *pre NULL;HashElement* element NULL;int bucket 0;HASHKEY key 0;key getHashKey(value, strlen(value));bucket GetBucketIndex(key);pre element hashtable[bucket];while(element ! NULL){if(element-hashKey key) {if(pre element){hashtable[bucket] NULL;}else{pre-link element-link;}return element;}pre element;element element-link;}return NULL;
}五、总结 本文介绍了哈希表的实现及原理同时介绍了几种hash计算方法。
当然本节介绍的内容都是在没有并发冲突的情况下使用如果多线程操作时需要进行加锁处理。
如果需要更高效的并发场景下的hash表后面章节会继续介绍。
结尾 非常感谢大家的支持在浏览的同时别忘了留下您宝贵的评论如果觉得值得鼓励请点赞收藏我会更加努力 作者邮箱studysenllang.onaliyun.com 如有错误或者疏漏欢迎指出互相学习。
注未经同意不得转载
