【数据结构】哈希表/散列表
本篇博文,旨在介绍哈希表的基本概念及其用法;介绍了减少哈希冲突的方法;并用代码实现了哈希表的线性探测和哈希桶
哈希表的基本概念哈希表是一种存储结构,它通过key值可以直接访问该key值在内存中从存储位置; 将关键值映射到表中的位置访问数据,这个映射函数叫做散列函数,存储数据的表叫做散列表; 构造哈希表的几种方法1、直接定址法根据关键值直接确定元素存取的位置,该散列函数是一个线性函数;例如 Hash(key) = A*key+B,其中,A和B都为常数 2、除留余数法取出关键值后,将关键值除以该散列表的长度从而获得的余数,作为散列地址;Hash(key) = key%m 3、平方取中法取关键字平方后的中间几位为哈希地址。由于一个数的平方的中间几位与这个数的每一位都有关,因而,平方取中法产生冲突的机会相对较小。 平方取中法中所取的位数由表长决定。 例: K = 456,K2 = 207936 若哈希表的长度m=102,则可取79(中间两位)作为哈希函数值。 4、折叠法将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。 5、随机数法选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。 6、数学分析法找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。 哈希冲突/哈希碰撞哈希冲突出现的原因关键值通过任何的散列函数获得的散列地址都有可能是重复的,这种情况叫做哈希冲突; 载荷因子散列表的载荷因子的定义为:a = 表中的元素个数/散列表的长度 对于开放定址法,载荷因子特别重要,一般情况下严格控制在0.7-0.8 超过0.8,哈希表的效率会很低 过低的话,浪费的空间会更大
任何的散列函数都是无法避免的,在处理哈希冲突的方法中,我们介绍下面两种方法 a 用开放定址法来处理哈希冲突a1 线性探测当有需要插入元素的位置已经有元素存在时,则向后遍历寻找空位置
a2 二次探测当插入位置冲突时,则向后寻找,但不是每次只挪动一个位置,而是冲突次数的平方次(1,4,9....)
b 用开链法处理哈希冲突哈希桶是一种顺序表和链表的结合体,定义一个数组,数组存储的内容是节点的指针,下面用一个个桶来存储元素; 这样可以提高哈希表的效率
如何减少哈希冲突a 素数使用素数做除数可以有效的减少哈希冲突 //素数表 const int _PrimeSize = 28; static const unsigned long _PrimeList[_PrimeSize] = { 53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul }; b 字符串哈希算法字符串哈希算法就是将一个字符串转化成一个Key值 字符串哈希算法有很多 下面这个链接有详细的介绍 http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html 代码实现开放定址法的线性检测节点的定义://定义枚举,表示节点的状态 enum Status { EXIST,DELETE,EMPTY,}; //节点的定义 template<typename K,typename V> struct HashNode { K _key; V _value; Status _status; HashNode(const K& key = K(),const V& value = V()) :_key(key),_value(value),_status(EMPTY) {} }; 状态位标识着这个位置有没有值存在,还是之前存在已被删除 哈希表的定义://HashFunc是采用的字符串哈希算法 template<typename K,typename V,typename HashFunc = __HashFunc<K>> class HashTable { typedef HashNode<K,V> Node; public: //缺省的构造函数 HashTable() {} //构造函数 HashTable(size_t size); //将K值转换成哈希值 size_t HashFunC(const K& key); //插入一组值 pair<Node*,bool> Insert(const K& key,const V& value); //查找元素 Node* find(const K& key); //删除一个节点 void Remove(const K& key); protected: vector<Node> _v;//用vector的下标标志位置 size_t _size;//哈希表中元素的数量 protected: //交换两个哈希表 void Swap(HashTable<K,V> &h); //进行容量的判别,进行扩容 void CheckCapacity(); }; 插入函数的实现:pair<Node*,const V& value) { //检查是否需要扩容 CheckCapacity(); //对K值进行取余,判断插入的位置 size_t index = HashFunC(key); //如果存在,则循环着继续寻找 while (_v[index]._status == EXIST) { index++; if (index == _v.size()) index = 0; } _v[index]._key = key; _v[index]._value = value; _v[index]._status = EXIST; _size++; return make_pair<Node*,bool>(&_v[index],true); } 插入函数,要找到关键值对应的位置,冲突的话后移;找到后放入对应的Key和value值,并且将状态位改变即可 查找函数的实现:Node* find(const K& key) { //对K值进行取余,判断插入的位置 size_t index = HashFunC(key); //如果存在,则继续寻找 while (_v[index]._status == EXIST) { //若相等,判断状态是否是删除 //若删除,则没找到,返回空 //若没删除,则返回该位置的地址 if (_v[index]._key == key) { if (_v[index]._status == DELETE) return NULL; return &_v[index]; } index++; if (index == _size) index = 0; } return &_v[index]; } 线性探测中,查找这块有个小问题。当一个关键值是因为冲突后移的话,若后移中的某个值之后删除了,就无法找到这个值了 删除函数的实现:void Remove(const K& key) { //删除仅需要将状态修改 Node* delNode = find(key); if (delNode) delNode->_status = DELETE; } 先查找是否存在,存在的话只需要将状态位修改成删除即可 扩容函数的实现:载荷因子超过0.7时,进行扩容 void CheckCapacity() { //如果_v为空,则扩容到7 if (_v.empty()) { _v.resize(_PrimeList[0]); return; } //如果超过载荷因子,则需要扩容 if (_size*10 / _v.size() >= 7) { /*size_t newSize = 2 * _v.size();*/ size_t index = 0; while (_PrimeList[index] < _v.size()) { index++; } size_t newSize = _PrimeList[index]; //用一个临时变量来存储新生成的哈希表 //生成完成后,将其和_v交换 HashTable<K,V> tmp(newSize); for (size_t i = 0; i < _v.size(); ++i) { //如果存在,则将该位置的哈希值插入到临时的哈希表中 if (_v[i]._status == EXIST) tmp.Insert(_v[i]._key,_v[i]._value); } //交换两个哈希表 Swap(tmp); } } 开链法 哈希桶节点的定义://节点的定义 template<class K,class V> //struct HushNode e2:拼写错误,Hash not hush struct HashNode { K _key; V _value; HashNode<K,V>* _next; HashNode(const K& key,const V& value) :_key(key),_next(NULL) {} }; 插入函数的实现://插入函数的实现 pair<Node*,const V& value) { //插入之前要先进行是否扩容的检查 CheckCapacity(); //找到这个数的位置 size_t index = _HushFunc(key); Node* cur = _ht[index]; while (cur) { if (cur->_key == key) return make_pair(cur,false); cur = cur->_next; } Node* temp = new Node(key,value); temp->_next = _ht[index]; _ht[index] = temp; return make_pair(temp,true); } 用pair可以返回插入成功后节点的指针(或插入失败,相同关键值的指针),以及判断插入成功与否的TRUE或FALSE 删除函数的实现://删除函数的实现 void Erase(const K& key) { //先进行查找这个数的位置 size_t index = _HushFunc(key); Node* pre = NULL; Node* cur = _ht[index]; //删除的时候要进行情况的分析讨论 while (cur) { if (pre == NULL) { _ht[index] = cur->_nex; delete cur; } else { pre->_next = cur->_next; } cur = cur->_next; } delete cur; } 删除元素的时候,需要分两种情况 a、链上有且仅有该节点 出现这种情况,就是pre为空时,仅需修改vector对应位置存储的指针 b、链上除该节点外,还有多个节点 将cur的指向下一个节点的指针给pre的下一个 查找函数的实现://查找函数的实现 Node* Find(const K& key) { for (int i = 0; i<_size; i++) { Node* cur = _ht[i]; while (cur) { if (cur->_key == key) return cur; cur = cur->_next; } } return NULL; } 扩容函数的实现:void CheckCapacity() { //当哈希桶为空的时候或者负载因子为1的时候,进行扩容 if (_ht.size() == 0 || _size / _ht.size() == 1) { //建一个新表 HushTable temp; size_t newsize = GetNewSize(); temp._ht.resize(newsize); //将元素放进去 for (int i = 0; i<_ht.size(); i++) { Node* cur = _ht[i]; while (cur) { temp.Insert(cur->_key,cur->_value); cur = cur->_next; } } } } 与线性探测不同的是,这里当载荷因子为1的时候进行扩容; 哈希桶的一种极端情况是,所有值都往同一个位置进行插入 如下:
解决方法: 当一个链上的节点数量达到一个百分比(自己定义,可以是100%,50%,10%),则不再存储链表,而是存储一颗红黑树 这一避免出现这种极端情况而带了的弊端
哈希表的github代码链接 https://github.com/haohaosong/DataStruct/blob/master/HashTable.h 哈希桶的github代码链接 https://github.com/haohaosong/DataStruct/blob/master/HashTableBucket.h (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |