数据结构——哈希表、哈希桶

本文来自:IT宝库(https://www.itbaoku.cn)

哈希概念

顺序结构以及平衡树中,元素关键码与其存储位置之间没有对应的关系,因此在查找一个元素时,必须要经过关键码的多次比较,顺序查找时间复杂度为O(N),平衡树中为树的高度,即O(logN),搜索的效率取决于搜索过程种元素的比较次数。

理想的搜索方法:可以不经过任何比较,一次直接从表中得到想要的搜索元素。如果构造一种存储结构,通过某种函数()HashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系,那么在查找时通过该函数可以很快找到该元素。

当向该结构中:

1.插入元素

                根据待插入元素的关键码,以此函数计算出该元素的存储位置并按此位置进行存放。

2.搜索元素

                对元素的关键码进行同样的计算,把求得的函数值当做元素的存储位置,在结构中按此位置取元素比较,若关键码相等,则搜索成功。

该方式即为哈希(散列)方法,哈希方法中使用的转换函数称为哈希(散列)函数,构造出来的结构称为哈希表(Hash Table)或者散列表。

例如:数据集合{1,7,6,4,5,9};

哈希函数设置为hash(key) = key % capacity  capacity为存储元素底层空间总的大小。

用同该方法进行搜索不必进行多次关键码的比较,因此搜索的速度比较快

哈希冲突

对于:4、14这两个元素的关键字,在上述的哈希函数中计算的哈希值都为4,此时就会存在哈希冲突,即:不同关键字通过相同的哈希函数计算出相同的哈希地址,该种现象称为哈希冲突或哈希碰撞。

哈希函数

引发哈希冲突的一个原因可能是:哈希函数设计不够合理。

哈希函数设计原则:

1.哈希函数的定义域必须包括需要存储的全部关键码,而如果散列表允许有m个地址是,其值域必须在0到m-1之间

2.哈希函数计算出来的地址能均匀分布在整个空间

3.哈希函数应该比较简单

常见的哈希函数:

1.直接定值法(常用)

取关键字的某个线性函数为散列地址:Hash(key) = A*key +B

优点:简单、均匀

缺点:需要事先知道关键字的分布情况

使用场景:适合查找比较小且连续的情况

2.除留余数法(常用)

设散列表允许的地址数为m,取一个不大于m,但是接近或等于m的质数p作为除数。

按照哈希函数:Hash(key) = key % p(p<=m),将关键码转换成哈希地址

优点:使用场景广泛,不受限制。
缺点:存在哈希冲突,需要解决哈希冲突,哈希冲突越多,效率下降越厉害。

3.平方取中法

假设关键字为1234,对它平方就是1522756,抽取中间的3位227作为哈希地址。

使用场景:不知道关键字的分布,而位数又不是很大的情况。

4.折叠法

折叠法是将关键字从左到右侧分割成位数相等的几部分(最后一部分可以短些),然后将这几部分叠加求和,并按散列表表长,取后几位作为散列地址

折叠法适合事先不需要知道关键字的分布,适合关键字位数比较多的情况

5.随机数法 

选择一个随机函数,取关键字的随机函数值为它的哈希地址,即H a s h ( K e y ) = r a n d o m ( K e y ) Hash(Key)=random(Key)Hash(Key)=random(Key),其中random为随机数函数。

使用场景:通常应用于关键字长度不等时。

 6.数学分析法

设有n个d位数,每一位可能有r种不同的符号,这r中不同的符号在各位上出现的频率不一定相同,可能在某些位上分布比较均匀,每种符号出现的机会均等,而在某些位上分布不均匀,只有几种符号经常出现。此时,我们可根据哈希表的大小,选择其中各种符号分布均匀的若干位作为哈希地址。

 

假设要存储某家公司员工登记表,如果用手机号作为关键字,那么极有可能前7位都是相同的,那么我们可以选择后面的四位作为哈希地址。

如果这样的抽取方式还容易出现冲突,还可以对抽取出来的数字进行反转(如1234改成4321)、右环位移(如1234改成4123)、左环位移(如1234改成2341)、前两数与后两数叠加(如1234改成12+34=46)等操作。

数字分析法通常适合处理关键字位数比较大的情况,或事先知道关键字的分布且关键字的若干位分布较均匀的情况。

注意:哈希函数设计的越精妙,产生哈希冲突的可能性越低,但是无法避免哈希冲突。

哈希冲突解决

闭散列(开放定址法)

闭散列:也叫开放定址法,当发生哈希冲突时,如果哈希表未被填满,说明在哈希表中必然还有空的位置,那么可以把key存放在冲突位置中的“下一个”空位置去。那么如何寻找下一个空位置呢?

1.线性探测

比如下图的场景中:需要插入44,先计算哈希地址,为4,因此应该插入在4的位置,但是该地方已经放入了元素为4的值,此时发生了哈希冲突

线性探测:从发生冲突的位置开始,依次向后探测,知道寻找到下一个空位置为止。

一:插入步骤:

        1.通过哈希函数获取待插入元素在哈希表的位置

        2.如果该位置没有元素则直接插入新元素,如果该位置中已经有元素(发生哈希冲突),那么使用线性探测找到下一个空位置,插入新元素。

 二:删除步骤:

        采用闭散列处理哈希冲突时,不能随便物理删除哈希表中已有的元素,若直接删除元素会影响其他元素的搜索。比如删除元素4,如果直接删掉,44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

2.二次探测

二次探测:i的2次方,i为查找次数,例如下图:

第一次为1,第二次为4,第三次为9,依次类推

所以下图的44是在第二次查找中找到了空位置并插入

开散列 (链地址法)

开散列又叫链地址法,首先对关键码集合用散列函数计算散列地址,具有相同地址的关键码归于同一子合集,每一个子集合称为一个桶,各个桶中的元素通过一个单链表链接起来,各链表的头结点存储在哈希表中,例如下图:

 从上图可以看出,开散列中每个桶中放的都是发生哈希冲突的元素。

负载因子

负载因子 = 表中有效数据个数 / 空间的大小

负载因子越大,产出冲突的概率越高,增删查改的效率越低。

负载因子越小,产出冲突的概率越低,增删查改的效率越高。

负载因子越小,也就意味着空间的利用率越低,此时大量的空间实际上都被浪费了。对于闭散列(开放定址法)来说,负载因子是特别重要的因素,一般控制在0.7~0.8以下,超过0.8会导致在查表时CPU缓存不命中(cache missing)按照指数曲线上升。
因此,一些采用开放定址法的hash库,如JAVA的系统库限制了负载因子为0.75,当超过该值时,会对哈希表进行增容。

一但负载因子超出设定值,那么该表需要扩容处理。

一般来说,在闭散列中负载因子设置为0.7,在开散列中负载因子设置为1

哈希表模拟实现

哈希表的结构

首先,我们得存储该位置的状态信息,定义一个枚举变量,状态分别为:

1.EMPTY

2.EXIST

3.DELEDE

许多同学会想,我们为什么要多定义一个DELEDE的状态呢?

我们在前面的学习中发现,在搜索元素的时候,找到空位置即停止,那么假设在搜索过程中,原本存在的数据被删除了,那么此时还要不要继续搜索呢?原本应该搜索到的元素,在中途因为某一个元素的删除而判定空,该怎么办呢?

所以就有了DELETE的状态。

在删除的时候将状态更改为DELETE,停止条件为遇到EMPTY则停止,那么就能顺利搜索了。

    //状态enum Status{EMPTY,//空EXIST,//存在DELETE//删除};

 每个哈希值结构除了存在键值对,还需要存在状态变量来存储状态,初始化都为空。

    //哈希值结构template<class K,class V>struct HashData{pair<K, V> _kv;//键值对Status _s = EMPTY;//状态};

在哈希类中,为了在插入元素时好计算当前哈希表的负载因子,我们还应该时刻存储整个哈希表中的有效元素个数,当负载因子过大时就应该进行哈希表的增容。

    //哈希类template<class K, class V>class HashTable{public://构造函数HashTables()//构造函数初始化空间为10{_tables.resize(10);}//析构函数~HashTables()//...private:vector<HashData<K, V>> _tables;size_t _n = 0;//存储关键字的格个数};

哈希表的插入

插入步骤:

1.检查是否存在插入的值 

这里我们按照Find函数进行直接查找即可,如果不为空,那么就说明有了,返回false,如果没查找到,那么说明该值不存在,进入下一步骤。

2.检查负载因子是否超过0.7,超过需要扩容

如果负载因子超过0.7,那么该表就需要扩容了

扩容又分为三步:

1.new一个新表出来

2.将旧表中的数据一一重新inser进新表,注意此时哈希函数也会发生变化。

3.将新旧表交换,因为新表才是我们需要的

如果负载因子没有超过设定值,那么开始寻找插入位置并插入

3.线性探测插入

先计算好该元素对应的哈希值,然后从该哈希值对应的位置开始,如果该位置已经存在,存在哈希冲突,那么按照线性探测往前寻找,如果遇到EXIST就继续往前,遇到EMPTY和DELETE那么就可以插入了。

        //插入函数bool Insert(const pair<K, V>& kv){//用find判断是否已经有了if (Find(kv.first)){return false;}//负载因子if (_n * 10 / _tables.size() >= 7)//如果负载因子>0.7,那么需要扩容{//开新表size_t newsize = _tables.size() * 2;HashTable<K, V> newht;newht._tables.resize(newsize);//遍历旧表for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]._s == EXIST){newht.Insert(_tables[i]._kv);}}//交换新旧表_tables.swap(newht._tables);}size_t hash = kv.first % _tables.size();//计算哈希值//开始寻找可插入位置while (_tables[hash]._s == EXIST)//如果该位置已经有值,那么线性向前探测{hash++;//线性探测,每次往前一位探测hash %= _tables.size();//防止探测越界}//开始插入_tables[hash]._kv = kv;_tables[hash]._s = EXIST;++_n;return true;}

哈希表的查找

 查找的方式很简单

1.计算哈希值

2. 从哈希值对应的位置开始查找

这里只要遇到不为空的都继续查找,因为插入的时候是线性探测,只要存在哈希冲突,那么往前查找到为空的就插入,也就是说只要遇到空就一定找不到。

        //查找函数HashData<K, V>* Find(const K& key){size_t hash = key % _tables.size();//计算哈希值while (_tables[hash]._s != EMPTY)//找到位置为空的就停止寻找{if (_tables[hash]._kv.first == key && _tables[hash]._s == EMPTY)//找到了{return &_tables[hash];//返回地址}//如果没找到,线性往前探测hash++;hash %= _tables.size();//防止探测越界}//出了循环return NULL;//返回空}

哈希表的删除

哈希表的删除也很简单

1.通过find函数查找到元素对应的地址

 2.将该地址的状态改为DELETE即可,也就是伪删除,最后删除成功

3.如果地址为空,说明要删除的元素不存在,删除失败

        //删除函数bool Erase(const K& key){HashData<K, V>* ret = Find(key);//先获取key的地址if (ret != NULL)//如果地址不为空,说明存在{ret->_s = DELETE;//状态改为删除--_n;//空间-1return true;}else//如果地址为空{return false;//删除失败}}

哈希桶模拟实现

哈希桶的结构

在开散列的哈希表中,哈希表的每个位置存储的实际上是某个单链表的头结点,即每个哈希桶中存储的数据实际上是一个结点类型,该结点类型除了存储所给数据之外,还需要存储一个结点指针用于指向下一个结点。

    template<class K,class V>struct HashNode{HashNode* _next;pair<K, V> _kv;HashNode(const pair<K, V>& kv):_kv(kv),_next(nullptr){}};

与闭散列的哈希表不同的是,在实现开散列的哈希表时,我们不用为哈希表中的每个位置设置一个状态字段,因为在开散列的哈希表中,我们将哈希地址相同的元素都放到了同一个哈希桶中,并不需要经过探测寻找所谓的“下一个位置”。

哈希表的开散列实现方式,在插入数据时也需要根据负载因子判断是否需要增容,所以我们也应该时刻存储整个哈希表中的有效元素个数,当负载因子过大时就应该进行哈希表的增容。

    template<class K,class V>class HashTables{typedef HashNode<K, V> Node;public://构造函数HashTables()//构造函数初始化空间为10{_tables.resize(10);}//析构函数~HashTables();//...private:vector<Node*> _tables;size_t _n = 0;};

哈希桶的插入

 插入的步骤和哈希表类似

1.通过find函数判断该元素是否存在

2. 检查负载因子是否超出设定值,超出则需要扩容

扩容的步骤如下:

1.开新表。

2.遍历旧表,将结点逐一挪到新表并将旧表置空。

3. 交换新旧表,因为新表才是我们需要的。

        //插入函数bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}//负载因子if (_n == _tables.size())//因子到1开始扩容{//开新表vector<Node*> newtables;newtables.resize(_tables.size() * 2, nullptr);//遍历旧表for (size_t i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;//记录下一个的地址size_t hash = cur->_kv.first % newtables.size();//计算哈希值//头插cur->_next = newtables[i];newtables[i] = cur;//更新下一个位置cur = next;}//将表置空_tables[i] = nullptr;}//交换新旧表_tables.swap(newtables);}size_t hash = kv.first % _tables.size();//计算哈希值Node* newnode = new Node(kv);//创建结点//头插newnode->_next = _tables[hash];_tables[hash] = newnode;++_n;return true;}

哈希桶的查找

在哈希表中查找数据的步骤如下:

1.计算哈希值

2.通过哈希值寻找位置

3.从该位置开始循环查找 

循环的步骤如下:

1.判断是否相同,相同则返回找到的地址

2.不相同则判断下一个

3.出了循环还没找到那么返回空

        //查找函数Node* Find(const K& key){size_t hash = key % _tables.size();//计算哈希值Node* cur = _tables[hash];//寻找位置while (cur)//cur不为空则继续寻找{if (cur->_kv.first == key)//相同则找到{return cur;//返回找到的地址}//不相同则判断下一个cur = cur->_next;}//出循环还没找到则返回空return NULL;}

哈希桶的删除

 删除的步骤如下:

1.计算哈希值,并记录哈希值对应当前位置和前一个结点的地址(NULL)

2.进入循环,判断是否相同,相同则删除,然后将前一个结点连接下一个结点。不相同则继续判断下一个,更改cur和prev的地址

 3.出了循环还没找到则删除失败

        //删除函数bool Erase(const K& key){size_t hash = key % _tables.size();//计算哈希值Node* prev = nullptr;//记录前地址Node* cur = _tables[hash];//记录当前地址while (cur)//不为空则继续寻找{if (cur->_kv.first == key)//相同则找到{if (prev == nullptr)//如果为头删{_tables[hash] = cur->_next;//将下一个结点地址放到指针数组上}else{prev->_next = cur->_next;//将前一个结点连接后一个地址}delete cur;//删除找到的结点return true;}prev = cur;cur = cur->_next;}//出循环还没找到则删除失败return false;}