【数据结构】万字一文手把手解读哈希————（开/闭散列）解决哈希冲突完整详解（6）-阿里云开发者社区

一.哈希（散列）的基本概念

1.哈希（散列）的基本概念

理想的搜索方法：不经过任何比较，一次直接从表中得到要搜索的元素。

如果构造一种存储结构， 通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系 ，那么在查找时通过该函数可以很快找到该元素

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

2.哈希表的简单基本例子

例如：数据集合{1，7，6，4，5，9}；哈希函数设置为：hash(key) = key % capacity;

capacity为存储元素底层空间总的大小

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

但是 当插入44时 ，就会出现问题： 不同值映射到相同位置 ，这就是第二部分要讲的" 哈希冲突问题 "

二.哈希冲突(哈希碰撞)

一句话理解哈希冲突: 不同值映射到相同位置

官方解释：对于两个数据元素的关键字k i k_iki和 k j k_jkj(i != j)，有k i k_iki != k j k_jkj，但有：Hash(k i k_iki) == Hash(k j k_jkj)，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

引起哈希冲突的一个原因可能是： 哈希函数设计不够合理 。这就是第二部分要讲的"哈希函数"

三.哈希函数

我们先要确定一点：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是 无法避免哈希冲突

1.哈希函数设计原则

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

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

哈希函数应该比较简单

2.常用的两种哈希函数

【1】直接定址法–(常用)

取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B

优点：简单、均匀

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

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

【2】除留余数法–(常用)

设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，

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

【※】哈希表中的荷载因子

四.解决哈希冲突法一：闭散列-“开放地址法”

一句话理解闭散列： 当前位置被占用了，按规则找到下一个位置（占用别人应该在的位置）

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

那如何寻找下一个空位置呢？—— 线性探测+二次探测

1. 线性探测＆二次探测

一句话理解 线性探测： 从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止 ,示例如下所示：

线性探测缺点： 一旦发生 哈希冲突 ，所有的冲突连在一起，容易产生 数据“堆积”

即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降
低。如何缓解呢？

二次探测 是为了避免该问题而生；找下一个空位置的方法为：H i H_iHi = (H 0 H_0H0 + i 2 i^2i2 )% m, 或者：H i H_iHi = (H 0 H_0H0 - i 2 i^2i2 )% m。其中： i = 1,2,3…， H 0 H_0H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。示例如下所示：

2.闭散列哈希中的基本状态

每一个元素格子可以分成三种状态：

EXIST（存在）

EMPTY（空）

DELETE（已被删除）

enum STATE
  {
    EXIST,
    EMPTY,
    DELETE
  };

3.闭散列哈希的基本结构

template<class K, class V>
  struct HashData
  {
    pair<K, V> _kv;
    STATE _state = EMPTY;
  };
   vector<HashData<K, V>> _table;
   size_t _n = 0; // 存储有效数据的个数————可用于识别荷载因子

4.线性探测中处理"查找"

代码如下所示：

