C++：哈希表特性及开散列哈希表的模拟实现
目录
1.22 iterator find(const K& key)
一、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;
}
}
}原文地址：https://blog.csdn.net/2301_79490289/article/details/140228187
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！