首页 > 编程语言 >C++：哈希表特性及开散列哈希表的模拟实现

C++：哈希表特性及开散列哈希表的模拟实现

时间：2024-07-17 22:25:53浏览次数：13  
标签：const key cur C++ 哈希 return 及开 size

目录

一、unordered_map

1.1 特性

1.2 接口

1.21 构造函数

1.22 iterator find(const K&  key)

1.23 insert

1.24 operator[]

1.25 erase

1.26 find

1.3 哈希概念

1.31闭散列哈希表

1.32开散列哈希表

二、部分功能模拟实现

hashtable.h

unordered_map.h

unordered_set.h

一、unordered_map

1.1 特性

a.可以存储键值对，pair<K,V>类型

b.可以按照任意指定的方式对元素排序

c.通过key访问单个元素比map快

d.重载了operator[]，可以通过key直接访问到value

e.是一个前向迭代器，支持++，但不支持--操作，其实也可以支持，不过代价太大了，效率会很低，可以想象成单链表。所以干脆不支持了。

1.2 接口

这里介绍需要注意的接口，其余的接口基本上看一眼文档就能了解

1.21 构造函数

支持迭代器区间构造，

支持给定初始的键值对构造

支持拷贝构造。

用法实例，这里用的是cplusplus.com的示例代码，本节用法示例中都是。

// constructing unordered_maps
#include <iostream>
#include <string>
#include <unordered_map>

typedef std::unordered_map<std::string,std::string> stringmap;

stringmap merge (stringmap a,stringmap b) {
  stringmap temp(a); temp.insert(b.begin(),b.end()); return temp;
}

int main ()
{
  stringmap first;                              // empty
  stringmap second ( {{"apple","red"},{"lemon","yellow"}} );       // init list
  stringmap third ( {{"orange","orange"},{"strawberry","red"}} );  // init list
  stringmap fourth (second);                    // copy
  stringmap fifth (merge(third,fourth));        // move
  stringmap sixth (fifth.begin(),fifth.end());  // range

  std::cout << "sixth contains:";
  for (auto& x: sixth) std::cout << " " << x.first << ":" << x.second;
  std::cout << std::endl;

  return 0;
}

1.22 iterator find(const K&  key)

此处返回的是key在哈希桶的位置，返回的是一个迭代器。

1.23 insert