HashData<const K, V>* Find(const K& key)
    {
      // 线性探测
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      while (_table[hashi]._state != EMPTY)
      {
        if (_table[hashi]._state == EXIST
          && _table[hashi]._kv.first == key)
        {
          return (HashData<const K, V>*) & _table[hashi];
        }
        ++hashi;
        hashi %= _table.size();
      }

5.线性探测中处理"插入"

【1】注意闭散列扩容问题

插入过程基本程序设计思路：

当荷载因子达到某个临界值_n * 10 / _table.size() >= 7，进入扩容

扩容过程： 1.设置新表大小 2.创建新表 3.遍历旧表的数据插入到新表即可 4.交换新表旧表首元素地址

正常插入过程遵循线性探测：
1.通过哈希函数找到相应映射的下表（hashi）
2.但遇到当前hashi已经被占据时_table[hashi]._state == EXIST，
进行 二次探测 hashi %= _table.size();重新寻找新hashi
3.找到状态为EMPTY的hashi时，存入数据，调整状态
_table[hashi]._kv = kv; _table[hashi]._state = EXIST; ++_n;

bool Insert(const pair<K, V>& kv)
    {
      if (Find(kv.first))
      {
        return false;
      }
      // 扩容
      //if ((double)_n / (double)_table.size() >= 0.7)
      if (_n * 10 / _table.size() >= 7) //荷载因子
      {
        size_t newSize = _table.size() * 2;
        // 遍历旧表，重新映射到新表
        HashTable<K, V, HashFunc> newHT;
        newHT._table.resize(newSize);
        // 遍历旧表的数据插入到新表即可
        for (size_t i = 0; i < _table.size(); i++)
        {
          if (_table[i]._state == EXIST)
          {
            newHT.Insert(_table[i]._kv);
          }
        }
        _table.swap(newHT._table);
      }
      // 线性探测
      HashFunc hf;
      size_t hashi = hf(kv.first) % _table.size();
      while (_table[hashi]._state == EXIST)
      {
        ++hashi;
        hashi %= _table.size();
      }
      _table[hashi]._kv = kv;
      _table[hashi]._state = EXIST;
      ++_n;
      return true;
    }

6.线性探测中处理"删除"

删除过程基本程序设计思路：

利用查找函数find接收返回值

将该hashi下表对应的状态设置成DELETE即可

// 按需编译
    bool Erase(const K& key)
    {
      HashData<const K, V>* ret = Find(key);
      if (ret)
      {
        ret->_state = DELETE;
        --_n;
        return true;
      }
      return false;
    }

7. 闭散列适应多种类型转换————“仿函数”＆“类模板特化”&“仿函数在类模板中充当默认模板实参的应用”

【1】仿函数

一句话解释 仿函数 ：用一个类重载（），让其实现函数的功能

仿函数在类模板中的应用传送门：传送门

使用仿函数的基本操作：重载（）——operator()

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

【2】类模板特化

使用仿函数的进阶操作：让闭散列适应多种类型转换

场景举例：正常情况下，我们输入int double，他都会通过仿函数重载的（）转换成对应的ASCLL码值，但是当传入的是字符串则会出现问题，因此我们需要把类模板 特化一下————struct DefaultHashFunc<string>

特化在类模板中的应用传送门：传送门

template<>
struct DefaultHashFunc<string>
{
  size_t operator()(const string& str)
  {
    // BKDR
    size_t hash = 0;
    for (auto ch : str)
    {
      hash *= 131;
      hash += ch;
    }
    return hash;
  }
};

【3】仿函数在类模板中充当默认实参的应用

仿函数在类模板中充当默认模板实参传送门：传送门

template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  class HashTable
  {
  //调用时
  HashFunc hf;
  size_t hashi = hf(kv.first) % _table.size();
  ...};

8.闭散列哈希完整代码展示

template<class K>
struct DefaultHashFunc
{
  size_t operator()(const K& key)
  {
    return (size_t)key;
  }
};
template<>
struct DefaultHashFunc<string>
{
  size_t operator()(const string& str)
  {
    // BKDR
    size_t hash = 0;
    for (auto ch : str)
    {
      hash *= 131;
      hash += ch;
    }
    return hash;
  }
};
namespace open_address
{
  enum STATE
  {
    EXIST,
    EMPTY,
    DELETE
  };
  template<class K, class V>
  struct HashData
  {
    pair<K, V> _kv;
    STATE _state = EMPTY;
  };
  template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  class HashTable
  {
  public:
    HashTable()
    {
      _table.resize(10);
    }
    bool Insert(const pair<K, V>& kv)
    {
      if (Find(kv.first))
      {
        return false;
      }
      // 扩容
      //if ((double)_n / (double)_table.size() >= 0.7)
      if (_n * 10 / _table.size() >= 7)
      {
        size_t newSize = _table.size() * 2;
        // 遍历旧表，重新映射到新表
        HashTable<K, V, HashFunc> newHT;
        newHT._table.resize(newSize);
        // 遍历旧表的数据插入到新表即可
        for (size_t i = 0; i < _table.size(); i++)
        {
          if (_table[i]._state == EXIST)
          {
            newHT.Insert(_table[i]._kv);
          }
        }
        _table.swap(newHT._table);
      }
      // 线性探测
      HashFunc hf;
      size_t hashi = hf(kv.first) % _table.size();
      while (_table[hashi]._state == EXIST)
      {
        ++hashi;
        hashi %= _table.size();
      }
      _table[hashi]._kv = kv;
      _table[hashi]._state = EXIST;
      ++_n;
      return true;
    }
    HashData<const K, V>* Find(const K& key)
    {
      // 线性探测
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      while (_table[hashi]._state != EMPTY)
      {
        if (_table[hashi]._state == EXIST
          && _table[hashi]._kv.first == key)
        {
          return (HashData<const K, V>*) & _table[hashi];
        }
        ++hashi;
        hashi %= _table.size();
      }
      return nullptr;
    }
    // 按需编译
    bool Erase(const K& key)
    {
      HashData<const K, V>* ret = Find(key);
      if (ret)
      {
        ret->_state = DELETE;
        --_n;
        return true;
      }
      return false;
    }
  private:
    vector<HashData<K, V>> _table;
    size_t _n = 0; // 存储有效数据的个数
  };
}

9.闭散列缺点

发生哈希冲突后，几个位置映射的值会 相互影响

五.解决哈希冲突法二：开散列-“链地址法(开链法)”-“哈希桶”

1. 开散列概念

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

开散列中每个桶中放的都是发生 哈希冲突 的元素。

2.开散列哈希基本形式

//哈希桶
namespace hash_bucket
{
HashTable...//哈希表
HashNode...//节点
vector<Node*> _table; // 指针数组
size_t _n = 0; // 存储了多少个有效数据
}
//哈希表
template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  class HashTable
  {
  typedef HashNode<K, V> Node;
  ....};
//节点
template<class K, class V>
  struct HashNode
  {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv)
      :_kv(kv)
      ,_next(nullptr)
    {}
  };

