devbox
运维做开发
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

[数据结构] --- 哈希表

作者：运维做开发 | 2024-08-14 23:03:48

赞

踩

哈希表

1 哈希表概念

1.1 什么是哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构 。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度（在此之前的我们都是采用遍历来查找指定元素，当数据量庞大时（亿万级别），挨个遍历就显得很慢，而哈希表可以通过某个函数直接访问到指定元素，这就是哈希表的NB之处）。这个映射函数叫做散列函数或者哈希函数，存放记录的数组叫做散列表。

1.2 为什么会有哈希表

数组的特点是：寻址容易，插入和删除困难；
链表的特点是：寻址困难，插入和删除容易。
那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表数据结构了。

1.3 哈希表的实现原理

哈希表hash table(key，value) 是将对象的Key通过哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，（这里为什么要提到数组？因为哈希表地底层实现是数组，这也随之带来了一些问题，后文解惑：）取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。）

这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

1.4 常见哈希函数的设计

< 1 > 直接定制法(常用):
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关 键字的分布情况 使用场景：适合查找比较小且连续的情况

< 2 > 除留余数法(常用):
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p<=m)，将关键码转换成哈希地址。

< 3 > 平方取中法(了解):
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对 它平方就是18671041，抽取中间的3位671(或710)作为哈希地址
平方取中法比较适合：不知道关键字的分 布，而位数又不是很大的情况

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

< 5 > 随机数法(了解):
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和， 并按散列表表长，取后几位作为散列地址。

2 哈希冲突及其解决方式

2.1 哈希冲突

哈希冲突（Hash Collision）指的是不同的键经过哈希函数计算后得到相同的哈希值，导致它们被映射到哈希表存储数组的同一位置。哈希冲突是使用哈希表时常常会遇到的问题，因为哈希函数将一个更大的键域映射到一个较小的索引空间，碰撞是不可避免的。

2.2 如何解决哈希冲突

解决哈希冲突的方法有多种，下面介绍常见的两种方法：开放寻址法和链地址法（又叫闭散列和开散列）。
在这里插入图片描述

2.2.1 链地址法

开散列方法又叫链地址法，哈希表中存储的是链表的头结点。链地址法有2种实现方式。

  • 数组 + 链表
  • 数组 + 二叉树

下面以数组+链表的方式进行介绍，具有相同的哈希地址会存放在同一链表中，每个链表中的元素都具有相同的哈希地址。
在这里插入图片描述
该哈希表示由指针数组来组成的，每个数组中的元素都是一个链表的头指针。从该表中我们可以看出，产生哈希冲突的元素并不会占用其他元素的位置，每个链表中的元素都是哈希冲突的元素

插入：当我们插入时，计算出哈希地址，就可以直接定位到该key对应的链表的头结点，但是由于不能存放相同的key，我们需要遍历该链表中是否存在相同元素，如果不存在才进行插入。插入时我们可以进行头插或者尾插，这里头插会更简单些，创建key的一个新的结点cur，让该结点指向该链表的头结点，并将该链表的头结点更新为新创建的新结点cur
在这里插入图片描述增容：开散列的增容并不像闭散列一样要求那么严格，虽然也是有个负载因子，但是这个负载因子可以为1，也就是当有10个元素，负载因子为1时。此时10个元素都没有产生哈希冲突，这效率才是最高的，所以我们没必要限制它的上限。也就是当元素比哈希表的元素大时才需要进行扩容，来减少产生哈希冲突。哈希表中每个元素都是一个链表的头结点，我们可以创建新的一个指针数组，遍历旧的哈希表，只要遍历的链表头结点不为空，就定义一个cur，用来遍历这个单链表，遍历单链表的也需要记录该当前节点的下一个结点，否则会下一个结点会被丢弃。我们在当前节点cur中计算它的哈希地址，然后在新的指针数组中的指定位置进行头插。每遍历完一个单链表，都需要将旧的链表的头结点置为空，因为后面我们需要交换这两个指针数组，然后释放掉旧的指针数组。
在这里插入图片描述
查找：查找一个元素，我们可以先计算出要查找元素的哈希地址，直接定位到指定的链表的头结点，然后遍历该条链表，如果当前节点的值和要查找的元素的值相同，则表示查找，返回所找到的结点，如果没有找到则返回空
删除：这里的删除是实际上的删除，我们可以先通过查找，查看要删除的值是否存在哈希表中，如果不存直接返回false，存在则需要先计算当前删除的结点的所在链表的哈希地址，找到后遍历该链表，并用一个prev结点记录要删除的前一个结点，当遍历找到我们删除的结点时，要先判断该节点是否为链表的头结点，如果为头结点，则将要删除的结点的下一个结点置为头结点，如果不是头结点则将记录的前结点prev的下一个结点的next置为要删除结点的下一个结点。最后将有效元素-1并删除要删除的结点
在这里插入图片描述

