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

c++的学习之路：28、哈希表

作者：繁依Fanyi0 | 2024-05-06 02:40:42

赞

踩

c++的学习之路：28、哈希表

摘要

本章主要是说一下哈希的实现

目录

摘要

一、哈希表

1、哈希概念

2、闭散列

1、节点创建

2、插入

3、查找

4、删除

5、测试

3、开散列

1、创建

2、插入

3、查找

4、删除

5、析构函数

二、map

三、set

四、位图与布隆过滤器

五、代码

test.cpp

HashTable.h

HashTable副本.h

UnorderedMap.h

UnorderedSet.h

一、哈希表

1、哈希概念

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

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

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

2、搜索元素

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

该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称
为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity;  capacity为存储元素底层空间总的大小，用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快

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

解决哈希冲突两种常见的方法是：闭散列和开散列，下面将会讲

2、闭散列

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

线性探测法
比如下图中的场景，现在需要插入元素44，先通过哈希函数计算哈希地址，hashAddr为4，因此44理论上应该插在该位置，但是该位置已经放了值为4的元素，即发生哈希冲突。

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

插入：通过哈希函数获取待插入元素在哈希表中的位置，如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素

 下面将会讲一下闭散列的代码实现

1、节点创建

这里是创建了一个枚举的表，里面存着三种状态，分别是空、存在和删除，分别代表这数据是否存在哈希表里面，节点里面存着pair创建的键值对和状态，这里默认初始为空的状态也就是EMPTY

enum State//记录状态，空、存在、删除
    {
        EMPTY,
        EXIST,
        DELETE
    };

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

2、插入

这个插入的写法，首先是判断是否有重复的，这里重复就直接返回flase，然后判断吧哈希表是否为空或者平衡因子是否等于0.7，当这两个条件，任意一个达成的时候，就可以进行扩容，这里是直接而被扩容，然后复用插入这个函数，然后再把两个表进行交换，这里是插入位置的计算是直接%上哈希表的大小，然后才直接找到映射的位置，然后进行插入，如果当前位置已经有数据的时候，就向后进行++找到没有数据的位置插入。

bool Insert(const pair<K, V> kv)//插入
        {
            if (Find(kv.first))//判断是否重复
                return false;
            if (_tables.size() == 0 || _n * 10 / _tables.size() == 7)//判断平衡因子或者刚开始的时候扩容，平衡因子是0.7
            {
                size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;//二倍扩容
                HashTable<K, V> newhs;//新表
                newhs._tables.resize(newsize);//开辟空间
                for (auto e : _tables)
                {
                    if (e._state == EXIST)
                    {
                        newhs.Insert(e._kv);
                    }
                }
                _tables.swap(newhs._tables);//交换两个表
            }
            size_t hashi = kv.first % _tables.size();//进行位置映射
            size_t i = 1;
            size_t index = hashi;
            while (_tables[index]._state == EXIST)//如果存在就进行向后面进行++找到没使用的格子插入
            {
                index = hashi + i;
                index %= _tables.size();
                ++i;
            }
            _tables[index]._kv = kv;
            _tables[index]._state = EXIST;
            _n++;
            return true;
        }

3、查找

这个查找也是利用映射位置进行查找，如果没有就进行向后遍历去查找，如果还是没有找到就返回空，找到就返回当前节点的位置

HashData<K, V>* Find(const K& key)//查找
        {
            if (_tables.size() == 0)
            {
                return nullptr;
            }
            size_t hashi = key % _tables.size();
            size_t i = 1;
            size_t index = hashi;
            while (_tables[index]._state != EMPTY)//不等于空就继续查找
            {
                if (_tables[index]._state == EXIST && _tables[index]._kv.first == key)
                {//状态等于插入并且key值相等
                    return&_tables[index];
                }
                index = hashi + i;
                index %= _tables.size();
                i++;
                if (index == hashi)
                {
                    break;
                }
            }
            return nullptr;
        }

4、删除

这个删除就是进行查找，查到就进行删除，这里需要把状态置为删除，然后n--

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

5、测试

这里就是进行插入，插入结束后，就进行查找，找到后就是打印在，然后再把13删除，然后就再次查找，这次肯定是找不到，也就是打印不在

 

void TestHashTable1()
    {
        int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
        HashTable<int, int> ht;
        for (auto e : a)
        {
            ht.Insert(make_pair(e, e));
        }

        ht.Insert(make_pair(15, 15));

        if (ht.Find(13))
        {
            cout << "13在" << endl;
        }
        else
        {
            cout << "13不在" << endl;
        }

        ht.Erase(13);

        if (ht.Find(13))
        {
            cout << "13在" << endl;
        }
        else
        {
            cout << "13不在" << endl;
        }
    }

 

3、开散列

1、创建

这里是进行创建一个节点，里面存放的是下一个节点的地址和键值对，然后这里也是创建了一个仿函数，然后用以后续使用的方便，这里也是进行特化了一个字符串的。