（1）插入返回的是pair，pair的first是一个迭代器，指向的是插入成功/失败后的位置，成功就是插入成功的值的位置，失败就是end（）(基本上是这个）

second是bool值，插入成功是1，失败是0。下面代码在VS编译后也验证了unordered_map是不能插入相同的key值的。第二个ttest2是插入失败的。

1.24 operator[]

方括号重载。

int main ()
{
  std::unordered_map<std::string,std::string> mymap;

  mymap["Bakery"]="Barbara";  // new element  inserted
  mymap["Seafood"]="Lisa";    // new element  inserted
  mymap["Produce"]="John";    // new element  inserted

  std::string name = mymap["Bakery"];   // existing element accessed (read)
  mymap["Seafood"] = name;              // existing element accessed (written)

  mymap["Bakery"] = mymap["Produce"];   // existing elements accessed (read/written)

  name = mymap["Deli"];      // non-existing element: new element "Deli" inserted!

  mymap["Produce"] = mymap["Gifts"];    // new element "Gifts" inserted, "Produce" written

  for (auto& x: mymap) {
    std::cout << x.first << ": " << x.second << std::endl;
  }

  return 0;
}

当哈希表中没有该元素时，使用方括号重载会插入该元素，并返回该元素的second的引用,当哈希表中有该元素时，返回它的second的引用.

下图只是为了方便理解，实际中它哈希表中用的哈希函数（为了避免哈希冲突）哪种排序我不知道。所以单词的顺序可能有差别，但是键值对是这样发生改变的。

1.25 erase

给定要删除的元素的迭代器，给定要删除的元素迭代器区间，给定要删除的元素的key值，都可以删除掉。

int main ()
{
  std::unordered_map<std::string,std::string> mymap;

  // populating container:
  mymap["U.S."] = "Washington";
  mymap["U.K."] = "London";
  mymap["France"] = "Paris";
  mymap["Russia"] = "Moscow";
  mymap["China"] = "Beijing";
  mymap["Germany"] = "Berlin";
  mymap["Japan"] = "Tokyo";

  // erase examples:
  mymap.erase ( mymap.begin() );      // erasing by iterator
  mymap.erase ("France");             // erasing by key
  mymap.erase ( mymap.find("China"), mymap.end() ); // erasing by range

  // show content:
  for ( auto& x: mymap )
    std::cout << x.first << ": " << x.second << std::endl;

  return 0;
}

示例中，通过迭代器的开始删除了第一个；通过key，删除了key为France的键值对；通过迭代器区间，删除了两个。

1.26 find

查找，可以通过key值查找，返回的是迭代器，const函数就是const迭代器。

1.3 哈希概念

哈希是一种一一映射的概念，有点像数学中的函数。通过建立映射关系，就可以通过这种法则，快速找到映射的另一个。

哈希表运用了哈希概念。它把待存储的数据和哈希表中的下标建立映射关系，提到下标，那么存储的容器当然是顺序表，通过数据的值本身就能飞快访问到数据所存储的位置。这种访问是时间复杂度是O(1)。

对于整型数据，整数1可以存在下标为1的位置，其他整数也以此类推。但数量过大的整数或者分布不太密集的整数可能会造成空间的浪费。因此需要有更加好的法则来建立一一映射的关系。

这种法则就是对数据进行初步处理之后，得到一个相应的下标，再把这个数存在相应的下标中。

这种处理数据的哈希函数有很多。处理后的下标可能是两个相同的数，比如哈希函数是原始数据%10，那么1%10==1，101%10==1，那么这两个数看起来似乎都要存在1，数据就会造成覆盖，这时就会造成哈希冲突。当然也可以把函数设置的复杂一点比如加上^&多种运算来建立映射关系。

再好的哈希函数都无法避免哈希冲突，因为数字是无限多的，而顺序表的容量是有限的。我们只能尽量避免哈希冲突。

1.31闭散列哈希表

线性探测解决。

线性探测的思路：如果1%10==1,1放在下标为1的位置，101%10==1，1的位置已经有值了，那么101就往1的后面没有值的位置找。如果2位置是空的，那么101就存在2这里了。但是2的位置被占领以后，如果有102%10==2，那么102就不能存在2的位置，依然要往后找，这样如果哈希冲突的数据比较多，很多数就被迫放在后面，那么查找的时间就消耗多一点，需要一直往后找。

所以一般情况下，不会让这个哈希表太满，数据/容量=0.7左右。这个值也叫负载因子。

后面又有了开散列来解决哈希冲突。

1.32开散列哈希表

它是一个顺序表，每个节点是一个指针，下面挂着的都是指针。相当于这个哈希表是一个指针数组。

如果遇到哈希冲突，就把这个值进行头插。需要找的时候，就在这个链表上找。这个方法一般设置

负载因子为1，在元素数据等于哈希表容量时，就要扩容。这样每个节点下也不会说挂太多值。在好的哈希函数之下，即使有哈希冲突，节点下面挂的节点并不会太多，查找的效率很高，已经可以看作O(1)的时间复杂度了。

二、部分功能模拟实现

本次主要模拟实现开散列的哈希表。

分析：

1.准备四个文件，一个是哈希表的头文件，然后再装迭代器，再装unordered_map和unordered_set，最后放在test.cpp文件里进行测试。

2.主要实现插入，删除，查找和扩容功能。

3.迭代器要实现前置++和后置++等常用功能。

细节很多，可以多了解一下官方的功能，然后再写。

hashtable.h

#pragma once
#include <iostream>
using namespace std;
#include <vector>
#include <string>
#include <assert.h>
#include <utility>

template<class K>
class HashFunc//哈希函数，仿函数，传一个val返回val
{
public:
	size_t operator()(const K& val)
	{
		return val;
	}
};

template<>
class HashFunc<string>//特化，如果是字符串，走这个仿函数
{
public:
	size_t operator()(const string& s)
	{
		const char* str = s.c_str();
		unsigned int seed = 131; // 31 131 1313 13131 131313
		unsigned int hash = 0;
		while (*str)
		{
			hash = hash * seed + (*str++);
		}

		return hash;//把字符串经过一些处理转变为unsigned int，达到映射，减少哈希冲突
	}
};
namespace OpenHash
{
	
	template<class K>
	struct HashBucketNode//哈希桶中的节点
	{
		HashBucketNode(const K& data)
			: _pNext(nullptr), _data(data)
		{}
		HashBucketNode<K>* _pNext;
		K _data;
	};

	template<class K, class T, class KeyOfValue, class HF>
	class HashBucket;

	// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
	//map和set中迭代器是相同的，所以都放到hashtable.h中来实现了
	template <class K, class T, class KeyOfValue, class HF>
	struct HBIterator
	{
		typedef HashBucket<K, T, KeyOfValue, HF> HashBucket;
		typedef HashBucketNode<T>* PNode;
	public:
		typedef HBIterator<K, T, KeyOfValue, HF> Self;

		HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr)//实现一下构造
			:_pNode(pNode)
			,_pHt(pHt)
		{

		}
		Self& operator++()//前置++
		{
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			if (_pNode->_pNext)
			{
				_pNode = _pNode->_pNext;
			}
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1;
				for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
				{
					if (_pNode = _pHt->_table[bucketNo])
						break;
				}
			}

			return *this;
		}
		Self operator++(int)//实现后置++
		{
			Self it = *this;
			if (_pNode->_pNext)
				_pNode = _pNode->_pNext;
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				size_t bucketNo = _pHt->HashFunc(KeyOfValue()(_pNode->_data)) + 1;
				for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
				{
					if (_pNode = _pHt->_table[bucketNo])
						break;
				}
			}

			return it;
		}
		T& operator*()
		{
			return _pNode->_data;
		}
		T* operator->()
		{
			return &_pNode->_data;
		}
		bool operator==(const Self& it) const
		{
			return _pNode == it._pNode;
		}
		bool operator!=(const Self& it) const
		{
			return _pNode != it._pNode;
		}
		PNode _pNode;             // 当前迭代器关联的节点
		HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
	};
	// 本文所实现的哈希桶中key是唯一的
	template<class K, class T, class KeyOfValue, class HF>
	class HashBucket
	{
		//把迭代器列为友元，这样迭代器就可以使用哈希桶中的成员了
		template <class K, class T, class KeyOfValue, class HF>
		friend struct HBIterator;

		typedef HBIterator<K, T, KeyOfValue, HF> iterator;
		typedef HashBucketNode<T> Node;//把节点重命名为Node
		typedef Node* PNode;
		typedef HashBucket< K, T, KeyOfValue, HF> Self;

	public:

		size_t GetNextPrime(const size_t & prime)
		{
			const int PRIMECOUNT = 28;
			static const size_t primeList[PRIMECOUNT] =
			{
				53ul, 97ul, 193ul, 389ul, 769ul,
				1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
				49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
				1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
				50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
				1610612741ul, 3221225473ul, 4294967291ul
			};

			// 获取比prime大那一个素数
			size_t i = 0;
			for (; i < PRIMECOUNT; ++i)
			{
				if (primeList[i] > prime)
					return primeList[i];
			}

			return primeList[PRIMECOUNT-1];
		}
		HashBucket(size_t capacity)
			: _table(GetNextPrime(capacity))
			, _size(0)
		{}
		HashBucket()
			:_table(GetNextPrime(0))
			,_size(0)
		{}
		//添加了迭代器
		iterator begin()
		{
			for (size_t i = 0; i < _table.size();++i)
			{
				if(_table[i])
				{
					return iterator(_table[i], this);
				}
			}
			return end();
		}
		iterator end()
		{
			return iterator(nullptr, this);
		}

		~HashBucket()
		{
			Clear();
		}

		// 哈希桶中的元素不能重复
		//返回的节点从Node*改为pair<iterator,bool>
		pair<iterator,bool> Insert(const T& data)
		{
			CheckCapacity();//检查一下容量，满了扩容
			KeyOfValue kov;
			size_t index  = HashFunc(kov(data));//取data映射的位置
			PNode cur = _table[index];//这个位置的指针
			
			while (cur)//指针不为空
			{
				if (cur->_data == data)
				{
					return { { cur, this }, false };
				}
				cur = cur->_pNext;
			}

			//出来以后，没有返回，说明这里没有重复值
			//插入
			PNode newnode = new Node(data);
			newnode->_pNext = _table[index];
			_table[index] = newnode;
			++_size;
			return { {newnode, this}, true };
		}

		// 删除哈希桶中为data的元素(data不会重复)
		bool Erase(const K& key)
		{
			//1.如果哈希表中没有元素，删除失败
			if (_table.size() == 0)
			{
				return false;
			}
			
			//2.找data的映射值
			KeyOfValue kov;
			size_t index = HashFunc(key);
			PNode cur = _table[index];
			PNode prev = nullptr;

			while (cur)
			{
				if (kov(cur->_data) != key)
				{
					prev = cur;
					cur = cur->_pNext;
				}
				else
				{
					break;
				}
			}
			//找到了
			if (prev)//cur不是头节点
			{
				prev->_pNext = cur->_pNext;
			}
			else
			{
				_table[index] = cur->_pNext;
			}
			delete cur;
			_size--;

			return true;
		}
		iterator Find(const K& key)
		{
			if (_table.size() == 0)
			{
				return iterator(nullptr,this);
			}
			
			KeyOfValue kov;
			size_t index = HashFunc(key);
			index %= _table.size();
			PNode cur = _table[index];
			while (cur)
			{
				if (kov(cur->_data) == key)
				{
					return iterator(cur,this);
				}
				cur = cur->_pNext;
			}
			return iterator(nullptr,this);
		}

		size_t Size()const
		{
			return _size;
		}

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

		void Clear()
		{
			size_t i = 0;
			for (; i < _table.size();++i)
			{
				PNode cur = _table[i];
				while (cur)
				{
					PNode next = cur->_pNext;
					delete cur;
					cur = next;
				}
				_table[i] = nullptr;
			}
			_size = 0;
		}

		size_t BucketCount()const
		{
			return _table.capacity();
		}

		void Swap(Self& ht)
		{
			_table.swap(ht._table);
			swap(_size, ht._size);
		}
 
		 size_t BucketSize(const K& key)
		{
			 return HashFunc(key);
		}

	private:
		size_t HashFunc(const K& data)
		{
			return HF()(data) % _table.capacity();  
		}

		void CheckCapacity()
		{
			if (_size == _table.size())
			{
				size_t newcapacity = GetNextPrime(_table.capacity());
				Self newtable(newcapacity);
				for (size_t i = 0; i < _table.size();++i)
				{
					PNode cur = _table[i];
					while (cur)
					{
						newtable.Insert(cur->_data);
						cur = cur->_pNext;
					}
				}
				Swap(newtable);
			}
		}

	private:
		vector<Node*> _table;
		size_t _size;      // 哈希表中有效元素的个数
	};
}