2.2.2 开放寻址法

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

开放寻址法主要处理方法有 线性探测 和 二次探测，下面分别介绍

线性探测

线性探测思想：从计算的哈希位置开始，往后找到第一个空闲的位置存放数据
在这里插入图片描述插入：插入就是计算哈希地址，将数据存放在计算出来的哈希位置上，如果该位置有数据则往后查找第一个空闲位置插入。但是当我们的元素越多时，我们产生的哈希冲突的次数就会越多，

删除：当我们要删除一个元素时，不能物理上直接删除，例如我们把15删除了，此时下标为8的位置为空，当我们要查找25这个元素时，也是会从下标为5这个位置开始查找，当5这个位置不是25时，说明产生了哈希冲突，且该插入是使用的是线性探测，也就是第一个空位置插入。我们往后查找时，如果该数据存在，则在空位置之前一定存在该数。但是此时我们物理上把15删除了。查找会查找到下标为8的位置就结束查找，此时也就不会找到25这个数据了。
在这里插入图片描述所以使用线性探测方法，删除并不是实际意义上的删除，而是一种伪删除，我们可以定义三种状态，分别是：EMPTY、EXIST、DELETE。EMPTY表示该位置从来没存放过数据，是一个空位置；EXIST表示该位置存在数据；DELETE表示该位置之前存放过数据，只是已经删除了而已

此时我们想要删除8这个位置上的数据时，就将该位置的状态置为DELETE，我们再次查找25这个数字时，遇到8位置就不会停止搜索，会继续往后搜索，直至遇到状态为EMPTY的位置为止。但是次方法会造成一个问题，就是有可能数据满了，如果此时还一直搜索，就不会找到空的位置，会一直搜索下去。而且如果数据比较极端且数据越来越多，产生的哈希冲突会越来越多。这就不符合我们的哈希要求的高效率的插入与查找。解决办法就是进行扩容

扩容：扩容并不是一定要等到数据满了才扩容。我们知道当数据越来越多，产生哈希冲突的次数就越多，所以我们要设定一个阈值，也就是当数据达到一定的数量时，就有必要进行扩容。而这决定这个阈值的高低的是一个叫负载因子。负载因子 = 实际存放元素 / 数组容量，范围在0~1之间，我们通常将负载因子置为[0.6, 0.8]之间。例如我们数组大小有10个，负载因为为0.7，则当插入第8个元素的时候就需要进行扩容，因为8/10=0.8>.07，也就是大于我们的负载因子就需要进行扩容。扩容的时候要注意，我们需要将原来的数据移动到新的表中，但是如果是单纯的赋值获取，那哈希冲突并没有解决，而此时我们应该将旧表中的数据重新以插入的方式插入到新的表中，从而减少哈希冲突的次数
在这里插入图片描述
查找：哈希的优势之一也就是在于查找，查找的效率是非常高，只要通过key来计算哈希地址，如果计算的哈希位置的值与要查找的key相同，则表示已经找到，如果遇到空之后还没找到表示不存在这个要查找的数。并且要注意的是，如果查找到末尾就需要将查找的索引置为0，从头开始查找

二次探测

二次探测和线性探测都属于闭散列，其原理都一样，两者的主要区别就是探测的方式不同，线性探测是如果要插入的位置已有元素，会一个一个往后查找到新的空位置。而二次探测是通过该位置的哈希冲突次数的平方来向后查找新的位置
在这里插入图片描述

将产生哈希冲突的数据分散，使不堆积在一起。但是这两种方法都有很大的缺陷，就是空间利用率低。在这个基础上，所以实际开发中更推荐使用链地址法。

3 开放寻址法和链地址法代码实现

3.1 开放地址寻址法代码实现

#include <iostream>
#include <string>
#include <vector>

using namespace std;

enum State
{
    EMPTY,	//空标记
    EXIST,	//存在
    DELETE	//删除
};

template<class K, class V>
struct HashDate
{
    pair<K, V> _kv;
    State _state = EMPTY;

};

template<class k>
struct HashFunc
{
    size_t operator()(const k& key)
    {
        return (size_t)key;
    }
};

