自学内容网 自学内容网

c++哈希(开散列原理及实现)

我把c++哈希表上篇讲解放在这了,建议大家先看这篇。

前言

在上篇文章中我们详细介绍了,哈希的思想及实现原理,也认识到了闭散列最大的缺陷就是空间利用率比较低,容易这也是哈希的缺陷。怎么来解决这个问题呢?下面我们就来学习一种新的方法————————开散列(链地址法)


一、开散列概念

在前面我们讲的开放定址法,是通过哈希函数将关键码与存储位置建立映射关系,从而将关键码,存储在哈希表中,而这种方式,在数据量大的情况下很容易发生哈希冲突(哈希碰撞)。

在这里插入图片描述

为了解决这里的问题,有人提出了,开散列这种方法。
开散列:

当然这里也是利用了哈希映射,只是对底层存储结构做了改变。

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

通俗的讲,就是我们在闭散列使用的是,vector< int>来模拟哈希表,而使用它发生哈希冲突时我们就要,使用线性探测这种方法来解决它,这样太麻烦了效率还低,不如把哈希表中每个节点换成一个单链表(这里叫哈希桶),这样再发生哈希冲突,我们就可以直接在链表中插入,哈希冲突就很好的解决了。
在这里插入图片描述

二、开散列的实现(链地址法的实现)

2.1、哈希桶结点定义

我们想要利用单链表形式来存储关键码,首先要定义链表结点。
注:代码的注释可以帮助我们理解


template<class K, class V>
struct HashNode
{
HashNode* _next;//链接结点
pair<K, V> _kv;//存储关键码

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

2.2、哈希函数的实现

同闭散列一样,这里我们也需要哈希函数帮助我们建立,关键码与存储位置之间的关系。

 template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>//,模板特化,应对string类型情况
struct HashFunc<string>
{
size_t operator()(const string& key)
{
// BKDR
size_t hash = 0;
for (auto e : key)
{
hash *= 31;//一种算法,可以有效降低字符串映射位置相同的概率
hash += e;
}
cout << key << ":" << hash << endl;
return hash;
}
};

2.3、插入操作

通过哈希映射找到桶的位置,使用头插尾插都可(同单链表的插入操作)。

在进行插入操作时,如果哈希桶过长(单链表过长)会导致我们的查找效率变低,因此当插入一定量的数据时,我们仍需要进行扩容操作,这里我们也使用负载因此作为是否扩容的依据。

       bool Insert(const pair<K, V>& kv)
       {
           if (Find(kv.first))//查找防止插入重复
               return false;
           Hash hf;
           if (_n == _tables.size())
           {
               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 hashi = hf(cur->_kv.first) % newTables.size();
                       cur->_next = newTables[hashi];
                       newTables[hashi] = cur;
                       cur = next;
                   }

                   _tables[i] = nullptr;
               }

               _tables.swap(newTables);
           }
           size_t hashi = hf(kv.first) % _tables.size();
           Node* newnode = new Node(kv);
           // 头插
           newnode->_next = _tables[hashi];
           _tables[hashi] = newnode;
           ++_n;
           return true;
       }
 }

2.4、查找操作

使用关键码(要查找值)映射出哈希值(也就是关键所在桶的序号),在对应桶中查找。

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

2.5、删除操作

同单链表删除相同

      bool Erase(const K& key)
      {
          Hash hf;
          size_t hashi = hf(key) % _tables.size();
          Node* prev = nullptr;
          Node* cur = _tables[hashi];
          while (cur)
          {
              if (cur->_kv.first == key)
              {
                  if (prev == nullptr)
                  {
                      _tables[hashi] = cur->_next;
                  }
                  else
                  {
                      prev->_next = cur->_next;
                  }
                  delete cur;

                  return true;
              }

              prev = cur;
              cur = cur->_next;
          }

          return false;
      }

3、全部代码

剩下的简单成员函数,就交给大家自己看吧

namespace hash_bucket
{
    template<class K>
    struct HashFunc
    {
        size_t operator()(const K& key)
        {
            return (size_t)key;
        }
    };
    template<>
    struct HashFunc<string>
    {
        size_t operator()(const string& key)
        {
            // BKDR
            size_t hash = 0;
            for (auto e : key)
            {
                hash *= 31;
                hash += e;
            }

            cout << key << ":" << hash << endl;
            return hash;
        }
    };
    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 Hash = HashFunc<K>>
    class HashTable
    {
        typedef HashNode<K, V> Node;
    public:
        HashTable()
        {
            _tables.resize(10);
        }

        ~HashTable()
        {
            for (size_t i = 0; i < _tables.size(); i++)
            {
                Node* cur = _tables[i];
                while (cur)
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                _tables[i] = nullptr;
            }
        }

        bool Insert(const pair<K, V>& kv)
        {
            if (Find(kv.first))
                return false;

            Hash hf;
            if (_n == _tables.size())
            {
                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 hashi = hf(cur->_kv.first) % newTables.size();
                        cur->_next = newTables[hashi];
                        newTables[hashi] = cur;

                        cur = next;
                    }

                    _tables[i] = nullptr;
                }

                _tables.swap(newTables);
            }

            size_t hashi = hf(kv.first) % _tables.size();
            Node* newnode = new Node(kv);

            // 头插
            newnode->_next = _tables[hashi];
            _tables[hashi] = newnode;
            ++_n;

            return true;
        }

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

                cur = cur->_next;
            }

            return NULL;
        }

        bool Erase(const K& key)
        {
            Hash hf;
            size_t hashi = hf(key) % _tables.size();
            Node* prev = nullptr;
            Node* cur = _tables[hashi];
            while (cur)
            {
                if (cur->_kv.first == key)
                {
                    if (prev == nullptr)
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;

                    return true;
                }

                prev = cur;
                cur = cur->_next;
            }

            return false;
        }
    private:
        vector<Node*> _tables;//哈希表
        size_t _n = 0;
    };

总结

总的来说,这部分代码实现比较简单,主要时掌握哈希思想。


原文地址:https://blog.csdn.net/2301_80774875/article/details/144155841

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!