unordered_map.h

这里typedef 的时候是pair<const K, V>，不是pair<K , V>，请注意。

#pragma once
#include "hashtable.h"


namespace ting
{

    // unordered_map中存储的是pair<K, V>的键值对，K为key的类型，V为value的类型，HF哈希函数类型
    // unordered_map在实现时，只需将hashbucket中的接口重新封装即可
    template<class K, class V, class HF = HashFunc<V>>
    class unordered_map
    {
        // 通过key获取value的操作
        struct mapKeyOfValue
        {
            const K& operator()(const pair<K, V>& kv) 
            {
                return kv.first;
            }
        };
    public:
        typedef typename OpenHash::HBIterator<K, pair<const K, V>, mapKeyOfValue, HF> iterator;
        typedef typename OpenHash::HashBucket<K, pair<const K, V>, mapKeyOfValue, HF>  HT;
        //typedef OpenHash::HBIterator<K, pair<K,V>, KeyOfValue, HF> iterator;
 
        //typename typedef HT::Iterator iterator;
        unordered_map() : _ht()
        {}

        iterator begin() { return _ht.begin(); }
        iterator end() { return _ht.end(); }

        // capacity
        size_t size()const { return _ht.size(); }
        bool empty()const { return _ht.empty(); }

        // Access
        V& operator[](const K& key)
        {
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }
        const V& operator[](const K& key)const
        {
            pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
            return ret.first->second;
        }

