• 【数据结构】哈希表（详）

    文章目录

    前言

     在之前，博主简要提了一下C语言的哈希原理与哈希表的接口，总结成了一篇文章：哈希表——C语言，今天就让我们彻底迈向哈希的大门！

    正文

    一、基本概念

     就目前博主学过的知识来看，哈希表是查找数据最快的一种数据结构，查找的时间复杂度为O(1)。

    • 它是如何做到的 ？

     首先在学习数组时，我们知道——通过指定下标访问数据的时间复杂度也为O(1), 既然下标+数组 == O(1)，那么哈希是不就是数组呢？

     答案是——Yes，不过赋予了下标索引更加具体的含义。

     比如说: 字符串通过处理转换成下标，用字符串查找，其实本质上还是用下标进行查找，但是丰富了下标的含义，那原来存数据的位置，就可以赋予比较常用的数据存在/次数之类的。

    关键码：索引值，比如字符串之类的数据，内部是对关键码进行处理再进行查找的。

     既然是这样，那是如何赋予下标具体的含义呢？

    二、基本原理

    1.哈希函数

    在这里插入图片描述
     看上面这一张图，或许就明白哈希函数是一种映射关系，就将关键码转换为下标的函数，看图可知，映射出来的值很有可能就不是连续的，这或许就是散列的由来。

     再来讨论这样一个问题，关键码映射出来的下标与关键码是一 一对应的关系吗？很遗憾不一定是，不是的现象我们称之为冲突。冲突是无法避免的，只能尽可能的减少，一种减少的方式就是取合适的哈希函数。

    那如何设计或者取到合适的哈希函数呢？

    设计与选择哈希函数的原则：

    1. 关键码通过哈希函数映射出来的必须在表的范围里（合法性）。
    2. 数据在表中应该较为分散（尽量减少冲突）
    3. 函数应该较为简单（可读，易理解）

    下面我们来介绍几种常见的哈希函数，便于使用。

    1.1直接定址法（常用）

     直接通过关键码进行映射，一般是取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B。

     优点是比较简单，但是这样设计的原则的缺点在于得事先知道关键码的分布，由此设计合适的哈希函数。

    举例： 博主在做哈希与字符串部分的题目，变位词这个概念经常考察，常常给出字母的范围为小写字母，这样我们就知道设计成这样：Hash（Key）= Key - ‘a’ ,数组只需要开辟26个类型的空间即可，至于索引得到的是什么，则要看题目的变化。

    1.2除留余数法（常用）

     就是哈希表最多能存多少个数，这里姑且设为m，再取一个质数（素数）设为 x(小于等于m)，设置为除数，由此设计的哈希函数为：Hash（Key）= Key % x。

     %可以将任意的未知的key，转换为[0,x-1]的数，就不会超出哈希表的范围，但是在计算机里面只能用作整数之间的运算，其它类型均不可取，这就又要另谋出路了。并且不同语言的设计%的方式不一样，因此不同平台的同一份数据的哈希表可能不会相同。

     接下来我们解决一下字符串的处理方式。一般采用131质数取其中的字母进行映射：

    	size_t key = 0;
	string str = "hello";
	for(auto e : str)
	{
		key += e;
		key *= 131;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    这有点玄学,至于为什么用131，这主要是有人取出一大堆数进行测试得到结论，这个数冲突会比较少。

    • 细节1：在key求和过程中，我们一般记时间复杂度为O(1)，因为在现实世界中，一组确定的字符串，其长度必然是常数，只是如果字符串过长有一点点的消耗罢了。
    • 细节2: 在key求和过程中，可能会发生溢出现象，这就是我们采用无符号整形的意义，自动处理溢出。

    总结一下：

    • 优点：不看数据范围，可直接映射到哈希表的合法区间。
    • 缺点：不看数据的分布，冲突的产生可能会比较严重，冲突过多，效率越低。

    说明： 等会儿我们实现哈希表时，用的就是这种方法。

    1.3 平方取中法（了解）

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

     再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址

     设计原因：因为key的有位数存在不同，而中间几位的结果取决于key的每一位，因此起到了减少冲突的效果。

     哈希函数：Hash（Key）= Key2 % 中间几位。中间几位是动态变化的，取决于哈希表的能存的最大容量的位数。

    • 适合：不知道关键字的分布，而位数又不是很大的情况，位数不能很大的原因在于溢出之后key的位数与最终结果的关联度降低了，可能会提高冲突的个数。
    1.4 折叠法(了解)

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

     设计原因：跟平方取中法雷同，最后和的结果与key的每一位都存在关系，从而减少冲突。

    • 哈希函数: Hash（Key）= 分割位数求和。 这个分割数的位数取决于哈希表的最大容量。

    • 适合事先不需要知道关键字的分布，适合关键字位数比较多的情况，因为是将大数拆成几部分取和，所以会比较小。

    1.5 随机数法(了解)

     选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。

     设计原因：随机数每次相同的概率很低，因此采用随机数，同时为了保证相同key映射出的随机函数的值是相同的。这里映射的随机数也要保存起来，因此random函数是一个伪随机函数。

    • 哈希函数: H(key) = random(key)

    • 通常应用于关键字长度不等时采用此法

    1.6数学分析法(了解)

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

     简单来讲，就是观察数据删除大致相同的部分，用基本不同的部分进行再设计求哈希函数。

     下面的电话号码就是一个很好的例子：
    在这里插入图片描述
     将后几位抽离出来，再使用之前的方法比如平方取中/随机数，这样再次处理，能够在一定程度上减少冲突。

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

    总结：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

    2.哈希冲突

    2.1 平均查找长度

     平均查找长度与冲突有着直接关系，即冲突越多，平均查找长度越长, 求平均查找长度的公式为：len = 查找每个元素的比较次数 / 元素的总个数。

    举个例就一目了然：

     已知有一个关键字序列：（19,14,23,1,68,20,84,27,55,11,10,79）散列存储在一个哈希表中，若散列函数为H（key）=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为()

    1. 第一步：先分类，求哈希值。

    在这里插入图片描述
    2. 第二步：画草图

    在这里插入图片描述

    1. 求比较总次数与数据个数，求结果。

    在这里插入图片描述

    2.2 负载因子

     负载（装载）因子是衡量哈希表中表被装满的程度，设表中存有的数据为x，设表中合法容量（size）为y，那么负载因子为：z = x / y, 负载因子越大，哈希表的填满的程度越大，即产生的冲突的可能性就越大，又因为要考虑空间利用率的情况，实验研究表明，设置负载因子最大不超过0.75比较合适，因此当x达到某一范围时，表就得扩容。

    2.3闭散列(开放定制法)

     简单理解就是，如果当前位置的存放有数据，产生冲突，就往哈希表的下一个位置去找，直到找到没有数据的位置为止，然后把数据放在这个位置里面。

    • 当然这个方法的前提是表永远存在着空位。
    2.1.1 线性探测

    最经典的方法，就是一步一步找坑位，如果为空，就放进去。

    这里就引用大佬2021dragon的文章的例子，一目了然。

     例如，我们用除留余数法将序列{1, 6, 10, 1000, 101, 18, 7, 40}插入到表长为10的哈希表中，当发生哈希冲突时我们采用闭散列的线性探测找到下一个空位置进行插入，插入过程如下：

    在这里插入图片描述

    最终结果：
    在这里插入图片描述

    说明一下：这里的哈希函数为： hash(key) = key % 10，当然这个10如果取成7（质数）会更好一点。

    继续讨论，当我们要进行查找1000时，要先计算hash值为0，从0下标开始找，然后比对数据，如果是就停止查找，如果不是继续查找，直到找到/找不到为止，整个查找过程为常数次。

    那当我们删除10时，1000还找的到吗？答案是可以的，因为我们并没有真的删除10，而是标记状态为删除（DELETE），那么没有数据的位置标记为空(EMPTY),存在数据的位置我们标记为存在(EXIST)。 也就是说，最开始整个表的数据都为EMPTY，插入数据为EXIST，删除数据为DELETE。从而更好的管理数据。

    问题是解决了，有没有什么缺陷呢？答案是有的，就是表的平均查找长度只会增不会减，因为删除位置也会被再次查找，所以这在一定程度上降低了效率。还有一个缺点就是冲突会聚集也就是会影响其它数据的查找。

    2.1.2 二次探测

     跟线性探测的思路大致相同。

    • 区别： 哈希函数的改变为: hash(key) = (key + i2) % m，这个m是小于等于哈希表容量的最大质数，i的范围为(1,2,3,4,5, ……)。

    但是这个也产生了聚集，只不过没有线性探测那么严重而已，因为步长会越来越大，而且我们通常也不常用二次探测，这个作为了解即可。

    2.1.3二重哈希

     规避了线性探测和二次探测的因为是每个数据探测的步长相等而导致的聚集问题，并在此基础上再设置了一个步长函数，使得每个数据的步长大概率不等，从而减少冲突。

    • 步长函数：stepSize = m - (key%m)，m是小于等于哈希表容量的最大质数,这是有实验得出的冲突概率比较小的函数。
    • 但是这会要求哈希表的容量为一个质数，举个例子，如果步长为5，初始位置为0，哈希表的容量为10，那么就会产生 0 5 0 5 的死循环，如果为质数那么总会溢出一个1，每次溢出的这个1就会与上一次循环产生一个错位，直到遍历完这个数据的每一个元素为止。

    那质数怎么取呢？如果在用的时候再求，是有点损耗效率的，于是库里就弄了一张表存放的是大致为2倍关系的质数，便于扩容的时候取。

    static const unsigned long __stl_prime_list[__stl_num_primes] =
{
  53,         97,         193,       389,       769,
  1543,       3079,       6151,      12289,     24593,
  49157,      98317,      196613,    393241,    786433,
  1572869,    3145739,    6291469,   12582917,  25165843,
  50331653,   100663319,  201326611, 402653189, 805306457, 
  1610612741, 3221225473, 4294967291
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

     如何取到扩容的相邻的质数呢？

    • 只需要遍历表中数据，得到第一个比扩容的容量大的数据即可。
    2.4 开散列

     简单理解是一种窝里斗的形式，不采用占别人的坑位，而是采用印度阿三的方式，如果冲突了，就站到你的上面。也就是下面所讲的一种拉链法。

    2.1.1 哈希链 / 哈希桶

     哈希链就是采用链表的形式，产生冲突之后，将数据挂起来。

    举个例子：

    • 设元素的关键码为(37, 25, 14, 36, 49, 68, 57, 11)
    • 表的大小为12
    • 哈希函数为Hash(x) = x % 11
      Hash(37)=4
      Hash(25)=3
      Hash(14)=3
      Hash(36)=3
      Hash(49)=5
      Hash(68)=2
      Hash(57)=2
      Hash(11)=0

    使用哈希函数计算出每个元素所在的桶号，同一个桶的链表中存放哈希冲突的元素。
    在这里插入图片描述

     除此之外，我们还要讨论冲突产生的聚集的问题，也就是一个链上的数据不能挂太多，很显然还得是用之前的负载因子，这里的负载因子控制在多少合适呢？一般来说取1比较合适，因为这样表示在理想状态下每个桶的数据为1，也就是说，查找的次数为1，当然在现实情况下，不会这么理想。

     在哈希链的基础上，我们再进行讨论，如果极端场景下，某一个桶的长度很大呢？这就要再采用某种方式进行优化，那比哈希表稍微次一点的查找结构是红黑树，如果我们桶的长度超出了某一个长度，我们就用红黑树这种结构，是不是更好？
    如图所示：
    在这里插入图片描述

    三、基本实现

    1.开散列实现（线性探测）

    1.1基本框架
    	//素数表
	static const unsigned long prime_list[28] =
    {
      53,         97,         193,       389,       769,
      1543,       3079,       6151,      12289,     24593,
      49157,      98317,      196613,    393241,    786433,
      1572869,    3145739,    6291469,   12582917,  25165843,
      50331653,   100663319,  201326611, 402653189, 805306457,
      1610612741, 3221225473, 4294967291
    };
    //获取下一个大于x的素数。
    size_t GetNextPrime(size_t x)
    {
        for (int i = 0; i < 28; i++)
        {
            if (x < prime_list[i])
            {
                return prime_list[i];
            }
        }
        return -1;
    }
	//线性探测，为了避免删除时下次的数据找不到，因此要标记状态值。
    enum STATE
    {
        EXIST = 0,
        EMPTY = 1,
        DELETE = 2
    };
    template<class K,class V>
    struct HashNode
    {
        HashNode(const pair<K,V>& val = pair<K,V>())
            :_data(val)
        {}
        pair<K,V> _data;
        STATE _state = EMPTY;
    };
    //对一般的key做处理，比如char，int，double等
    template<class K>
    struct HashFunc
    {
        K operator()(const K& val)
        {
            return (size_t)val;
        }
    };
    //对特殊的数据做处理，这里是对string，上面讲到过。
    template<>
    struct HashFunc<string>
    {
        size_t operator()(const string& val)
        {
            size_t x = 0;
            for (auto e : val)
            {
                x += e;
                x *= 131;
            }
            return x;
        }
    };
    template<class K, class V,class DefaultHashFunc = HashFunc<K>>
    class HashTable
    {
    public:
        HashTable(size_t n = 17)
        {
        	_table.resize(GetNextPrime(n));
        }
        typedef HashNode<K,V>  Node;
        Node* find(const K& key);
        bool insert(const pair<K, V>& key);
        bool erase(const K& key);
    private:
        vector<Node> _table;
        size_t _n = 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
    1.2 find
     Node* find(const K& key)
 {
     DefaultHashFunc handle_key;
     int innode = handle_key(key) % _table.size();
     while (_table[innode]._state != EMPTY)
     {
         if (_table[innode]._data.first == key)
         {
             return &_table[innode];
         }
         else
         {
             innode++;
             innode %= _table.size();
         }
     }
     return nullptr;
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    1.3 insert
      bool insert(const pair<K, V>& kv)
  {
      //对负载因子进行判断，看是否需要扩容。
      if ((double)_n  / (double)_table.size() >= 0.7)
      {
          //进行扩容，再进行移表
          int newsize = 2 * _table.size();
          HashTable<K, V> newtable(newsize);
          for (size_t i = 0; i < _table.size(); i++)
          {
              //只需要将存在的数据移去新表即可。
              if (_table[i]._state == EXIST)
              {
                  newtable.insert(_table[i]._data);
              }
          }
          //swap，交给析构函数即可。
          swap(newtable._table, _table);
      }

      DefaultHashFunc handle_key;
      int innode = handle_key(kv.first) % _table.size();

      while (_table[innode]._state != EMPTY)
      {
          if (_table[innode]._data.first == kv.first)
          //如果已经存在就无需插入，就返回false
          {
              return false;
          }
          else
          {
               innode++;
               innode %= _table.size();
          }
      }
      //找到空位置，进行插入即可
      _table[innode] = kv;
      _table[innode]._state = EXIST;
      _n++;
      return true;
  }

    • 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
    1.4 erase
     bool erase(const K& key)
 {
     DefaultHashFunc handle_key;
     int innode = handle_key(key) % _table.size();
     
     while (_table[innode]._state != EMPTY)
     {
         //如果数据存在并且key值相等，才进行删除。
         if (_table[innode]._state == EXIST
             && _table[innode]._data.first == key)
         {
             _table[innode]._state = DELETE;
             _n--;
             return true;
         }
         innode++;
         innode %= _table.size();
     }
     return false;
 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    2.闭散列实现（哈希桶）

    2.1基本框架
        template<class K,class V>
    struct HashNode
    {
        HashNode(const pair<K, V>& val = pair<K, V>())
            :_data(val)
        {}
        pair<K, V> _data;
        HashNode* _next = nullptr;
    };
     static const unsigned long prime_list[28] =
    {
      53,         97,         193,       389,       769,
      1543,       3079,       6151,      12289,     24593,
      49157,      98317,      196613,    393241,    786433,
      1572869,    3145739,    6291469,   12582917,  25165843,
      50331653,   100663319,  201326611, 402653189, 805306457,
      1610612741, 3221225473, 4294967291
    };//素数表
    size_t GetNextPrime(size_t x)
    {
        for (int i = 0; i < 28; i++)
        {
            if (x < prime_list[i])
            {
                return prime_list[i];
            }
        }
        return -1;
    }
    
    template<class K, class V,class KeyOfF = KeyOff<K>>
    class HashTable
    {
        typedef HashNode<K,V> Node;
    public:
        HashTable(size_t n = 17)
        {
             _table.resize(GetNextPrime(n));
        }
        bool insert(const pair<K, V>& key);
        bool erase(const K& key);
    private:
        vector<Node*> _table;
        size_t _n = 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
    2.2 find
      Node* find(const K& key)
  {
      int innode = handle_key(key) % _table.size();
      Node* head = _table[innode];
      while (head)
      {
          if (head->_data.first == kv.first)
          {
              return head;
          }
          head = head->_next;
      }
      return nullptr;
  }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    2.3 insert
    bool insert(const pair<K, V>& kv)
{
    if ((double)_n / (double)_table.size() >= 1.0)
    {
        //换新表
        size_t newsize = 2 * _table.size();
        HashTable<K, V> new_table(newsize);
        //只能移数据
        for (int i = 0; i < (int)_table.size(); i++)
        {
            Node* node = _table[i];
            int innode = i % newsize;
            while (node)
            {
                node->_next = new_table._table[innode];
                new_table._table[innode] = node;
                node = node->_next;
            }
        }
        //交换数据,因为只是移数据，所以没有必要进行销毁。
        _table.resize(0);//调整size为0，即可避免被销毁。
        swap(_table, new_table._table);
    }

    DefaultHashFunc handle_key;
    int innode = handle_key(kv.first) % _table.size();
    Node* head = _table[innode];
    while (head)
    {
        //如果结点已经存在就无需再进行插入。
        if (head->_data.first == kv.first)
        {
            return false;
        }
        head = head->_next;
    }
    Node* newnode = new(Node);
    newnode->_data = kv;
    //指向头结点，更新头结点。
    newnode->_next = _table[innode];
    _table[innode] = newnode;

    //更新有效数据
    _n++;
    return true;
}

    • 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
    2.4 erase
      bool erase(const K& key)
  {
      DefaultHashFunc handle_key;
      int innode = handle_key(key) % _table.size();
      Node* cur = _table[innode];
      Node* prev = nullptr;
      while (cur)
      {
          if (cur->_data.first == key)
          {
              if (prev == nullptr)
              {
                  _table[innode] = nullptr;
              }
              else
              {
                  prev->_next = cur->_next;
              }
              delete cur;
              --_n;
              return true;
          }
          cur = cur->_next;
      }
      return false;
  }

    • 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

    总结

     只要掌握了相关原理，代码是不难实现的，关于实现原理，博主基本上都已提及，如果有所帮助，不妨点个赞鼓励一下吧！

  • 相关阅读:
    智能高效的转运机器人，为物流行业注入新动力
    迈道科技生产安全风险调度管控系统
    【Go】fatal error: concurrent map writes 问题记录
    【细读经典】springBoot源码（一）创建SpringApplication
    ArcObjects SDK开发 012 PageLayout和Page
    算法通过村第十六关-滑动窗口|青铜笔记|滑动很简单
    特斯拉一面算法原题
    软件工程：帕金森定律，项目工期的那点事儿
    jquery列表顺序倒转排序效果
    不同单位之间的字节换算
  • 原文地址：https://blog.csdn.net/Shun_Hua/article/details/133046638