//特化--string
template<>
struct HashFunc<string>
{
    size_t operator()(const string& s)
    {
        size_t val = 0;
        for (const auto ch : s)	//迭代器
        {
            val *= 131;
            val += ch;
        }

        return val;
    }
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
    bool Insert(const pair<K, V>& kv)
    {
        if (Find(kv.first))
        {
            return false;
        }

        //负载因子到了就扩容
        if (_tables.size() == 0 || 10 * _size / _tables.size() >= 7)  //扩容
        {
            size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
            HashTable<K, V, Hash> newHT;
            newHT._tables.resize(newSize);
            //旧表数据映射到新表内
            for (auto e : _tables)
            {
                if (e._state == EXIST)
                {
                    newHT.Insert(e._kv);
                }
            }

            _tables.swap(newHT._tables);
        }

        Hash hash;
        size_t hashi = hash(kv.first) % _tables.size();
        //线性探测
        while (_tables[hashi]._state == EXIST)
        {
            ++hashi;
            hashi %= _tables.size();
        }

        //找到位置了
        _tables[hashi]._kv = kv;
        _tables[hashi]._state = EXIST;
        ++_size;

        return true;
    }

    // 查找
    HashDate<K, V>* Find(const K& key)
    {
        if (Empty())
        {
            return nullptr;
        }

        Hash hash;
        size_t hashi = hash(key) % _tables.size();
        while (_tables[hashi]._state != EMPTY)
        {
            if (_tables[hashi]._state != DELETE && key == _tables[hashi]._kv.first)
            {
                return  &_tables[hashi];
            }
            ++hashi;
            hashi %= _tables.size();
        }

        //没找到
        return nullptr;
    }

    // 删除
    bool Erase(const K& key)
    {
        HashDate<K, V>* ret = Find(key);
        if (ret)
        {
            ret->_state = DELETE;
            --_size;
            return true;
        }
        else
        {
            return false;
        }

    }

    bool Empty() const
    {
        return _size == 0;
    }

    size_t Size()const
    {
        return _size;
    }

    //打印一下，用来测试
    void Print()
    {
        for (size_t i = 0; i < _tables.size(); ++i)
        {
            if (_tables[i]._state == EXIST)
            {
                printf("[%d:%d] ", i, _tables[i]._kv.first);
            }
            else
            {
                printf("[%d:*] ", i);
            }
        }
        cout << endl;
    }

private:
    vector<HashDate<K, V>> _tables;
    size_t _size = 0;	//存储多少个有效数据
};


void TestHT1()
{
    //int a[] = { 1, 11, 4, 15, 26, 7, 44, 9 };
    int a[] = { 1, 11, 4, 15, 26, 7, 44 };
    HashTable<int, int> ht;
    for (auto e : a)
    {
        ht.Insert(make_pair(e, e));
    }

    ht.Print();

    ht.Erase(4);
    cout << ht.Find(44)->_kv.first << endl;
    cout << ht.Find(4) << endl;
    ht.Print();

    ht.Insert(make_pair(-2, -2));
    ht.Print();

    cout << ht.Find(-2)->_kv.first << endl;
}

void TestHT2()
{
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

    //HashTable<string, int, HashFuncString> countHT;
    HashTable<string, int> countHT;
    for (auto& str : arr)
    {
        auto ptr = countHT.Find(str);
        if (ptr)
        {
            ptr->_kv.second++;
        }
        else
        {
            countHT.Insert(make_pair(str, 1));
        }
    }

    for (auto& str : arr)
    {
        cout << str << ":" << countHT.Find(str)->_kv.second << "---";
    }
    cout << endl;
}

void TestHT3()
{
    HashFunc<string> hash;
    cout << hash("abcd") << endl;
    cout << hash("bcad") << endl;
    cout << hash("eat") << endl;
    cout << hash("ate") << endl;
    cout << hash("abcd") << endl;
    cout << hash("aadd") << endl << endl;

    cout << hash("abcd") << endl;
    cout << hash("bcad") << endl;
    cout << hash("eat") << endl;
    cout << hash("ate") << endl;
    cout << hash("abcd") << endl;
    cout << hash("aadd") << endl << endl;
}

int main()
{
    TestHT1();
    // TestHT2();
    // TestHT3();
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242

另一个版本的实现

//定义仿函数
template<class K>
struct _HashFunc
{
   
    size_t operator()(const K& key)
    {
   
        return key;
    }
};

//特化string的版本
template<>
struct _HashFunc<string>
{
   
    static size_t BKDRHash(const char* str)
    {
   
        size_t seed = 131;    // 31 131 1313 13131 131313
        size_t hash = 0;
        while (*str)
        {
   
            hash = hash*seed + (*str++);
        }
        return (hash & 0x7fffffff);
    }
    size_t operator()(const string& key)
    {
   
        return BKDRHash(key.c_str());    //c_str()返回的是一个const char*  类型的字符串
    }
};

enum Status
{
   
    EXIST
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/运维做开发/article/detail/981051
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号