3.开散列插入

【1】哈希桶基本插入问题

采取 头插方式

// 头插
  Node* newnode = new Node(kv);
  newnode->_next = _table[hashi];
  _table[hashi] = newnode;

【2】注意闭散列扩容问题

引入：

如果不扩容，不断插入某些桶越来越长效率得不到保障，负载因子适当放大一些，一般负载因子控制在1，平均下来就是每一个桶一个数据

// 负载因子到1就扩容
if (_n == _table.size())
{
  size_t newSize = _table.size()*2;
  vector<Node*> newTable;
  newTable.resize(newSize, nullptr);
  if(...)//剩余操作
}

【3】注意闭散列扩容后的操作

注意：这里我们采用 遍历旧表，顺手牵羊，把节点牵下来挂到新表的方式

原因：重新开空间开节点，消耗大，效率低

// 遍历旧表，顺手牵羊，把节点牵下来挂到新表
for (size_t i = 0; i < _table.size(); i++)
{
  Node* cur = _table[i];//旧表
  while (cur)
  {
      Node* next = cur->_next;//保存下一个地址
        //找到新的对应位置
      size_t hashi = hf(cur->_kv.first) % newSize; //hf为仿函数，在开散列相关章可以查看
       //头插到新表
    cur->_next = newTable[hashi];
    newTable[hashi] = cur;
    cur = next;
  }
   //把旧表置空
  _table[i] = nullptr;
}
//最后交换新旧表首元素地址
_table.swap(newTable);

【4】闭散列完整插入操作

bool Insert(const pair<K, V>& kv)
    {
      if(Find(kv.first))
      {
        return false;
      }
      HashFunc hf;
      // 负载因子到1就扩容
      if (_n == _table.size())
      {
        size_t newSize = _table.size()*2;
        vector<Node*> newTable;
        newTable.resize(newSize, nullptr);
        // 遍历旧表，顺手牵羊，把节点牵下来挂到新表
        for (size_t i = 0; i < _table.size(); i++)
        {
          Node* cur = _table[i];
          while (cur)
          {
            Node* next = cur->_next;
            // 头插到新表
            size_t hashi = hf(cur->_kv.first) % newSize;
            cur->_next = newTable[hashi];
            newTable[hashi] = cur;
            cur = next;
          }
          _table[i] = nullptr;
        }
        _table.swap(newTable);
      }
      size_t hashi = hf(kv.first) % _table.size();
      // 头插
      Node* newnode = new Node(kv);
      newnode->_next = _table[hashi];
      _table[hashi] = newnode;
      ++_n;
      return true;
    }

