unorderedset和unorderedmap结构和封装
- 一.哈希表：
- 1.直接定址法：
- 2.闭散列的开放定址法：
- 1.基本结构：
- 2.insert
- 3.find
- 4.erase
- 5.补充：
- 6.pair<k,v> k的数据类型：
- 3.开散列的拉链法/哈希桶：
- 1.基本结构：
- 2.insert
- 1.正常插入：
- 2.考虑扩容
- 3.find
- 4.erase
- 5.数据计算观察：
- 二.unordered_set和unordered_map的封装：
- 1.unordered_set
- 1.基本结构：
- 2.插入：
- 3.迭代器：
- 4.find
- 5.整体代码：
- 2.unorder_map
- 1.基本结构：
- 2.插入：
- 3.迭代器：
- 4.find
- 5.operator[]重载：
- 6.整体代码：
- 7.补充代码：
- 3.HashTable
- 1.find查找：
- 2.迭代器：
- 1.基本结构：
- 2.operator++
- 3.整体代码：
- 3.插入：
- 1.bool返回的插入：
- 2.重载operator[]实现的重载unordered_map独有：
一.哈希表：
1.直接定址法：
1.数据比较集中并且数据都比较小。
2.使用key值作为下标进行数据的存贮。
3.适用于数据比较小并且连续的情况。
字符串中第一个唯一字符
2.闭散列的开放定址法：
1.基本结构：
namespace oper_addres {
enum state {
Empty,
Delete,
Exist,
};
template<class k, class v>
struct Hash_Node {
Hash_Node(pair<k, v> x = pair<k,v>())
:_date(x)
,_state(Empty)
{}
pair<k, v> _date;
state _state;
};
template<class k, class v>
class Hash {
public:
Hash(size_t n = 10)
{
_hash.resize(n);
}
private:
vector<Hash_Node<k, v>> _hash;
size_t _num = 0;
};
}
2.insert
1.不存在重复数据：除留余数法，1%10==1 下标1位置放置数值1，4%10=4 下标4位置放置数值4，以此类推。
2.存在重复数据->线性探测->7%10=7 ,下标7位置放置数值7，17%10=7 下标7位置有值就向后放置下标8就放置17，27%10=7下标7位置有值 下标8位置有值下标9放置，++然后取模找到可以放置值的位置结束。
3.如何确定这个位置的值情况？
提供枚举常量 ：Empty Delete Exist
4.扩容+数值拷贝：每插入一个值都需要计算负载因子 = 当前插入的数据量/可以插入的size 当这个差值>=0.7就需要进行扩容，新建一个newhashtable大小为当前表的两倍，新的表使用insert插入原来哈希表数据最后交换两个哈希表的vector。
bool insert(pair<k, v> x)
{
//扩容：
size_t tmp = ((_num * 10) / _hash.size());
if (tmp >= 7)
{
Hash<k, v>* newhash = new Hash<k, v>(_hash.size() * 2);
for (auto e : _hash)
{
newhash->insert(e._date);
}
_hash.swap(newhash->_hash);
}
//1.正常插入：插入位置
size_t indx = x.first % _hash.size();
//2.进行插入：
if ((_hash[indx]._state) != Empty || (_hash[indx]._state) == Delete)
{
//向后查找->线性探测：
while (_hash[indx]._state == Exist)
{
indx++;
indx %= _hash.size();
}
_hash[indx]._date = x;
_hash[indx]._state = Exist;
_num++;
return true;
}
_hash[indx]._date = x;
_hash[indx]._state = Exist;
_num++;
return true;
}
3.find
1.find数据传参查找的数据并且返回数据的下标。
2.数据%hashtable.size(),对应下标位置就是这个值返回下标，如果不是线性探测直到空为止。数据不存在返回-1.
int find(const k& fd)
{
size_t Hashi = fd % _hash.size();
if (_hash[Hashi]._state == Exist && _hash[Hashi]._date.first == fd)
{
return Hashi;
}
else
{
while (_hash[Hashi]._date.first != fd && _hash[Hashi]._state != Empty)
{
Hashi++;
Hashi %= _hash.size();
}
if (_hash[Hashi]._date.first == fd && _hash[Hashi]._state == Exist)
return Hashi;
else
return -1;
}
}
4.erase
1.这个地方首先使用find找到对应的下标位置进行返回。
2.找到就修改这个位置的状态为Delete，并且返回true。
bool erase(const k& fd)
{
int hashi = find(fd);
if (hashi != -1)
{
_hash[hashi]._state = Delete;
return true;
}
return false;
}
5.补充：
size_t size()
{
return _num;
}
bool empty()
{
if (_num == 0)
return true;
return false;
}
1.哈希冲突？
2.数据%hashtable.size()同一个位置的数据然后进行线性探测，线性探测的次数越多哈希冲突越多。哈希冲突越多，效率就越低。
3.当因子大于0.7就考虑进行扩容。
6.pair<k,v> k的数据类型：
1.数据类型的一个转换考虑如何变成下标可以识别的size_t类型。
2.实现仿函数，并且重载operator()
3.特殊类型可以使用类模板的特化。
template<class T>
struct transition
{
size_t operator()(const T& x)
{
return x;
}
};
//1.string -> string
template<>
struct transition<string>
{
size_t operator()(const string& x)
{
//1.可以计算string字符串的asia码的和并且每次*131降低哈希冲突：
size_t sum = 0;
for (auto& e : x)
{
sum += (e*131);
}
return sum;
}
};
3.开散列的拉链法/哈希桶：
1.开散列,首先对于key值计算出下标位置，具有相同下标位置的值放在同一个子集里面，每一个子集就是一个桶，每一个桶中的元素通过一个单链表连接在一起，每一个链表的头节点由vector保存
1.基本结构：
namespace Hash_bucket{
template<class T>
struct transition
{
size_t operator()(const T& x)
{
return x;
}
};
//1.string -> string
template<>
struct transition<string>
{
size_t operator()(const string& x)
{
//1.可以计算string字符串的asia码的和并且每次*131降低哈希冲突：
size_t sum = 0;
for (auto& e : x)
{
sum += (e * 131);
}
return sum;
}
};
template<class k, class v>
struct Hash_Node {
typedef Hash_Node Node;
Hash_Node(pair<k, v> x = pair<k, v>())
:_date(x)
,_next(nullptr)
{}
pair<k, v> _date;
Node* _next;
};
//, class trans = transition<k>
template<class k, class v, class trans = transition<k>>
class Hash {
public:
typedef Hash_Node<k, v> Node;
Hash(size_t n = 10)
{
_hash.resize(n,nullptr);
_num = 0;
}
private:
vector<Node*> _hash;
size_t _num;
};
}
2.insert
1.正常插入：
bool insert(const pair<k, v>& x)
{
//1.正常插入：
trans kot;
size_t hashi = kot(x.first) % _hash.size();
Node* newnode = new Node(x);
//1-1:_hash[hashi]==nullptr 直接插入节点：
if (_hash[hashi] == nullptr)
{
_hash[hashi] = newnode;
_num++;
return true;
}
//1-2：_hash[hashi]!=nullptr 进行单链表的头插：
else
{
newnode->_next = _hash[hashi];
_hash[hashi] = newnode;
_num++;
return true;
}
return false;
}
2.考虑扩容
1,什么时候需要取进行扩容？
2.当我们的vector<Node*> _hash;每一个下标处都有非空节点就进行扩容。
3.扩容需要考虑原来链表中保存的节点并且考虑进行重新的插入数据。
4.节点数据不需要先delete后new，直接进行简单连接的转移。
5.开头使用find可以帮助我们判断要插入的这个节点之前存不存在。
bool insert(const pair<k, v>& x)
{
if (find(x.first))
return false;
trans kot;
//1.计算平衡因子：
if (_num == _hash.size())
{
vector<Node*> newhash(_hash.size() * 2, nullptr);
for(int i=0;i<_hash.size();i++)
{
Node* cur = _hash[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = kot(cur->_date.first) % (_hash.size()*2);
cur->_next = newhash[hashi];
newhash[hashi] = cur;
cur = next;
}
_hash[i] = nullptr;
}
_hash.swap(newhash);
}
else
{
//1.正常插入
size_t hashi = kot(x.first) % _hash.size();
Node* newnode = new Node(x);
//1-1:_hash[hashi]==nullptr 直接插入节点：
newnode->_next = _hash[hashi];
_hash[hashi] = newnode;
_num++;
return true;
}
return false;
}
3.find
1.%_hash.size()快速确定下标位置。
2.通过cur遍历单链表找到值相同的节点就返回。
3.找不到就返回空节点。
Node* find(const k& fd)
{
trans kot;
size_t i = kot(fd) % _hash.size();
Node* cur = _hash[i];
while (cur)
{
if (cur->_date.first == fd)
return cur;
cur = cur->_next;
}
return nullptr;
}
4.erase
1.%_hash.size()快速确定下标位置。
2.两个情况：
2-1：_hash[hashi]保存的就是需要删除的节点
2-1：需要删除的节点在单链表中。
bool erase(const k& fd)
{
trans kot;
size_t i = kot(fd) % _hash.size();
Node* cur = _hash[i];
Node* prev = nullptr;
while (cur)
{
if (cur->_date.first == fd)
{
//头节点就是需要删除的
if (prev == nullptr)
{
_hash[i] = cur->_next;
}
//在单链表中的节点需要被删除：
else
{
prev->_next = cur->_next;
}
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
5.数据计算观察：
void Some()
{
size_t bucketSize = 0;
size_t maxBucketLen = 0;
size_t sum = 0;
double averageBucketLen = 0;
for (size_t i = 0; i < _hash.size(); i++)
{
Node* cur = _hash[i];
if (cur)
{
++bucketSize;
}
size_t bucketLen = 0;
while (cur)
{
++bucketLen;
cur = cur->_next;
}
sum += bucketLen;
if (bucketLen > maxBucketLen)
{
maxBucketLen = bucketLen;
}
}
averageBucketLen = (double)sum / (double)bucketSize;
//平衡因子
printf("load factor:%lf\n", (double)_num / _hash.size());
//表长度：
printf("all bucketSize:%d\n",_hash.size());
//桶的个数：
printf("bucketSize:%d\n", bucketSize);
//最长的桶的长度
printf("maxBucketLen:%d\n", maxBucketLen);
//平均桶长度
printf("averageBucketLen:%lf\n\n", averageBucketLen);
}
二.unordered_set和unordered_map的封装：
1.unordered_set
1.基本结构：
namespace sfpy {
template<class k,class transition = transition<k>>
class myunset {
public:
struct copy_set {
const k& operator()(const k& x)
{
return x;
}
};
private:
Hash_bucket::Hash<k,k,copy_set,transition> _t;
};
}
2.插入：
//1.插入：
bool Insert(const k& x)
{
pair<iterator, bool> ret = _t.Insert(x);
return ret.second;
}
bool insert(const k& x)
{
return _t.insert(x);
}
3.迭代器：
typedef typename Hash_bucket::Hash<k, k, copy_set, transition>::_iterator iterator;
iterator begin()
{
return _t.find_begin();
}
iterator end()
{
return nullptr;
}
4.find
//3.find()
iterator _find(const k& x)
{
return _t.Find(x);
}
5.整体代码：
namespace sfpy {
template<class k,class transition = transition<k>>
class myunset {
public:
struct copy_set {
const k& operator()(const k& x)
{
return x;
}
};
typedef typename Hash_bucket::Hash<k, k, copy_set, transition>::_iterator iterator;
//1.插入：
bool Insert(const k& x)
{
pair<iterator, bool> ret = _t.Insert(x);
return ret.second;
}
bool insert(const k& x)
{
return _t.insert(x);
}
//2.迭代器：
iterator begin()
{
return _t.find_begin();
}
iterator end()
{
return nullptr;
}
//3.find()
iterator _find(const k& x)
{
return _t.Find(x);
}
private:
Hash_bucket::Hash<k,k,copy_set,transition> _t;
};
}
2.unorder_map
1.基本结构：
namespace sfpy {
template<class k , class v , class transition = transition<k>>
class myunmap {
public:
struct copy_map{
const k& operator()(const pair<k,v>& x)
{
return x.first;
}
};
private:
Hash_bucket::Hash<k,pair<k,v>, copy_map , transition> _t;
};
}
2.插入：
//1.插入：
bool Insert(const pair<k, v> x)
{
pair<iterator, bool> ret = _t.Insert(x);
return ret.second;
}
bool insert(const pair<k, v> x)
{
return _t.insert(x);
}
3.迭代器：
typedef typename Hash_bucket::Hash<k, pair<k, v>, copy_map, transition>::_iterator iterator;
//2.迭代器
iterator begin()
{
return _t.find_begin();
}
iterator end()
{
return _t.find_end();
}
4.find
iterator _find(const k& x)
{
return _t.Find(x);
}
5.operator[]重载：
v& operator[](const k& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key,v()));
return ret.first->second;
}
6.整体代码：
namespace sfpy {
template<class k , class v , class transition = transition<k>>
class myunmap {
public:
struct copy_map{
const k& operator()(const pair<k,v>& x)
{
return x.first;
}
};
typedef typename Hash_bucket::Hash<k, pair<k, v>, copy_map, transition>::_iterator iterator;
//1.插入：
bool Insert(const pair<k, v> x)
{
pair<iterator, bool> ret = _t.Insert(x);
return ret.second;
}
bool insert(const pair<k, v> x)
{
return _t.insert(x);
}
//2.迭代器
iterator begin()
{
return _t.find_begin();
}
iterator end()
{
return _t.find_end();
}
//3.find()
iterator _find(const k& x)
{
return _t.Find(x);
}
v& operator[](const k& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key,v()));
return ret.first->second;
}
private:
Hash_bucket::Hash<k,pair<k,v>, copy_map , transition> _t;
};
}
7.补充代码：
1.我们知道在unordered_set和unordered_map中key值是不可以被修改的。
2.我们上面的代码是可以修改key值就是一个比较离谱的事情。
3.封装unordered_map和unordered_set对key的类型进行加const。
namespace sfpy {
template<class k , class v , class transition = transition<k>>
class myunmap {
public:
struct copy_map{
const k& operator()(const pair<const k,v>& x)
{
return x.first;
}
};
typedef typename Hash_bucket::Hash<k, pair<const k, v>, copy_map, transition>::_iterator iterator;
//1.插入：
bool Insert(const pair<const k, v> x)
{
pair<iterator, bool> ret = _t.Insert(x);
return ret.second;
}
bool insert(const pair<const k, v> x)
{
return _t.insert(x);
}
//2.迭代器
iterator begin()
{
return _t.find_begin();
}
iterator end()
{
return _t.find_end();
}
//3.find()
iterator _find(const k& x)
{
return _t.Find(x);
}
v& operator[](const k& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key,v()));
return ret.first->second;
}
private:
Hash_bucket::Hash<k,pair<const k, v>, copy_map , transition> _t;
};
}
3.HashTable
1.map和set去封装同一个哈希表。
2.模板：template<class k , class T, class copy, class trans>
3.copy类重载了operator()做键值的获取。
4.trans是一个类型转换，比如说string转化为一个size_t类型方便下标的使用。
1.find查找：
1.返回查找到的数据的节点或者空指针。
2.数据计算下表并且遍历单链表找到节点返回节点指针。
3.找不到节点就返回nullptr
Node* find(const k& fd)
{
trans up;
copy kot;
size_t i = up(fd) % _hash.size();
Node* cur = _hash[i];
while (cur)
{
if ((up(kot(cur->_date))) == up(fd))
return cur;
cur = cur->_next;
}
return nullptr;
}
2.迭代器：
1.基本结构：
1.迭代器肯定需要封装数据的节点。
2.封装数据的节点够吗？不够！
3.只封装数据的节点重载++在一个单链表的数据还可以，但是进行链表的跳转就无法实现了。
4.考虑封装一个哈希表到迭代器中。
5.迭代器和哈希表会相互封装(上面的类找不到下面的)—>模板+声明放到上面的那个类的上面。
struct unorderediterator
{
typedef Hash_Node<T> Node;
typedef Hash<k, T, copy, trans> HT;
typedef unorderediterator<k, T, copy, trans> self;
HT* _Hash;
Node* _node;
unorderediterator(HT* hash, Node* x)
:_Hash(hash)
, _node(x)
{}
};
2.operator++
1,情况一：当前节点的下一个不是空直接修改迭代器中节点的内容_node = cur->next
2.情况二：当前节点的下一个是空，求当前单链表所在节点的哈希下表使用节点访问数据进行计算，找到下标之后哈希表向后进行遍历。
2-1：找到一个不是空的就进行_node的修改。
2-2：找不到，表示哈希表一直向后进行遍历到结尾都是空指针。
//主要是要去找节点：
self operator++()
{
trans kot;
copy up;
//1.情况一：当前节点有下一个节点：
if (_node->_next != nullptr)
_node = _node->_next;
//2.哈希位置的跳转：
else
{
size_t hashi = kot(up(_node->_date)) % _Hash->_hash.size();
hashi++;
while (hashi < _Hash->_hash.size())
{
if (_Hash->_hash[hashi])
{
_node = _Hash->_hash[hashi];
break;
}
hashi++;
}
if (hashi == _Hash->_hash.size())
_node = nullptr;
}
return *this;
}
3.整体代码：
//迭代器：
template<class k, class T, class copy, class trans>
struct unorderediterator
{
typedef Hash_Node<T> Node;
typedef Hash<k, T, copy, trans> HT;
typedef unorderediterator<k, T, copy, trans> self;
HT* _Hash;
Node* _node;
unorderediterator(HT* hash, Node* x)
:_Hash(hash)
, _node(x)
{}
T& operator*()
{
return _node->_date;
}
T* operator->()
{
return &(_node->_date);
}
bool operator!=(const self& bitter)//self* bitter
{
//比较哈希表中的vector不是iterator？
//迭代器==哈希+节点 比较迭代器的地址还是节点的地址？
if (this->_node == bitter._node)
return false;
return true;
}
//主要是要去找节点：
self operator++()
{
trans kot;
copy up;
//1.情况一：当前节点有下一个节点：
if (_node->_next != nullptr)
_node = _node->_next;
//2.哈希位置的跳转：
else
{
size_t hashi = kot(up(_node->_date)) % _Hash->_hash.size();
hashi++;
while (hashi < _Hash->_hash.size())
{
if (_Hash->_hash[hashi])
{
_node = _Hash->_hash[hashi];
break;
}
hashi++;
}
if (hashi == _Hash->_hash.size())
_node = nullptr;
}
return *this;
}
};
3.插入：
1.bool返回的插入：
1.正常插入：通过key计算下标值。
2.当前Hash[hashi]中已经有数据进行头插操作。
3.当前Hash[hashi]中没有有数据就修改hash[hashi]值。
4.负载因子到1就需要进行扩容操作，负载因子=单链表个数/hash.size()
5.创建一个新的大小为当前哈希表的两倍，遍历原来的链表有key求下标的方法重新进行原来数据的移动，节约了时间，结尾和_node进行哈希表的交换。
bool insert(const T& x)
{
copy kot;
trans up;
//1.调find函数去查一下当前要插入的数据是否已经存在
if (find(kot(x)))
return false;
//1.计算平衡因子：
if (_num == _hash.size())
{
vector<Node*> newhash(_hash.size() * 2, nullptr);
for (int i = 0; i < _hash.size(); i++)
{
Node* cur = _hash[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = up(kot(cur->_date)) % (_hash.size() * 2);
cur->_next = newhash[hashi];
newhash[hashi] = cur;
cur = next;
}
_hash[i] = nullptr;
}
_hash.swap(newhash);
}
else
{
//1.正常插入
size_t hashi = up(kot(x)) % _hash.size();
Node* newnode = new Node(x);
//1-1:_hash[hashi]==nullptr 直接插入节点：
newnode->_next = _hash[hashi];
_hash[hashi] = newnode;
_num++;
return true;
}
return false;
}
Node* find(const k& fd)
{
trans up;
copy kot;
size_t i = up(fd) % _hash.size();
Node* cur = _hash[i];
while (cur)
{
if ((up(kot(cur->_date))) == up(fd))
return cur;
cur = cur->_next;
}
return nullptr;
}
2.重载operator[]实现的重载unordered_map独有：
1,重载operator[]一定需要pair<iterator,bool>的插入返回。
2.operator[]不存在就插入，存在就返回value的引用可以进行修改。
3.ret.second 为false表示已经插入过对应的key值。
4.ret.second 为true表示没有插入过对应的key值这一次刚刚插入数据。
5.优化了一个find的查找返回迭代器类型的数据方便pair<iterator,bool>返回。
pair <_iterator, bool> Insert(const T& x)
{
copy kot;
trans up;
//1.调find函数去查一下当前要插入的数据是否已经存在
if (Find(kot(x))._node)
return make_pair(Find(kot(x)),false);
//1.计算平衡因子：
if (_num == _hash.size())
{
vector<Node*> newhash(_hash.size() * 2, nullptr);
for (int i = 0; i < _hash.size(); i++)
{
Node* cur = _hash[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = up(kot(cur->_date)) % (_hash.size() * 2);
cur->_next = newhash[hashi];
newhash[hashi] = cur;
cur = next;
}
_hash[i] = nullptr;
}
_hash.swap(newhash);
}
else
{
//1.正常插入
size_t hashi = up(kot(x)) % _hash.size();
Node* newnode = new Node(x);
//1-1:_hash[hashi]==nullptr 直接插入节点：
newnode->_next = _hash[hashi];
_hash[hashi] = newnode;
_num++;
return make_pair(_iterator(this,newnode), true);
}
return make_pair(_iterator(this,nullptr),false);
}
_iterator Find(const k& fd)
{
trans up;
copy kot;
size_t i = up(fd) % _hash.size();
Node* cur = _hash[i];
while (cur)
{
if ((up(kot(cur->_date))) == up(fd))
return _iterator(this, cur);
cur = cur->_next;
}
return _iterator(this,nullptr);
}
#pragma once
#include<iostream>
#include<string>
#include<vector>
using namespace std;
template<class T>
struct transition
{
size_t operator()(const T& x)
{
return x;
}
};
//1.string -> string
template<>
struct transition<string>
{
size_t operator()(const string& x)
{
//1.可以计算string字符串的asia码的和并且每次*131降低哈希冲突：
size_t sum = 0;
for (auto& e : x)
{
sum += (e * 131);
}
return sum;
}
};
namespace Hash_bucket
{
template<class T>
struct Hash_Node {
typedef Hash_Node Node;
Hash_Node(T x = T())
:_date(x)
,_next(nullptr)
{}
T _date;
Node* _next;
};
//T() ---> int
//T() ---> pair<int,int> pair类型：
//哈希表和迭代器相互包含需要声明迭代器到哈希表的前面：
//类模板的声明需要模板+struct/class + 类名：
template<class k, class T, class copy, class trans>
struct unorderediterator;
template<class k , class T, class copy, class trans>
class Hash {
template<class K, class T, class copy, class Hash>
friend struct unorderediterator;
public:
typedef Hash_Node<T> Node;
typedef unorderediterator<k, T, copy, trans> _iterator;
Hash(size_t n = 10)
{
_hash.resize(n,nullptr);
_num = 0;
}
pair <_iterator, bool> Insert(const T& x)
{
copy kot;
trans up;
//1.调find函数去查一下当前要插入的数据是否已经存在
if (Find(kot(x))._node)
return make_pair(Find(kot(x)),false);
//1.计算平衡因子：
if (_num == _hash.size())
{
vector<Node*> newhash(_hash.size() * 2, nullptr);
for (int i = 0; i < _hash.size(); i++)
{
Node* cur = _hash[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = up(kot(cur->_date)) % (_hash.size() * 2);
cur->_next = newhash[hashi];
newhash[hashi] = cur;
cur = next;
}
_hash[i] = nullptr;
}
_hash.swap(newhash);
}
else
{
//1.正常插入
size_t hashi = up(kot(x)) % _hash.size();
Node* newnode = new Node(x);
//1-1:_hash[hashi]==nullptr 直接插入节点：
newnode->_next = _hash[hashi];
_hash[hashi] = newnode;
_num++;
return make_pair(_iterator(this,newnode), true);
}
return make_pair(_iterator(this,nullptr),false);
}
_iterator Find(const k& fd)
{
trans up;
copy kot;
size_t i = up(fd) % _hash.size();
Node* cur = _hash[i];
while (cur)
{
if ((up(kot(cur->_date))) == up(fd))
return _iterator(this, cur);
cur = cur->_next;
}
return _iterator(this,nullptr);
}
bool insert(const T& x)
{
copy kot;
trans up;
//1.调find函数去查一下当前要插入的数据是否已经存在
if (find(kot(x)))
return false;
//1.计算平衡因子：
if (_num == _hash.size())
{
vector<Node*> newhash(_hash.size() * 2, nullptr);
for (int i = 0; i < _hash.size(); i++)
{
Node* cur = _hash[i];
while (cur)
{
Node* next = cur->_next;
// 头插到新表
size_t hashi = up(kot(cur->_date)) % (_hash.size() * 2);
cur->_next = newhash[hashi];
newhash[hashi] = cur;
cur = next;
}
_hash[i] = nullptr;
}
_hash.swap(newhash);
}
else
{
//1.正常插入
size_t hashi = up(kot(x)) % _hash.size();
Node* newnode = new Node(x);
//1-1:_hash[hashi]==nullptr 直接插入节点：
newnode->_next = _hash[hashi];
_hash[hashi] = newnode;
_num++;
return true;
}
return false;
}
Node* find(const k& fd)
{
trans up;
copy kot;
size_t i = up(fd) % _hash.size();
Node* cur = _hash[i];
while (cur)
{
if ((up(kot(cur->_date))) == up(fd))
return cur;
cur = cur->_next;
}
return nullptr;
}
bool erase(const T& fd)
{
trans kot;
copy up;
size_t i = kot(up(fd)) % _hash.size();
Node* cur = _hash[i];
Node* prev = nullptr;
while (cur)
{
if (up(cur->_date) == fd)
{
if (prev == nullptr)
{
_hash[i] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
void Some()
{
size_t bucketSize = 0;
size_t maxBucketLen = 0;
size_t sum = 0;
double averageBucketLen = 0;
for (size_t i = 0; i < _hash.size(); i++)
{
Node* cur = _hash[i];
if (cur)
{
++bucketSize;
}
size_t bucketLen = 0;
while (cur)
{
++bucketLen;
cur = cur->_next;
}
sum += bucketLen;
if (bucketLen > maxBucketLen)
{
maxBucketLen = bucketLen;
}
}
averageBucketLen = (double)sum / (double)bucketSize;
//平衡因子
printf("load factor:%lf\n", (double)_num / _hash.size());
//表长度：
printf("all bucketSize:%d\n",_hash.size());
//桶的个数：
printf("bucketSize:%d\n", bucketSize);
//最长的桶的长度
printf("maxBucketLen:%d\n", maxBucketLen);
//平均桶长度
printf("averageBucketLen:%lf\n\n", averageBucketLen);
}
//找开始的节点：
_iterator find_begin()
{
for (int i = 0; i < _hash.size(); i++)
{
if (_hash[i])
{
return _iterator(this, _hash[i]);
}
}
return _iterator(this, nullptr);
}
_iterator find_end()
{
return _iterator(this, nullptr);
}
private:
//指针数组：
vector<Node*> _hash;
size_t _num;
};
//迭代器：
template<class k, class T, class copy, class trans>
struct unorderediterator
{
typedef Hash_Node<T> Node;
typedef Hash<k, T, copy, trans> HT;
typedef unorderediterator<k, T, copy, trans> self;
HT* _Hash;
Node* _node;
unorderediterator(HT* hash, Node* x)
:_Hash(hash)
, _node(x)
{}
T& operator*()
{
return _node->_date;
}
T* operator->()
{
return &(_node->_date);
}
bool operator!=(const self& bitter)//self* bitter
{
//比较哈希表中的vector不是iterator？
//迭代器==哈希+节点 比较迭代器的地址还是节点的地址？
if (this->_node == bitter._node)
return false;
return true;
}
//主要是要去找节点：
self operator++()
{
trans kot;
copy up;
//1.情况一：当前节点有下一个节点：
if (_node->_next != nullptr)
_node = _node->_next;
//2.哈希位置的跳转：
else
{
size_t hashi = kot(up(_node->_date)) % _Hash->_hash.size();
hashi++;
while (hashi < _Hash->_hash.size())
{
if (_Hash->_hash[hashi])
{
_node = _Hash->_hash[hashi];
break;
}
hashi++;
}
if (hashi == _Hash->_hash.size())
_node = nullptr;
}
return *this;
}
};
}