template<class K, class V>
    struct HashNode//哈希节点
    {
        HashNode<K, V>* _next;
        pair<K, V> _kv;

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

    template<class K>
    struct HashFunc//仿函数进行使用，方便访问，重载了（），这样就可以传入各种类型的参数
    {
        size_t operator()(const K& key)
        {
            return key;
        }
    };

    template<>// 特化
    struct HashFunc<string>//特化一个字符串类型
    {
        // BKDR
        size_t operator()(const string& s)//这里是利用ASCLL码值存储
        {
            size_t hash = 0;
            for (auto ch : s)
            {
                hash += ch;
                hash *= 31;//BKDR的参考数字是31
            }
            return hash;
        }
    };

2、插入

这个插入和闭散列差不多，但是他是一个节点下面挂着一串一串的，这样就会减少冲突，这里的计算扩容就是按照大佬的写法就是利用素数进行扩容

size_t GetNextPrime(size_t prime)//素数，这里就是用来计算表扩容需要的大小，这里就是利用素数进行扩容的
        {
            static const int __stl_num_primes = 28;
            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
            };
            size_t i = 0;
            for (; i < __stl_num_primes; ++i)
            {
                if (__stl_prime_list[i] > prime)
                    return __stl_prime_list[i];
            }
            return __stl_prime_list[i];//找到下一个素数进行返回
        }

        bool Insert(const pair<K, V>& kv)//插入
        {
            if (Find(kv.first))//去查找需要插入的数，如果找到了就直接返回
                return false;
            Hash hash;
            if (_n == _tables.size())// 负载因因子==1时扩容
            {
                size_t newsize = GetNextPrime(_tables.size());//进行获取下一个素数
                vector<Node*> newtables(newsize, nullptr);//按照这个素数的大小进行创建新的表
                for (auto& cur : _tables)//遍历旧的表进行把之前的表插入在新的表
                {
                    while (cur)
                    {
                        Node* next = cur->_next;
                        size_t hashi = hash(cur->_kv.first) % newtables.size();
                        cur->_next = newtables[hashi];
                        newtables[hashi] = cur;
                        cur = next;
                    }
                }
                _tables.swap(newtables);//交换两个表
            }
            size_t hashi = hash(kv.first) % _tables.size();//计算需要插入的映射位置
            Node* newnode = new Node(kv);//创建一个新的节点
            newnode->_next = _tables[hashi];//然后进行头插
            _tables[hashi] = newnode;
            ++_n;//这里不能忘了把n进行++
            return true;
        }

3、查找

这个就是查找就是首先计算到映射的位置，因为开散列的情况下，就是下面在相应的映射位置下面挂着一长串节点，这里就是找到映射节点在进行遍历寻找。

Node* Find(const K& key)//查找
        {
            if (_tables.size() == 0)//表里面如果是空就返回空
                return nullptr;
            Hash hash;//利用仿函数创建key值
            size_t hashi = hash(key) % _tables.size();//这个就是计算需要映射的地址
            Node* cur = _tables[hashi];//然后记录当前节点
            while (cur)//利用这个节点进行遍历桶
            {
                if (cur->_kv.first == key)//如果找到相等key值的时候就返回当前节点
                    return cur;
                cur = cur->_next;//进行迭代
            }
            return nullptr;//找不到就返回空
        }

4、删除

这个删除的函数写法就是首先找到映射位置，然后这里需要注意的是要创建两个节点，以防在后面还有节点就给释放了，出现野指针的情况，这里是用两个接待你进行迭代，以防出现也野指针的情况