4. 开散列查找操作

Node* Find(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      Node* cur = _table[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          return cur;
        }
        cur = cur->_next;
      }
      return nullptr;
    }

5. 开散列哈希完整代码展示

namespace hash_bucket
{
  template<class K, class V>
  struct HashNode
  {
    pair<K, V> _kv;
    HashNode<K, V>* _next;
    HashNode(const pair<K, V>& kv)
      :_kv(kv)
      ,_next(nullptr)
    {}
  };
  template<class K, class V, class HashFunc = DefaultHashFunc<K>>
  class HashTable
  {
    typedef HashNode<K, V> Node;
  public:
    HashTable()
    {
      _table.resize(10, nullptr);
    }
    ~HashTable()
    {
      for (size_t i = 0; i < _table.size(); i++)
      {
        Node* cur = _table[i];
        while (cur)
        {
          Node* next = cur->_next;
          delete cur;
          cur = next;
        }
        _table[i] = nullptr;
      }
    }
    bool Insert(const pair<K, V>& kv)
    {
      if(Find(kv.first))
      {
        return false;
      }
      HashFunc hf;
      // 负载因子到1就扩容
      if (_n == _table.size())
      {
        size_t newSize = _table.size()*2;
        vector<Node*> newTable;
        newTable.resize(newSize, nullptr);
        // 遍历旧表，顺手牵羊，把节点牵下来挂到新表
        for (size_t i = 0; i < _table.size(); i++)
        {
          Node* cur = _table[i];
          while (cur)
          {
            Node* next = cur->_next;
            // 头插到新表
            size_t hashi = hf(cur->_kv.first) % newSize;
            cur->_next = newTable[hashi];
            newTable[hashi] = cur;
            cur = next;
          }
          _table[i] = nullptr;
        }
        _table.swap(newTable);
      }
      size_t hashi = hf(kv.first) % _table.size();
      // 头插
      Node* newnode = new Node(kv);
      newnode->_next = _table[hashi];
      _table[hashi] = newnode;
      ++_n;
      return true;
    }
    Node* Find(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      Node* cur = _table[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          return cur;
        }
        cur = cur->_next;
      }
      return nullptr;
    }
    bool Erase(const K& key)
    {
      HashFunc hf;
      size_t hashi = hf(key) % _table.size();
      Node* prev = nullptr;
      Node* cur = _table[hashi];
      while (cur)
      {
        if (cur->_kv.first == key)
        {
          if (prev == nullptr)
          {
            _table[hashi] = cur->_next;
          }
          else
          {
            prev->_next = cur->_next;
          }
          delete cur; 
          return true;
        }
        prev = cur;
        cur = cur->_next;
      }
      return false;
    }
    void Print()
    {
      for (size_t i = 0; i < _table.size(); i++)
      {
        printf("[%d]->", i);
        Node* cur = _table[i];
        while (cur)
        {
          cout << cur->_kv.first <<":"<< cur->_kv.second<< "->";
          cur = cur->_next;
        }
        printf("NULL\n");
      }
      cout << endl;
    }
  private:
    vector<Node*> _table; // 指针数组
    size_t _n = 0; // 存储了多少个有效数据
  };
}

六.哈希表的使用