        // lookup
        iterator find(const K& key) { return _ht.Find(key); }
        size_t count(const K& key) { return _ht.Count(key); }

        // modify
        pair<iterator, bool> insert(const pair<K,V> value)
        {
            return _ht.Insert(value);
        }

        iterator erase(iterator position)
        {
            return _ht.Erase(position);
        }

        // bucket
        size_t bucket_count() { return _ht.BucketCount(); }
        size_t bucket_size(const K& key) { return _ht.BucketSize(key); }
    private:
        HT _ht;
    };
    void maptest()
    {
        unordered_map<string, string> m;
        m.insert(make_pair("left",""));
        m.insert(make_pair("right",""));
        m.insert(make_pair("medium",""));

        for (auto e : m)
        {
            cout << e.first << endl;
        }
    }
}

unordered_set.h

#pragma once
#include "hashtable.h"


namespace ting
{
	 //unordered_set中存储的是K类型，HF哈希函数类型
	// unordered_set在实现时，只需将hashbucket中的接口重新封装即可
	template<class K, class HF = HashFunc<K>>
	class unordered_set
	{
		
		// 通过key获取value的操作
		struct setKeyOfValue
		{
			const K& operator()(const K& data)
			{
				return data;
			}
		};
		
	public:
		typedef typename OpenHash::HBIterator<K, K, setKeyOfValue, HF> iterator;
		typedef typename OpenHash::HashBucket<K, K, setKeyOfValue, HF> HT;
		unordered_set() : _ht() {}

		
		iterator begin() { return _ht.begin(); }
		iterator end() { return _ht.end(); }
		