bool Erase(const K& key)//删除
        {
            Hash hash;//利用仿函数创建key值
            size_t hashi = hash(key) % _tables.size();//计算映射的地址
            Node* prev = nullptr;//这里是创建一个节点用来记录，以防删除的时候会造成野指针
            Node* cur = _tables[hashi];//利用cur记录桶的当前节点
            while (cur)//进行遍历
            {
                if (cur->_kv.first == key)//找到了
                {
                    if (prev == nullptr)//这时就进行判断perv是不是空节点，如果是就直接把桶的下一个节点挂在桶原来的节点
                    {
                        _tables[hashi] = cur->_next;
                    }
                    else//如果perv不是空节点，就把cur的下一个节点挂在了perv节点上面
                    {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    return true;
                }
                else//没找到就进行迭代
                {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;//全部遍历完还没有找到就返回false
        }

5、析构函数

这个析构函数的遍历是为把整个表全部都清理干净

~HashTable()//这个析构函数是为了把整个哈希表都清理干净
        {
            for (auto& cur : _tables)//遍历整个表
            {
                while (cur)//表里面的桶进行把那一串全删了，迭代进行
                {
                    Node* next = cur->_next;
                    delete cur;
                    cur = next;
                }
                cur = nullptr;
            }
        }

二、map

这个map的封装和上章的差不多，这里直接放测试了，然后代码放在文章末

void test_unordered_map1()
    {
        unordered_map<int, int> m;
        m.insert(make_pair(1, 1));
        m.insert(make_pair(3, 3));
        m.insert(make_pair(2, 2));

        unordered_map<int, int>::iterator it = m.begin();
        while (it != m.end())
        {

            cout << it->first << ":" << it->second << endl;
            ++it;
        }
        cout << endl;
    }

    void test_unordered_map2()
    {
        string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };
        unordered_map<string, int> countMap;
        for (auto& e : arr)
        {
            countMap[e]++;
        }

        for (auto& kv : countMap)
        {
            cout << kv.first << ":" << kv.second << endl;
        }
    }

三、set

这个set的封装和上章的差不多，这里直接放测试了，然后代码放在文章末

void test_unordered_set1()
    {
        int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
        unordered_set<int> s;
        for (auto e : a)
        {
            s.insert(e);
        }

        s.insert(54);
        s.insert(107);

        unordered_set<int>::iterator it = s.begin();
        while (it != s.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;

        for (auto e : s)
        {
            cout << e << " ";
        }
        cout << endl;

        print(s);
    }

 

四、位图与布隆过滤器

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用
来判断某个数据存不存在的。

布隆过滤器提出：

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1、用哈希表存储用户记录，缺点：浪费空间

2、用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。

3、将哈希与位图结合，即布隆过滤器

布隆过滤器概念：

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概
率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存
在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也
可以节省大量的内存空间。

五、代码

test.cpp

  1. #define _CRT_SECURE_NO_WARNINGS 1
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6. #include "HashTable.h"
  7. #include "HashTable - 副本.h"
  8. #include "UnorderedMap.h"
  9. #include "UnorderedSet.h"
  10.  
  11. int main()
  12. {
  13. 	//ly1::TestHashTable1();
  14. 	//ly2::TestHashTable1();
  15. 	//ly2::TestHashTable2();	
  16. 	//ly2::TestHashTable3();
  17. 	lyset::test_unordered_set1();
  18. 	//lymap::test_unordered_map1();
  19. 	//lymap::test_unordered_map2();
  20. }

HashTable.h

  1. #pragma once
  2.  
  3. namespace ly3
  4. {
  5. 	template<class T>
  6. 	struct HashNode//哈希节点
  7. 	{
  8. 		HashNode<T>* _next;
  9. 		T _data;
  10.  
  11. 		HashNode(const T& data)
  12. 			:_next(nullptr)
  13. 			, _data(data)
  14. 		{}
  15. 	};
  16.  
  17. 	template<class K>
  18. 	struct HashFunc//仿函数进行使用，方便访问，重载了（），这样就可以传入各种类型的参数
  19. 	{
  20. 		size_t operator()(const K& key)
  21. 		{
  22. 			return key;
  23. 		}
  24. 	};
  25.  
  26. 	// 特化
  27. 	template<>// 特化
  28. 	struct HashFunc<string>//特化一个字符串类型
  29. 	{
  30. 		// BKDR
  31. 		size_t operator()(const string& s)//这里是利用ASCLL码值存储
  32. 		{
  33. 			size_t hash = 0;
  34. 			for (auto ch : s)
  35. 			{
  36. 				hash += ch;
  37. 				hash *= 31;//BKDR的参考数字是31
  38. 			}
  39. 			return hash;
  40. 		}
  41. 	};
  42.  
  43. 	//前置声明
  44. 	template<class K, class T, class KeyOfT, class Hash>
  45. 	class HashTable;
  46.  
  47. 	template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
  48. 	struct __HashIterator//迭代器
  49. 	{//下面是一堆重定义，方便编写
  50. 		typedef HashNode<T> Node;
  51. 		typedef HashTable<K, T, KeyOfT, Hash> HT;
  52. 		typedef __HashIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;
  53. 		typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
  54.  
  55. 		Node* _node;
  56. 		const HT* _ht;
  57. 		//下面都是两种，一个是普通迭代器，一个是const迭代器
  58. 		__HashIterator(Node* node, const HT* ht)
  59. 			:_node(node)
  60. 			, _ht(ht)
  61. 		{}
  62.  
  63. 		__HashIterator(const Iterator& it)
  64. 			:_node(it._node)
  65. 			, _ht(it._ht)
  66. 		{}
  67.  
  68. 		Ref operator*()
  69. 		{
  70. 			return _node->_data;
  71. 		}
  72.  
  73. 		Ptr operator->()
  74. 		{
  75. 			return &_node->_data;
  76. 		}
  77.  
  78. 		bool operator!=(const Self& s)//判断是否相等，直接判断地址就可以
  79. 		{
  80. 			return _node != s._node;
  81. 		}
  82.  
  83. 		Self& operator++()//这个++就是用来继续遍历的，就是首先把桶内的数据遍历完，地址在进行++
  84. 		{
  85. 			if (_node->_next != nullptr)//下一个节点不是空就继续迭代
  86. 			{
  87. 				_node = _node->_next;
  88. 			}
  89. 			else//如果是有就进行查找下一个不为空的地址
  90. 			{
  91. 				KeyOfT kot;
  92. 				Hash hash;
  93. 				size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();//记录映射的地址
  94. 				++hashi;
  95. 				while (hashi < _ht->_tables.size())//进行迭代
  96. 				{
  97. 					if (_ht->_tables[hashi])
  98. 					{
  99. 						_node = _ht->_tables[hashi];
  100. 						break;
  101. 					}
  102. 					else
  103. 					{
  104. 						++hashi;
  105. 					}
  106. 				}
  107. 				if (hashi == _ht->_tables.size())//如果到最后，也就是满的地方，就把node置为空
  108. 				{
  109. 					_node = nullptr;
  110. 				}
  111. 			}
  112.  
  113. 			return *this;
  114. 		}
  115. 	};
  116.  
  117. 	template<class K, class T, class KeyOfT, class Hash>
  118. 	class HashTable
  119. 	{
  120. 		template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
  121. 		friend struct __HashIterator;
  122.  
  123. 		typedef HashNode<T> Node;
  124. 	public:
  125. 		typedef __HashIterator<K, T, T&, T*, KeyOfT, Hash> iterator;
  126. 		typedef __HashIterator<K, T, const T&, const T*, KeyOfT, Hash> const_iterator;
  127.  
  128. 		iterator begin()//begin迭代器
  129. 		{
  130. 			Node* cur = nullptr;
  131. 			for (size_t i = 0; i < _tables.size(); ++i)//遍历找到第一个不为空的直接返回
  132. 			{
  133. 				cur = _tables[i];
  134. 				if (cur)
  135. 				{
  136. 					break;
  137. 				}
  138. 			}
  139.  
  140. 			return iterator(cur, this);
  141. 		}
  142.  
  143. 		iterator end()//返回最后一个迭代器
  144. 		{
  145. 			return iterator(nullptr, this);
  146. 		}
  147.  
  148. 		const_iterator begin() const//const版本的
  149. 		{
  150. 			Node* cur = nullptr;
  151. 			for (size_t i = 0; i < _tables.size(); ++i)
  152. 			{
  153. 				cur = _tables[i];
  154. 				if (cur)
  155. 				{
  156. 					break;
  157. 				}
  158. 			}
  159.  
  160. 			return const_iterator(cur, this);
  161. 		}
  162.  
  163. 		const_iterator end() const
  164. 		{
  165. 			return const_iterator(nullptr, this);
  166. 		}
  167.  
  168. 		~HashTable()//这个析构函数是为了把整个哈希表都清理干净
  169. 		{
  170. 			for (auto& cur : _tables)//遍历整个表
  171. 			{
  172. 				while (cur)//表里面的桶进行把那一串全删了，迭代进行
  173. 				{
  174. 					Node* next = cur->_next;
  175. 					delete cur;
  176. 					cur = next;
  177. 				}
  178. 				cur = nullptr;
  179. 			}
  180. 		}
  181.  
  182. 		iterator Find(const K& key)//查找，这个就是利用迭代器查找，原理和上面一个没有封装版本差不多
  183. 		{
  184. 			if (_tables.size() == 0)
  185. 				return end();
  186. 			KeyOfT kot;
  187. 			Hash hash;
  188. 			size_t hashi = hash(key) % _tables.size();
  189. 			Node* cur = _tables[hashi];
  190. 			while (cur)
  191. 			{
  192. 				if (kot(cur->_data) == key)
  193. 				{
  194. 					return iterator(cur, this);
  195. 				}
  196. 				cur = cur->_next;
  197. 			}
  198. 			return end();
  199. 		}
  200.  
  201. 		bool Erase(const K& key)//删除的也是和原始版本差不多
  202. 		{
  203. 			Hash hash;
  204. 			KeyOfT kot;
  205. 			size_t hashi = hash(key) % _tables.size();
  206. 			Node* prev = nullptr;
  207. 			Node* cur = _tables[hashi];
  208. 			while (cur)
  209. 			{
  210. 				if (kot(cur->_data) == key)
  211. 				{
  212. 					if (prev == nullptr)
  213. 					{
  214. 						_tables[hashi] = cur->_next;
  215. 					}
  216. 					else
  217. 					{
  218. 						prev->_next = cur->_next;
  219. 					}
  220. 					delete cur;
  221. 					return true;
  222. 				}
  223. 				else
  224. 				{
  225. 					prev = cur;
  226. 					cur = cur->_next;
  227. 				}
  228. 			}
  229. 			return false;
  230. 		}
  231.  
  232. 		size_t GetNextPrime(size_t prime)
  233. 		{
  234. 			static const int __stl_num_primes = 28;
  235. 			static const unsigned long __stl_prime_list[__stl_num_primes] =
  236. 			{
  237. 				53, 97, 193, 389, 769,
  238. 				1543, 3079, 6151, 12289, 24593,
  239. 				49157, 98317, 196613, 393241, 786433,
  240. 				1572869, 3145739, 6291469, 12582917, 25165843,
  241. 				50331653, 100663319, 201326611, 402653189, 805306457,
  242. 				1610612741, 3221225473, 4294967291
  243. 			};
  244.  
  245. 			size_t i = 0;
  246. 			for (; i < __stl_num_primes; ++i)
  247. 			{
  248. 				if (__stl_prime_list[i] > prime)
  249. 					return __stl_prime_list[i];
  250. 			}
  251. 			return __stl_prime_list[i];
  252. 		}
  253.  
  254. 		pair<iterator, bool> Insert(const T& data)
  255. 		{
  256. 			KeyOfT kot;
  257. 			iterator it = Find(kot(data));
  258. 			if (it != end())
  259. 			{
  260. 				return make_pair(it, false);
  261. 			}
  262. 			Hash hash;
  263. 			if (_n == _tables.size())
  264. 			{
  265. 				size_t newsize = GetNextPrime(_tables.size());
  266. 				vector<Node*> newtables(newsize, nullptr);
  267. 				for (auto& cur : _tables)
  268. 				{
  269. 					while (cur)
  270. 					{
  271. 						Node* next = cur->_next;
  272. 						size_t hashi = hash(kot(cur->_data)) % newtables.size();
  273. 						cur->_next = newtables[hashi];
  274. 						newtables[hashi] = cur;
  275. 						cur = next;
  276. 					}
  277. 				}
  278. 				_tables.swap(newtables);
  279. 			}
  280. 			size_t hashi = hash(kot(data)) % _tables.size();
  281. 			Node* newnode = new Node(data);
  282. 			newnode->_next = _tables[hashi];
  283. 			_tables[hashi] = newnode;
  284. 			++_n;
  285. 			return make_pair(iterator(newnode, this), false);;
  286. 		}
  287.  
  288. 		size_t MaxBucketSize()
  289. 		{
  290. 			size_t max = 0;
  291. 			for (size_t i = 0; i < _tables.size(); ++i)
  292. 			{
  293. 				auto cur = _tables[i];
  294. 				size_t size = 0;
  295. 				while (cur)
  296. 				{
  297. 					++size;
  298. 					cur = cur->_next;
  299. 				}
  300. 				if (size > max)
  301. 				{
  302. 					max = size;
  303. 				}
  304. 			}
  305. 			return max;
  306. 		}
  307. 	private:
  308. 		vector<Node*> _tables; // 指针数组
  309. 		size_t _n = 0; // 存储有效数据个数
  310. 	};
  311. }

HashTable副本.h

  1. #pragma once
  2.  
  3. namespace ly1//散列
  4. {
  5. 	enum State//记录状态，空、存在、删除
  6. 	{
  7. 		EMPTY,
  8. 		EXIST,
  9. 		DELETE
  10. 	};
  11.  
  12. 	template<class K, class V>
  13. 	struct HashData
  14. 	{
  15. 		pair<K, V> _kv;
  16. 		State _state = EMPTY;
  17. 	};
  18.  
  19. 	template<class K, class V>
  20. 	class HashTable
  21. 	{
  22. 	public:
  23. 		bool Insert(const pair<K, V> kv)//插入
  24. 		{
  25. 			if (Find(kv.first))//判断是否重复
  26. 				return false;
  27. 			if (_tables.size() == 0 || _n * 10 / _tables.size() == 7)//判断平衡因子或者刚开始的时候扩容，平衡因子是0.7
  28. 			{
  29. 				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;//二倍扩容
  30. 				HashTable<K, V> newhs;//新表
  31. 				newhs._tables.resize(newsize);//开辟空间
  32. 				for (auto e : _tables)
  33. 				{
  34. 					if (e._state == EXIST)
  35. 					{
  36. 						newhs.Insert(e._kv);
  37. 					}
  38. 				}
  39. 				_tables.swap(newhs._tables);//交换两个表
  40. 			}
  41. 			size_t hashi = kv.first % _tables.size();//进行位置映射
  42. 			size_t i = 1;
  43. 			size_t index = hashi;
  44. 			while (_tables[index]._state == EXIST)//如果存在就进行向后面进行++找到没使用的格子插入
  45. 			{
  46. 				index = hashi + i;
  47. 				index %= _tables.size();
  48. 				++i;
  49. 			}
  50. 			_tables[index]._kv = kv;
  51. 			_tables[index]._state = EXIST;
  52. 			_n++;
  53. 			return true;
  54. 		}
  55.  
  56. 		HashData<K, V>* Find(const K& key)//查找
  57. 		{
  58. 			if (_tables.size() == 0)
  59. 			{
  60. 				return nullptr;
  61. 			}
  62. 			size_t hashi = key % _tables.size();
  63. 			size_t i = 1;
  64. 			size_t index = hashi;
  65. 			while (_tables[index]._state != EMPTY)//不等于空就继续查找
  66. 			{
  67. 				if (_tables[index]._state == EXIST && _tables[index]._kv.first == key)
  68. 				{//状态等于插入并且key值相等
  69. 					return&_tables[index];
  70. 				}
  71. 				index = hashi + i;
  72. 				index %= _tables.size();
  73. 				i++;
  74. 				if (index == hashi)
  75. 				{
  76. 					break;
  77. 				}
  78. 			}
  79. 			return nullptr;
  80. 		}
  81.  
  82. 		bool Erase(const K& key)//删除
  83. 		{
  84. 			HashData<K, V>* ret = Find(key);
  85. 			if (ret)
  86. 			{
  87. 				ret->_state = DELETE;
  88. 				_n--;
  89. 				return true;
  90. 			}
  91. 			else
  92. 			{
  93. 				return false;
  94. 			}
  95. 		}
  96. 	private:
  97. 		vector<HashData<K, V>> _tables;
  98. 		size_t _n = 0; // 存储的数据个数
  99. 	};
  100.  
  101. 	void TestHashTable1()
  102. 	{
  103. 		int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
  104. 		HashTable<int, int> ht;
  105. 		for (auto e : a)
  106. 		{
  107. 			ht.Insert(make_pair(e, e));
  108. 		}
  109.  
  110. 		ht.Insert(make_pair(15, 15));
  111.  
  112. 		if (ht.Find(13))
  113. 		{
  114. 			cout << "13在" << endl;
  115. 		}
  116. 		else
  117. 		{
  118. 			cout << "13不在" << endl;
  119. 		}
  120.  
  121. 		ht.Erase(13);
  122.  
  123. 		if (ht.Find(13))
  124. 		{
  125. 			cout << "13在" << endl;
  126. 		}
  127. 		else
  128. 		{
  129. 			cout << "13不在" << endl;
  130. 		}
  131. 	}
  132. }
  133.  
  134.  
  135. namespace ly2
  136. {
  137. 	template<class K, class V>
  138. 	struct HashNode//哈希节点
  139. 	{
  140. 		HashNode<K, V>* _next;
  141. 		pair<K, V> _kv;
  142.  
  143. 		HashNode(const pair<K, V>& kv)
  144. 			:_next(nullptr)
  145. 			, _kv(kv)
  146. 		{}
  147. 	};
  148.  
  149. 	template<class K>
  150. 	struct HashFunc//仿函数进行使用，方便访问，重载了（），这样就可以传入各种类型的参数
  151. 	{
  152. 		size_t operator()(const K& key)
  153. 		{
  154. 			return key;
  155. 		}
  156. 	};
  157.  
  158. 	template<>// 特化
  159. 	struct HashFunc<string>//特化一个字符串类型
  160. 	{
  161. 		// BKDR
  162. 		size_t operator()(const string& s)//这里是利用ASCLL码值存储
  163. 		{
  164. 			size_t hash = 0;
  165. 			for (auto ch : s)
  166. 			{
  167. 				hash += ch;
  168. 				hash *= 31;//BKDR的参考数字是31
  169. 			}
  170. 			return hash;
  171. 		}
  172. 	};
  173.  
  174. 	template<class K, class V, class Hash = HashFunc<K>>
  175. 	class HashTable
  176. 	{
  177. 		typedef HashNode<K, V> Node;
  178. 	public:
  179. 		Node* Find(const K& key)//查找
  180. 		{
  181. 			if (_tables.size() == 0)//表里面如果是空就返回空
  182. 				return nullptr;
  183. 			Hash hash;//利用仿函数创建key值
  184. 			size_t hashi = hash(key) % _tables.size();//这个就是计算需要映射的地址
  185. 			Node* cur = _tables[hashi];//然后记录当前节点
  186. 			while (cur)//利用这个节点进行遍历桶
  187. 			{
  188. 				if (cur->_kv.first == key)//如果找到相等key值的时候就返回当前节点
  189. 					return cur;
  190. 				cur = cur->_next;//进行迭代
  191. 			}
  192. 			return nullptr;//找不到就返回空
  193. 		}
  194.  
  195. 		bool Erase(const K& key)//删除
  196. 		{
  197. 			Hash hash;//利用仿函数创建key值
  198. 			size_t hashi = hash(key) % _tables.size();//计算映射的地址
  199. 			Node* prev = nullptr;//这里是创建一个节点用来记录，以防删除的时候会造成野指针
  200. 			Node* cur = _tables[hashi];//利用cur记录桶的当前节点
  201. 			while (cur)//进行遍历
  202. 			{
  203. 				if (cur->_kv.first == key)//找到了
  204. 				{
  205. 					if (prev == nullptr)//这时就进行判断perv是不是空节点，如果是就直接把桶的下一个节点挂在桶原来的节点
  206. 					{
  207. 						_tables[hashi] = cur->_next;
  208. 					}
  209. 					else//如果perv不是空节点，就把cur的下一个节点挂在了perv节点上面
  210. 					{
  211. 						prev->_next = cur->_next;
  212. 					}
  213. 					delete cur;
  214. 					return true;
  215. 				}
  216. 				else//没找到就进行迭代
  217. 				{
  218. 					prev = cur;
  219. 					cur = cur->_next;
  220. 				}
  221. 			}
  222. 			return false;//全部遍历完还没有找到就返回false
  223. 		}
  224.  
  225. 		size_t GetNextPrime(size_t prime)//素数，这里就是用来计算表扩容需要的大小，这里就是利用素数进行扩容的
  226. 		{
  227. 			static const int __stl_num_primes = 28;
  228. 			static const unsigned long __stl_prime_list[__stl_num_primes] =
  229. 			{
  230. 				53, 97, 193, 389, 769,
  231. 				1543, 3079, 6151, 12289, 24593,
  232. 				49157, 98317, 196613, 393241, 786433,
  233. 				1572869, 3145739, 6291469, 12582917, 25165843,
  234. 				50331653, 100663319, 201326611, 402653189, 805306457,
  235. 				1610612741, 3221225473, 4294967291
  236. 			};
  237. 			size_t i = 0;
  238. 			for (; i < __stl_num_primes; ++i)
  239. 			{
  240. 				if (__stl_prime_list[i] > prime)
  241. 					return __stl_prime_list[i];
  242. 			}
  243. 			return __stl_prime_list[i];//找到下一个素数进行返回
  244. 		}
  245.  
  246. 		bool Insert(const pair<K, V>& kv)//插入
  247. 		{
  248. 			if (Find(kv.first))//去查找需要插入的数，如果找到了就直接返回
  249. 				return false;
  250. 			Hash hash;
  251. 			if (_n == _tables.size())// 负载因因子==1时扩容
  252. 			{
  253. 				size_t newsize = GetNextPrime(_tables.size());//进行获取下一个素数
  254. 				vector<Node*> newtables(newsize, nullptr);//按照这个素数的大小进行创建新的表
  255. 				for (auto& cur : _tables)//遍历旧的表进行把之前的表插入在新的表
  256. 				{
  257. 					while (cur)
  258. 					{
  259. 						Node* next = cur->_next;
  260. 						size_t hashi = hash(cur->_kv.first) % newtables.size();
  261. 						cur->_next = newtables[hashi];
  262. 						newtables[hashi] = cur;
  263. 						cur = next;
  264. 					}
  265. 				}
  266. 				_tables.swap(newtables);//交换两个表
  267. 			}
  268. 			size_t hashi = hash(kv.first) % _tables.size();//计算需要插入的映射位置
  269. 			Node* newnode = new Node(kv);//创建一个新的节点
  270. 			newnode->_next = _tables[hashi];//然后进行头插
  271. 			_tables[hashi] = newnode;
  272. 			++_n;//这里不能忘了把n进行++
  273. 			return true;
  274. 		}
  275.  
  276. 		size_t MaxBucketSize()//获取最大桶的大小
  277. 		{
  278. 			size_t max = 0;//用来记录最大的大小
  279. 			for (size_t i = 0; i < _tables.size(); ++i)//首先就是遍历整个表
  280. 			{
  281. 				auto cur = _tables[i];//获取表的每个节点
  282. 				size_t size = 0;//每一遍的大小
  283. 				while (cur)//进行迭代
  284. 				{
  285. 					++size;
  286. 					cur = cur->_next;
  287. 				}
  288. 				if (size > max)//如果这一遍的大小比之前记录的大小大就把这个数值给记录最大数的变量
  289. 				{
  290. 					max = size;
  291. 				}
  292. 				return max;
  293. 			}
  294. 		}
  295.  
  296. 		~HashTable()//这个析构函数是为了把整个哈希表都清理干净
  297. 		{
  298. 			for (auto& cur : _tables)//遍历整个表
  299. 			{
  300. 				while (cur)//表里面的桶进行把那一串全删了，迭代进行
  301. 				{
  302. 					Node* next = cur->_next;
  303. 					delete cur;
  304. 					cur = next;
  305. 				}
  306. 				cur = nullptr;
  307. 			}
  308. 		}
  309. 	private:
  310. 		vector<Node*> _tables; // 指针数组
  311. 		size_t _n = 0; // 存储有效数据个数
  312. 	};
  313.  
  314. 	void TestHashTable1()
  315. 	{
  316. 		int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
  317. 		HashTable<int, int> ht;
  318. 		for (auto e : a)
  319. 		{
  320. 			ht.Insert(make_pair(e, e));
  321. 		}
  322.  
  323. 		ht.Insert(make_pair(15, 15));
  324. 		ht.Insert(make_pair(25, 25));
  325. 		ht.Insert(make_pair(35, 35));
  326. 		ht.Insert(make_pair(45, 45));
  327. 		ht.Erase(12);
  328. 		ht.Erase(3);
  329. 		ht.Erase(33);
  330. 	}
  331.  
  332. 	void TestHashTable2()
  333. 	{
  334. 		HashTable<string, string> ht;
  335. 		ht.Insert(make_pair("sort", "排序"));
  336. 		ht.Insert(make_pair("string", "字符串"));
  337. 		ht.Insert(make_pair("left", "左边"));
  338. 		ht.Insert(make_pair("right", "右边"));
  339. 		ht.Insert(make_pair("", "右边"));
  340. 	}
  341.  
  342. 	void TestHashTable3()
  343. 	{
  344. 		size_t N = 900000;
  345. 		HashTable<int, int> ht;
  346. 		srand((unsigned)time(0));
  347. 		for (size_t i = 0; i < N; ++i)
  348. 		{
  349. 			size_t x = rand() + i;
  350. 			ht.Insert(make_pair(x, x));
  351. 		}
  352. 		cout << ht.MaxBucketSize() << endl;
  353. 	}
  354. }

UnorderedMap.h

  1. #pragma once
  2.  
  3. namespace lymap
  4. {
  5. 	template<class K, class V, class Hash = ly3::HashFunc<K>>
  6. 	class unordered_map
  7. 	{
  8. 	public:
  9. 		struct MapKeyOfT
  10. 		{
  11. 			const K& operator()(const pair<K, V>& kv)
  12. 			{
  13. 				return kv.first;
  14. 			}
  15. 		};
  16. 	public:
  17. 		typedef typename ly3::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;
  18. 		typedef typename ly3::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::const_iterator const_iterator;
  19.  
  20. 		iterator begin()
  21. 		{
  22. 			return _ht.begin();
  23. 		}
  24.  
  25. 		iterator end()
  26. 		{
  27. 			return _ht.end();
  28. 		}
  29.  
  30. 		const_iterator begin() const
  31. 		{
  32. 			return _ht.begin();
  33. 		}
  34.  
  35. 		const_iterator end() const
  36. 		{
  37. 			return _ht.end();
  38. 		}
  39.  
  40. 		pair<iterator, bool> insert(const pair<K, V>& kv)
  41. 		{
  42. 			return _ht.Insert(kv);
  43. 		}
  44.  
  45. 		V& operator[](const K& key)
  46. 		{
  47. 			pair<iterator, bool> ret = insert(make_pair(key, V()));
  48. 			return ret.first->second;
  49. 		}
  50.  
  51. 		iterator find(const K& key)
  52. 		{
  53. 			return _ht.Find(key);
  54. 		}
  55.  
  56. 		bool erase(const K& key)
  57. 		{
  58. 			return _ht.Erase(key);
  59. 		}
  60.  
  61. 	private:
  62. 		ly3::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
  63. 	};
  64.  
  65. 	void test_unordered_map1()
  66. 	{
  67. 		unordered_map<int, int> m;
  68. 		m.insert(make_pair(1, 1));
  69. 		m.insert(make_pair(3, 3));
  70. 		m.insert(make_pair(2, 2));
  71.  
  72. 		unordered_map<int, int>::iterator it = m.begin();
  73. 		while (it != m.end())
  74. 		{
  75.  
  76. 			cout << it->first << ":" << it->second << endl;
  77. 			++it;
  78. 		}
  79. 		cout << endl;
  80. 	}
  81.  
  82. 	void test_unordered_map2()
  83. 	{
  84. 		string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉", "梨" };
  85. 		unordered_map<string, int> countMap;
  86. 		for (auto& e : arr)
  87. 		{
  88. 			countMap[e]++;
  89. 		}
  90.  
  91. 		for (auto& kv : countMap)
  92. 		{
  93. 			cout << kv.first << ":" << kv.second << endl;
  94. 		}
  95. 	}
  96. }

UnorderedSet.h

  1. #pragma once
  2. namespace lyset
  3. {
  4. 	template<class K, class Hash = ly3::HashFunc<K>>
  5. 	class unordered_set
  6. 	{
  7. 	public:
  8. 		struct SetKeyOfT
  9. 		{
  10. 			const K& operator()(const K& key)
  11. 			{
  12. 				return key;
  13. 			}
  14. 		};
  15. 	public:
  16. 		typedef typename ly3::HashTable<K, K, SetKeyOfT, Hash>::const_iterator iterator;
  17. 		typedef typename ly3::HashTable<K, K, SetKeyOfT, Hash>::const_iterator const_iterator;
  18.  
  19.  
  20. 		iterator begin()
  21. 		{
  22. 			return _ht.begin();
  23. 		}
  24.  
  25. 		iterator end()
  26. 		{
  27. 			return _ht.end();
  28. 		}
  29.  
  30. 		const_iterator begin() const
  31. 		{
  32. 			return _ht.begin();
  33. 		}
  34.  
  35. 		const_iterator end() const
  36. 		{
  37. 			return _ht.end();
  38. 		}
  39.  
  40. 		pair<iterator, bool> insert(const K& key)
  41. 		{
  42. 			return _ht.Insert(key);
  43. 		}
  44.  
  45. 		iterator find(const K& key)
  46. 		{
  47. 			return _ht.Find(key);
  48. 		}
  49.  
  50. 		bool erase(const K& key)
  51. 		{
  52. 			return _ht.Erase(key);
  53. 		}
  54.  
  55. 	private:
  56. 		ly3::HashTable<K, K, SetKeyOfT, Hash> _ht;
  57. 	};
  58.  
  59. 	void print(const unordered_set<int>& s)
  60. 	{
  61. 		unordered_set<int>::const_iterator it = s.begin();
  62. 		while (it != s.end())
  63. 		{
  64. 			cout << *it << " ";
  65. 			++it;
  66. 		}
  67. 		cout << endl;
  68. 	}
  69.  
  70. 	void test_unordered_set1()
  71. 	{
  72. 		int a[] = { 3, 33, 2, 13, 5, 12, 1002 };
  73. 		unordered_set<int> s;
  74. 		for (auto e : a)
  75. 		{
  76. 			s.insert(e);
  77. 		}
  78.  
  79. 		s.insert(54);
  80. 		s.insert(107);
  81.  
  82. 		unordered_set<int>::iterator it = s.begin();
  83. 		while (it != s.end())
  84. 		{
  85. 			cout << *it << " ";
  86. 			++it;
  87. 		}
  88. 		cout << endl;
  89.  
  90. 		for (auto e : s)
  91. 		{
  92. 			cout << e << " ";
  93. 		}
  94. 		cout << endl;
  95.  
  96. 		print(s);
  97. 	}
  98. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/542069
推荐阅读
相关标签

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

  

闽ICP备14008679号