#include"HashTable.h"
int main()
{
  HashTable<int, int> ht;
  int a[] = { 1,111,4,7,15,25,44,9 };
  for (auto e : a)
  {
    ht.Insert(make_pair(e, e));
  }
  ht.Erase(15);
  auto ret = ht.Find(4);
  //ret->_kv.first = 41;
  ret->_kv.second = 400;
  //HashTable<string, string, StringHashFunc> dict;
  HashTable<string, string> dict;
  dict.Insert(make_pair("sort", "排序"));
  dict.Insert(make_pair("left", "xxx"));
  auto dret = dict.Find("left");
  //dret->_kv.first = "xx";//不可修改，const
  dret->_kv.second = "左边";
  string s1("xxx");
  string s2("xxx");
  DefaultHashFunc<string> hf;
  cout << hf(s1) << endl;
  cout << hf(s2) << endl;
  cout << hf("bacd") << endl;
  cout << hf("abcd") << endl;
  cout << hf("abbe") << endl;
  cout << hf("https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=STATE&fenlei=256&rsv_pq=0xdd48647300054f47&rsv_t=1cd5rO%2BE6TJzo6qf9QKcibznhQ9J3lFwGEzmkc0Goazr3HuQSIIc2zD78Pt0&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=2&rsv_n=2&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=STAT%2526gt%253B&rsp=5&inputT=656&rsv_sug4=796") << endl;
  return 0;
}

【数据结构】万字一文手把手解读哈希————（开/闭散列）解决哈希冲突完整详解（6）

一.哈希（散列）的基本概念

1.哈希（散列）的基本概念

2.哈希表的简单基本例子

二.哈希冲突(哈希碰撞)

三.哈希函数

1.哈希函数设计原则

2.常用的两种哈希函数

【1】直接定址法–(常用)

【2】除留余数法–(常用)

【※】哈希表中的荷载因子

四.解决哈希冲突法一：闭散列-“开放地址法”

1. 线性探测＆二次探测

2.闭散列哈希中的基本状态

3.闭散列哈希的基本结构

4.线性探测中处理"查找"

5.线性探测中处理"插入"

【1】注意闭散列扩容问题

6.线性探测中处理"删除"

7. 闭散列适应多种类型转换————“仿函数”＆“类模板特化”&“仿函数在类模板中充当默认模板实参的应用”

【1】仿函数

【2】类模板特化

【3】仿函数在类模板中充当默认实参的应用

8.闭散列哈希完整代码展示

9.闭散列缺点

五.解决哈希冲突法二：开散列-“链地址法(开链法)”-“哈希桶”

1. 开散列概念

2.开散列哈希基本形式

3.开散列插入

【1】哈希桶基本插入问题

【2】注意闭散列扩容问题

【3】注意闭散列扩容后的操作

【4】闭散列完整插入操作

4. 开散列查找操作

5. 开散列哈希完整代码展示

六.哈希表的使用

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【数据结构】万字一文手把手解读哈希————（开/闭散列）解决哈希冲突完整详解（6）

一.哈希（散列）的基本概念

1.哈希（散列）的基本概念

2.哈希表的简单基本例子

二.哈希冲突(哈希碰撞)

三.哈希函数

1.哈希函数设计原则

2.常用的两种哈希函数

【1】 直接定址法–(常用)

【2】除留余数法–(常用)

【※】哈希表中的荷载因子

四.解决哈希冲突法一：闭散列-“开放地址法”

1. 线性探测＆二次探测

2.闭散列哈希中的基本状态

3.闭散列哈希的基本结构

4.线性探测中处理"查找"

5.线性探测中处理"插入"

【1】注意闭散列扩容问题

6.线性探测中处理"删除"

7. 闭散列适应多种类型转换————“仿函数”＆“类模板特化”&“仿函数在类模板中充当默认模板实参的应用”

【1】仿函数

【2】类模板特化

【3】仿函数在类模板中充当默认实参的应用

8.闭散列哈希完整代码展示

9.闭散列缺点

五.解决哈希冲突法二：开散列-“链地址法(开链法)”-“哈希桶”

1. 开散列概念

2.开散列哈希基本形式

3.开散列插入

【1】哈希桶基本插入问题

【2】注意闭散列扩容问题

【3】注意闭散列扩容后的操作

【4】闭散列完整插入操作

4. 开散列查找操作

5. 开散列哈希完整代码展示

六.哈希表的使用

热门文章

最新文章

相关课程

相关电子书

【1】直接定址法–(常用)