Lenyiin/unordered-set-map
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
master
unordered-set-map/Windows_Unordered_Set_Map/HashTable.hpp

685 lines
20 KiB
C++
Raw Permalink Normal View History

博客 https://blog.lenyiin.com/unordered-set-map/ 的代码仓库
2024-09-28 02:21:54 +08:00
#pragma once
#include <iostream>
#include <vector>
#include <string>
// unordered_set<K> -> HashTable<K, K>
// unordered_map<K, V> -> HashTable<K, pair<K, V>>
namespace Lenyiin
{
template <class K>
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
enum State
{
EMPTY, // <20><>λΪ<CEBB><CEAA>
EXIST, // <20><>λ<EFBFBD>Ѿ<EFBFBD><D1BE><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>Ԫ<EFBFBD><D4AA>
DELETE // <20><>λ<EFBFBD><CEBB>Ԫ<EFBFBD>ر<EFBFBD>ɾ<EFBFBD><C9BE>
};
template <class T>
struct HashData
{
T _data;
State _state;
HashData()
: _data(T()), _state(EMPTY)
{
}
};
template <class K, class T, class KeyOfT>
class Close_HashTable
{
private:
typedef struct HashData<T> HashData;
size_t SecondHash(const K& key, size_t table_size)
{
return 1 + (key % (table_size - 1));
}
public:
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD> = <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>/<2F><><EFBFBD>Ĵ<EFBFBD>С <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ϣ<EFBFBD><CFA3><EFBFBD><EFBFBD><EFBFBD>ij̶<C4B3>
// <20><>Խ<EFBFBD>ӽ<EFBFBD><D3BD><EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Խ<EFBFBD><D4BD><EFBFBD>׳<EFBFBD>ͻ, <20><>ͻԽ<CDBB><D4BD>, Ч<><D0A7>Խ<EFBFBD><D4BD>
// <20><>ϣ<EFBFBD><CFA3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>˲<EFBFBD><CBB2><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD>Ŷ<EFBFBD><C5B6>Ʒ<EFBFBD><C6B7><EFBFBD>, һ<>㸺<EFBFBD><E3B8BA><EFBFBD><EFBFBD><EFBFBD>ӵ<EFBFBD> 0.7 <20><><EFBFBD>ҾͿ<D2BE>ʼ<EFBFBD><CABC><EFBFBD><EFBFBD>
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԽС, <20><>ͻ<EFBFBD><CDBB><EFBFBD><EFBFBD>Խ<EFBFBD><D4BD>, <20><><EFBFBD><EFBFBD>Ч<EFBFBD><D0A7>Խ<EFBFBD><D4BD>, <20><><EFBFBD>Ǹ<EFBFBD><C7B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ԽС, <20>˷ѵĿռ<C4BF>Խ<EFBFBD><D4BD>, <20><><EFBFBD>Ը<EFBFBD><D4B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>ȡһ<C8A1><D2BB><EFBFBD><EFBFBD><EFBFBD>е<EFBFBD>ֵ
void CheckCapacity()
{
KeyOfT koft;
// // version 1
// if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
// {
// // <20><><EFBFBD><EFBFBD>
// // 1. <20><> 2<><32><EFBFBD><EFBFBD>С<EFBFBD><D0A1><EFBFBD>±<EFBFBD>
// // 2. <20><><EFBFBD><EFBFBD><EFBFBD>ɱ<EFBFBD><C9B1><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݣ<EFBFBD><DDA3><EFBFBD><EFBFBD>¼<EFBFBD><C2BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±<EFBFBD><C2B1><EFBFBD>λ<EFBFBD><CEBB>
// // 3. <20>ͷžɱ<C5BE>
// std::vector<HashData> newtables;
// size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
// newtables.resize(newsize);
// for (size_t i = 0; i < _tables.size(); i++)
// {
// if (_tables[i]._state == EXIST)
// {
// // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±<EFBFBD><C2B1>е<EFBFBD>λ<EFBFBD><CEBB>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͻ
// size_t index = koft(_tables[i]._data) % newtables.size();
// while (newtables[index]._state == EXIST)
// {
// ++index;
// if (index == _tables.size())
// {
// index = 0;
// }
// }
// newtables[index] = _tables[i];
// }
// }
// _tables.swap(newtables);
// }
// // version 2
// if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
// {
// // <20><><EFBFBD><EFBFBD>
// // 1. <20><> 2<><32><EFBFBD><EFBFBD>С<EFBFBD><D0A1><EFBFBD>±<EFBFBD>
// // 2. <20><><EFBFBD><EFBFBD><EFBFBD>ɱ<EFBFBD><C9B1><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݣ<EFBFBD><DDA3><EFBFBD><EFBFBD>¼<EFBFBD><C2BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±<EFBFBD><C2B1><EFBFBD>λ<EFBFBD><CEBB>
// // 3. <20>ͷžɱ<C5BE>
// std::vector<HashData> newtables;
// size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
// newtables.resize(newsize);
// for (size_t i = 0; i < _tables.size(); i++)
// {
// if (_tables[i]._state == EXIST)
// {
// // <20><><EFBFBD>¼<EFBFBD><C2BC><EFBFBD><EFBFBD>±<EFBFBD><C2B1>е<EFBFBD>λ<EFBFBD><CEBB>
// size_t index = koft(_tables[i]._data) % newtables.size();
// size_t step = SecondHash(koft(_tables[i]._data), newtables.size());
// // <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ͻ<EFBFBD><CDBB>˫<EFBFBD>ع<EFBFBD>ϣ̽<CFA3><CCBD>
// while (newtables[index]._state == EXIST)
// {
// index = (index + step) % newtables.size();
// }
// // <20><><EFBFBD><EFBFBD>Ԫ<EFBFBD>ص<EFBFBD><D8B5>±<EFBFBD>
// newtables[index] = _tables[i];
// }
// }
// _tables.swap(newtables);
// }
// version 3
// <20><>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>˼·
if (_tables.size() == 0 || _num * 10 / _tables.size() >= 7)
{
Close_HashTable<K, T, KeyOfT> newht;
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
newht._tables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i]._state == EXIST)
{
newht.Insert(_tables[i]._data);
}
}
_tables.swap(newht._tables);
}
}
bool Insert(const T& data)
{
KeyOfT koft;
CheckCapacity();
// <20><>ɢ<EFBFBD><C9A2><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>̽<EFBFBD><CCBD><EFBFBD><EFBFBD>ʲô<CAB2><C3B4><EFBFBD><EFBFBD>?
// <20><><EFBFBD><EFBFBD>̽<EFBFBD><CCBD>˼·<CBBC><C2B7><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD>λ<EFBFBD>ñ<EFBFBD>ռ<EFBFBD><D5BC>, <20>ҾͰ<D2BE><CDB0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȥռ<C8A5><D5BC><EFBFBD>˵<EFBFBD>λ<EFBFBD><CEBB>, <20><><EFBFBD>ܻᵼ<DCBB><E1B5BC>һƬһƬ<D2BB>ij<EFBFBD>ͻ, <20><>ˮЧӦ
// version 1
// <20><><EFBFBD><EFBFBD>̽<EFBFBD><CCBD>
// <20><><EFBFBD><EFBFBD> data <20>е<EFBFBD> key <20>ڱ<EFBFBD><DAB1><EFBFBD>ӳ<EFBFBD><D3B3><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
// size_t index = koft(data) % _tables.size();
// while (_tables[index]._state == EXIST)
// {
// if (koft(_tables[index]._data) == koft(data))
// {
// return false; // <20>Ѿ<EFBFBD><D1BE><EFBFBD><EFBFBD><EFBFBD>
// }
// ++index;
// if (index == _tables.size())
// {
// index = 0;
// }
// }
// version 2
// <20><><EFBFBD><EFBFBD>̽<EFBFBD><CCBD>
// <20><><EFBFBD><EFBFBD> data <20>е<EFBFBD> key <20>ڱ<EFBFBD><DAB1><EFBFBD>ӳ<EFBFBD><D3B3><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
// size_t start = koft(data) % _tables.size();
// size_t index = start;
// int i = 0;
// while (_tables[index]._state == EXIST)
// {
// if (koft(_tables[index]._data) == koft(data))
// {
// return false; // <20>Ѿ<EFBFBD><D1BE><EFBFBD><EFBFBD><EFBFBD>
// }
// index = start + i * i;
// i++;
// index %= _tables.size();
// }
// version 3
// ˫<>ع<EFBFBD>ϣ
size_t index = koft(data) % _tables.size();
size_t step = SecondHash(koft(data), _tables.size());
while (_tables[index]._state == EXIST)
{
if (koft(_tables[index]._data) == koft(data))
{
return false; // <20><><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD>ͬ<EFBFBD><CDAC> key<65><79><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʧ<EFBFBD><CAA7>
}
index = (index + step) % _tables.size(); // ʹ<><CAB9>˫<EFBFBD>ع<EFBFBD>ϣ<EFBFBD><CFA3><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>λ<EFBFBD><CEBB>
}
_tables[index]._data = data;
_tables[index]._state = EXIST;
++_num;
// <20><>ô<EFBFBD><C3B4><EFBFBD>Կ<EFBFBD><D4BF><EFBFBD><EFBFBD><EFBFBD>ɢ<EFBFBD><C9A2>-<2D><><EFBFBD>Ŷ<EFBFBD><C5B6>Ʒ<EFBFBD><C6B7><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD>ֺõĽ<C3B5><C4BD><EFBFBD><EFBFBD><EFBFBD>ʽ, <20><>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ҵ<EFBFBD>λ<EFBFBD>ñ<EFBFBD>ռ<EFBFBD><D5BC>, <20>Ҿ<EFBFBD>ȥ<EFBFBD><C8A5>ռ<EFBFBD><D5BC><EFBFBD>˵<EFBFBD>λ<EFBFBD>õ<EFBFBD>˼·
// Ҳ<><D2B2><EFBFBD><EFBFBD>˵<EFBFBD><CBB5><EFBFBD>Ĺ<EFBFBD>ϣ<EFBFBD><CFA3>ͻ<EFBFBD><CDBB><EFBFBD>໥Ӱ<E0BBA5><D3B0>, <20>ҳ<EFBFBD>ͻռ<CDBB><D5BC><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD>ͻռ<CDBB><D5BC><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD>ͻ<EFBFBD><CDBB>... , û<><C3BB>û<EFBFBD><C3BB>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ч<EFBFBD>ʶ<EFBFBD><CAB6><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// <20><>ɢ<EFBFBD>еĹ<D0B5>ϣͰ<CFA3><CDB0><EFBFBD>Խ<EFBFBD><D4BD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
return true;
}
// <20><><EFBFBD><EFBFBD>̽<EFBFBD><CCBD>
// HashData *Find(const K &key)
// {
// KeyOfT koft;
// // <20><><EFBFBD><EFBFBD> data <20>е<EFBFBD> key <20>ڱ<EFBFBD><DAB1><EFBFBD>ӳ<EFBFBD><D3B3><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
// size_t index = key % _tables.size();
// while (_tables[index]._state != EMPTY)
// {
// if (koft(_tables[index]._data) == key)
// {
// if (_tables[index]._state == EXIST)
// {
// return &_tables[index];
// }
// else if (_tables[index]._state == DELETE)
// {
// return nullptr;
// }
// }
// ++index;
// if (index == _tables.size())
// {
// index = 0;
// }
// }
// return nullptr;
// }
// ˫<>ع<EFBFBD>ϣ
HashData* Find(const K& key)
{
KeyOfT koft;
size_t index = key % _tables.size();
size_t step = SecondHash(key, _tables.size()); // <20><><EFBFBD>㲽<EFBFBD><E3B2BD>
while (_tables[index]._state != EMPTY)
{
if (koft(_tables[index]._data) == key)
{
if (_tables[index]._state == EXIST)
{
return &_tables[index];
}
else if (_tables[index]._state == DELETE)
{
return nullptr;
}
}
index = (index + step) % _tables.size(); // ʹ<><CAB9>˫<EFBFBD>ع<EFBFBD>ϣ̽<CFA3><CCBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>λ<EFBFBD><CEBB>
}
return nullptr;
}
bool Erase(const K& key)
{
HashData* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_num;
return true;
}
else
{
return false;
}
}
HashData& getHashData(int pos)
{
return _tables[pos];
}
void Print()
{
int size = _tables.size();
for (int i = 0; i < size; i++)
{
std::cout << i << "\t";
}
std::cout << std::endl;
for (int i = 0; i < size; i++)
{
auto cur = _tables[i];
if (cur._state == EXIST)
{
std::cout << cur._data << "\t";
}
else
{
std::cout << "*\t";
}
}
std::cout << "\n\n";
}
private:
std::vector<HashData> _tables;
size_t _num = 0; // <20>洢<EFBFBD>˼<EFBFBD><CBBC><EFBFBD><EFBFBD><EFBFBD>Ч<EFBFBD><D0A7><EFBFBD><EFBFBD>
};
template <class T>
struct HashNode
{
T _data; // <20>洢<EFBFBD><E6B4A2><EFBFBD><EFBFBD>
HashNode<T>* _next; // <20>洢<EFBFBD><E6B4A2>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҫʵ<D2AA>ֵ<EFBFBD><D6B5><EFBFBD>˳<EFBFBD><CBB3>Ϊ<EFBFBD><CEAA><EFBFBD><EFBFBD>˳<EFBFBD><CBB3>, <20><><EFBFBD>Լ<EFBFBD><D4BC><EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><D6B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// HashNode<T>* _linknext;
// HashNode<T>* _linkprev;
HashNode(const T& data)
: _data(data), _next(nullptr)
{
}
};
// ǰ<><C7B0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
template <class K, class T, class KeyOfT, class Hash>
class Open_HashTable;
// <20><>ϣ<EFBFBD><CFA3>ֻ<EFBFBD>е<EFBFBD><D0B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, ֻ<><D6BB> ++, û<><C3BB>--
template <class K, class T, class KeyOfT, class Hash>
struct __HashTableIterator
{
typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;
typedef Open_HashTable<K, T, KeyOfT, Hash> HT;
typedef HashNode<T> Node;
Node* _node;
HT* _pht;
__HashTableIterator(Node* node, HT* pht)
: _node(node), _pht(pht)
{
}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
// <20><><EFBFBD><EFBFBD>һ<EFBFBD><D2BB>Ͱ<EFBFBD><CDB0><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20>ҵ<EFBFBD><D2B5><EFBFBD>һ<EFBFBD><D2BB>Ͱ<EFBFBD><CDB0><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
KeyOfT koft;
size_t index = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.size();
++index;
while (index < _pht->_tables.size())
{
Node* cur = _pht->_tables[index];
if (cur)
{
_node = cur;
return *this;
}
++index;
}
_node = nullptr;
}
return *this;
}
Self operator++(int)
{
Self tmp(*this);
++*this;
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
template <class K>
struct _Hash
{
const K& operator()(const K& key)
{
return key;
}
};
// <20>ػ<EFBFBD>
template <>
struct _Hash<std::string>
{
size_t operator()(const std::string& key)
{
// BKDR Hash
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
struct _HashString
{
size_t operator()(const std::string& key)
{
// BKDR Hash
size_t hash = 0;
for (size_t i = 0; i < key.size(); i++)
{
hash *= 131;
hash += key[i];
}
return hash;
}
};
template <class K, class T, class KeyOfT, class Hash>
// template <class K, class T, class KeyOfT, class Hash = _Hash<K>>
class Open_HashTable
{
private:
typedef HashNode<T> Node;
public:
friend struct __HashTableIterator<K, T, KeyOfT, Hash>;
typedef __HashTableIterator<K, T, KeyOfT, Hash> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
if (_tables[i])
{
return iterator(_tables[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
Open_HashTable()
{
}
Open_HashTable(size_t bucket_count)
: _tables(bucket_count), _num(0)
{
}
~Open_HashTable()
{
Clear();
}
void Clear()
{
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;
}
}
size_t HashFunc(const K& key)
{
Hash hash;
return hash(key);
}
size_t GetNextPrime(size_t num)
{
const int PrimeSize = 28;
static const unsigned long PrimeList[PrimeSize] =
{
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 };
for (size_t i = 0; i < PrimeSize; i++)
{
if (PrimeList[i] > num)
{
return PrimeList[i];
}
}
return PrimeList[PrimeSize - 1]; // <20><><EFBFBD><EFBFBD><EFBFBD>Ѿ<EFBFBD><D1BE><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
}
// <20><><EFBFBD>¹<EFBFBD>ϣ
void Rehash(size_t newsize)
{
KeyOfT koft;
std::vector<Node*> newtables;
newtables.resize(newsize);
for (size_t i = 0; i < _tables.size(); i++)
{
// <20><><EFBFBD>ɱ<EFBFBD><C9B1>еĽڵ<C4BD>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD>, <20><><EFBFBD>¼<EFBFBD><C2BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±<EFBFBD><C2B1>е<EFBFBD>λ<EFBFBD><CEBB>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ȥ
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = HashFunc(koft(cur->_data)) % newtables.size();
cur->_next = newtables[index];
newtables[index] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݳ<EFBFBD>ͻ, <20><>Щ<EFBFBD><D0A9>ϣ<EFBFBD><CFA3>ͻ<EFBFBD><CDBB><EFBFBD><EFBFBD><EFBFBD>ݾͻ<DDBE><CDBB><EFBFBD><EFBFBD><EFBFBD>ͬһ<CDAC><D2BB><EFBFBD><EFBFBD>ʽͰ<CABD><CDB0>, <20><><EFBFBD><EFBFBD>ʱЧ<CAB1>ʾͻή<CDBB><E1BDB5>, <20><><EFBFBD>Կ<EFBFBD>ɢ<EFBFBD><C9A2>-<2D><>ϣͰҲ<CDB0><D2B2>Ҫ<EFBFBD><D2AA><EFBFBD>ƹ<EFBFBD>ϣ<EFBFBD><CFA3>ͻ<EFBFBD>ġ<EFBFBD>
// <20><><EFBFBD>ο<EFBFBD><CEBF><EFBFBD><EFBFBD><EFBFBD>? ͨ<><CDA8><EFBFBD><EFBFBD><EFBFBD>Ƹ<EFBFBD><C6B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ͱѿռ<D1BF><D5BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һЩ, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ҳ<EFBFBD><D2B2><EFBFBD>Ը<EFBFBD>һЩ, һ<>㿪ɢ<E3BFAA>аѸ<D0B0><D1B8><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӿ<EFBFBD><D3BF>Ƶ<EFBFBD>1, <20><><EFBFBD>ȽϺ<C8BD>һ<EFBFBD><D2BB>
std::pair<iterator, bool> Insert(const T& data)
{
KeyOfT koft;
// 1. <20><><EFBFBD>鸺<EFBFBD><E9B8BA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ӵ<EFBFBD><D3B5><EFBFBD> 1 , <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>Ĺ<EFBFBD>ϣ<EFBFBD><CFA3>ͻ
if (_tables.size() == _num)
{
// 1. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>С<EFBFBD><D0A1><EFBFBD>±<EFBFBD><C2B1><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
// 2. <20><><EFBFBD><EFBFBD><EFBFBD>ɱ<EFBFBD><C9B1><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD>¼<EFBFBD><C2BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD>±<EFBFBD><C2B1>е<EFBFBD>λ<EFBFBD><CEBB>
// 3. <20>ͷžɱ<C5BE>
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
// size_t newsize = GetNextPrime(_tables.size());
Rehash(newsize);
}
// 2. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڱ<EFBFBD><DAB1><EFBFBD>ӳ<EFBFBD><D3B3><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
size_t index = HashFunc(koft(data)) % _tables.size();
// 3. <20>Ȳ<EFBFBD><C8B2><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ֵ<EFBFBD>ڲ<EFBFBD><DAB2>ڱ<EFBFBD><DAB1><EFBFBD>, <20>Ƿ<EFBFBD><C7B7>г<EFBFBD>ͻ
Node* cur = _tables[index];
while (cur)
{
if (HashFunc(koft(cur->_data)) == HashFunc(koft(data)))
{
// <20><><EFBFBD><EFBFBD><EFBFBD>Ѿ<EFBFBD><D1BE><EFBFBD><EFBFBD>ڸü<DAB8><C3BC><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ʧ<EFBFBD><CAA7>
return std::make_pair(iterator(cur, this), false);
}
else
{
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>
cur = cur->_next;
}
}
// 4. ͷ<><CDB7><EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>(β<><CEB2>Ҳ<EFBFBD>ǿ<EFBFBD><C7BF>Ե<EFBFBD>)
Node* newnode = new Node(data);
newnode->_next = _tables[index];
_tables[index] = newnode;
++_num; // <20><><EFBFBD><EFBFBD><EFBFBD>Ѵ洢Ԫ<E6B4A2><D4AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
return std::make_pair(iterator(newnode, this), true);
}
// <20><><EFBFBD>Ҳ<EFBFBD><D2B2><EFBFBD>
Node* Find(const K& key)
{
KeyOfT koft;
// 1. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ڱ<EFBFBD><DAB1><EFBFBD>ӳ<EFBFBD><D3B3><EFBFBD><EFBFBD>λ<EFBFBD><CEBB>
size_t index = HashFunc(key) % _tables.size();
Node* cur = _tables[index];
// 2. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ƥ<EFBFBD><C6A5><EFBFBD>ļ<EFBFBD>
while (cur)
{
if (HashFunc(koft(cur->_data)) == HashFunc(key))
{
// <20><><EFBFBD><EFBFBD><EFBFBD>ҵ<EFBFBD>ƥ<EFBFBD><C6A5><EFBFBD><EFBFBD>Ԫ<EFBFBD>أ<EFBFBD><D8A3><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ָ<EFBFBD><D6B8>
return cur;
}
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>
cur = cur->_next;
}
// <20><><EFBFBD><EFBFBD>δ<EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ؿ<EFBFBD>ָ<EFBFBD><D6B8>
return nullptr;
}
bool Erase(const K& key)
{
KeyOfT koft;
// 1. <20><><EFBFBD><EFBFBD>Ҫɾ<D2AA><C9BE>Ԫ<EFBFBD>صĹ<D8B5>ϣֵ
size_t index = HashFunc(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[index];
// 2. <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>, <20><><EFBFBD><EFBFBD>ƥ<EFBFBD><C6A5><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA>
while (cur)
{
if (HashFunc(koft(cur->_data)) == HashFunc(key))
{
// 3. <20>ҵ<EFBFBD>Ԫ<EFBFBD>غ<EFBFBD>, <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ṹ
if (prev == nullptr)
{
// <20><><EFBFBD><EFBFBD>Ҫɾ<D2AA><C9BE><EFBFBD><EFBFBD>Ԫ<EFBFBD><D4AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ĵ<EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>, ֱ<><D6B1><EFBFBD><EFBFBD>Ͱָ<CDB0><D6B8><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>
_tables[index] = cur->_next;
}
else
{
// <20><><EFBFBD>򣬽<EFBFBD>ǰһ<C7B0><D2BB><EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD> next ָ<><D6B8><EFBFBD><EFBFBD>ǰ<EFBFBD>ڵ<EFBFBD><DAB5><EFBFBD><EFBFBD><EFBFBD>һ<EFBFBD><D2BB><EFBFBD>ڵ<EFBFBD>
prev->_next = cur->_next;
}
// 4. <20>ͷŽڵ<C5BD><DAB5>ڴ<EFBFBD>
delete cur;
--_num; // Ԫ<><D4AA><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
return true;
}
else
{
// <20><><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
prev = cur;
cur = cur->_next;
}
}
// <20><><EFBFBD><EFBFBD>δ<EFBFBD>ҵ<EFBFBD><D2B5><EFBFBD>Ԫ<EFBFBD>أ<EFBFBD><D8A3><EFBFBD><EFBFBD><EFBFBD> false
return false;
}
void Print() const
{
KeyOfT koft;
int size = _tables.size();
for (int i = 0; i < size; i++)
{
std::cout << i << "\t";
Node* cur = _tables[i];
while (cur)
{
std::cout << koft(cur->_data) << "\t";
cur = cur->_next;
}
std::cout << std::endl;
}
std::cout << std::endl;
}
private:
std::vector<Node*> _tables; // <20><>ϣ<EFBFBD><CFA3><EFBFBD>洢Ͱ
size_t _num; // <20><>¼<EFBFBD>Ŵ洢<C5B4><E6B4A2><EFBFBD><EFBFBD><EFBFBD>ݸ<EFBFBD><DDB8><EFBFBD>
};
}
Reference in New Issue Copy Permalink