		// capacity
		size_t size()const { return _ht.size(); }
		bool empty()const { return _ht.empty(); }
		///
		// lookup
		iterator find(const K& key) { return _ht.Find(key); }
		size_t count(const K& key) { return _ht.Count(key); }
		/
		// modify
		pair<iterator, bool> insert(const K& value)
		{
			return _ht.Insert(value);
		}

		bool erase(const K& key)
		{
			return _ht.Erase(key);
		}
		
		// bucket
		size_t bucket_count() { return _ht.BucketCount(); }
		size_t bucket_size(const K& key) { return _ht.BucketSize(key); }
	private:
		HT _ht;
	};

	void settest()
	{
		unordered_set<int> s1;
		s1.insert(1);
		s1.insert(2);
		s1.insert(3);

		for (auto e : s1)
		{
			cout << e << endl;
		}
		unordered_set<int>::iterator it = s1.find(1);
		it = s1.begin();

		while (it != s1.end())
		{
			cout << *it << endl;
			++it;
		}

	}
}

标签：const,key,cur,C++,哈希,return,及开,size
From： https://blog.csdn.net/2301_79490289/article/details/140228187

相关文章

  • 真的求求点赞+关注+收藏了！！（c++小游戏3）（还有其它的）
    13、球球大作战//奇怪的游戏#include<bits/stdc++.h>#include<windows.h>#include<conio.h>usingnamespacestd;voidpass(){CONSOLE_CURSOR_INFOcursor_info={1,0};SetConsoleCursorInfo(GetStdHandle(STD_OUTPUT_HANDLE),&cursor_info);}intjj......
  • Linux C++ 059-设计模式之备忘录模式
    LinuxC++059-设计模式之备忘录模式本节关键字：Linux、C++、设计模式、备忘录模式相关库函数：概念备忘录模式（MementoPattern），又叫做快照模式（SnapshotPattern）或Token模式，是GoF的23种设计模式之一，属于行为模式。定义(源于GoF《设计模式》)：在不破坏封闭的前提下，捕获一个......
  • Linux C++ 060-设计模式之单例模式
    LinuxC++060-设计模式之单例模式本节关键字：Linux、C++、设计模式、单例模式相关库函数：概念单例模式是设计模式中最简单的形式之一。这一模式的目的是使得类的一个对象成为系统中的唯一实例。要实现这一点，可以从客户端对其进行实例化开始。因此需要用一种只允许生成对......
  • C++ 基础 - 3 - 数据类型
    简言什么是数据类型？数据类型（DataTypes）是变量或函数返回值的属性，它们决定了变量可以存储哪种类型的数据，以及这些数据如何被解释和存储在计算机的内存中。C++是一种静态类型语言，这意味着每个变量都必须在使用前声明其类型。C++提供了丰富的数据类型，可以分为几大类：基本......
  • C++ 基础 - 2 - 变量常量
    简言什么是变量与常量在计算机编程中，变量是存储数据的一种容器。它可以用于存储各种类型的数据，如整数、浮点数、字符串等。变量的值可以随时改变。常量与变量相反，常量是一个固定的值，它在程序运行期间是不会改变的。常量在程序中起到类似变量的作用，但其值是固定的，不能被......
  • 万能的哈希
    本章节将介绍哈希如何实现KMP与manacher。KMP我们对于文本串\(s\)和模式串\(t\)，先用一个数组\(has_i\)表示\(s\)中前\(i\)位的哈希值，用\(hat\)表示\(t\)的哈希值。然后遍历\(s\)，计算以第\(i\)位为起点的长度为\(|t|\)的区间的哈希值，与\(hat\)比较，累加......
  • C++学习第一天
    CPP的学习day11.VisualStudio的学习安装跳过……1.创建项目选择创建新项目因为是学习，选择第二个控制台应用分配好后点击创建等一会儿就创建好了……先修改设置：右击选择属性然后改为如下图2.CPP的表达式概念表达式就是运算符和操作数的序列，指定一项计算，表达式的求......
  • c++中结构体与类的区别
    在C++中，结构体（struct）与类（class）在功能上非常相似，实际上他们之间的主要区别在于默认的访问权限和继承方式。下面详细解释这两种类型的区别：结构体与类最大的不同就在于访问权限默认访问权限结构体(struct)：默认的成员访问权限是公开的（public）。这意味着，除非显式地指定访问......
  • C++竞赛优化技巧与考场实用技巧
    在洛谷观看更加简约哦~：一键直达距离2024CSP/NOIP已经不远了，在这里，我便分享一下我总结出来的竞赛优化技巧时间优化算法/数据结构优化在处理一些问题，我们可以采用更高效的算法/数据结构来代替低效的算法/数据结构。例如，你需要多次求一段区间的和时，一般会采用循环直接......
  • 2024年华为OD机试真题-图像物体的边界-C++-OD统一考试（C卷D卷）
     2024年OD统一考试（D卷）完整题库：华为OD机试2024年最新题库（Python、JAVA、C++合集）题目描述：给定一个二维数组M行N列，二维数组里的数字代表图片的像素，为了简化问题，仅包含像素1和5两种像素，每种像素代表一个物体，2个物体相邻的格子为边界，求像素1代表的物体的边界个数。像素1代表的......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99