Directory
Hash table transformation
hash table structure
functor implementation
hash table iterator
structure
operator* and operator->
operator != and ==
operator ++
Constructor
copy construction
destructor
copy construction
The complete code of the hash table
unordered_set package source code
unordered_map package source code
Hash table transformation
We know that unordered_map is a K-type structure, unordered_map is a K, V-type structure, so how to encapsulate them through a hash table?
Next we transform the hash table. (This article uses an open hash structure to implement a hash table)
T represents the data type stored by the node.
Hash Table Structure
template<class T>
struct HashNode
{
T_data;
HashNode<T>* _next;
HashNode(const T & data)
:_data(data)
,_next(nullptr)
{
}
};
Since unordered_map is a KV structure, we need to add a template parameter to extract the key value, which is KeyofT,
And the hash table needs to convert the key value into an integer that can be modulo, so set a HashFunc parameter, through which we can implement the functor to achieve our goal.
template<class K, class T, class KeyofT, class HashFunc=Hash<K>>
class HashTable
{
typedef HashNode<T> Node;
private:
vector<Node*> _table;//storage node pointer
size_t _n=0;//Number of valid data
};
Functor implementation
struct MapKeyofT
{
const K & amp; operator()(const pair<K, V> & amp; kv)
{
return kv.first;
}
};
struct SetKeyofT
{
const K & amp; operator()(const K & amp; key)
{
return key;
}
};
The string type is also commonly used as a key, so we specialize the string type.
template<class K>
struct Hash
{
size_t operator()(const K & key)
{
return key;
}
};
template<>
struct Hash<string>
{
size_t operator()(const string & s)
{
size_t ret = 0;
for (auto e : s)
{
ret *= 31;
ret += e;
}
return ret;
}
};
unordered_set structure:
template<class K, class hash = Hash<K>>
class unordered_set
{
private:
HashTable<K, K, SetKeyofT, hash> _ht;
};
unordered_map structure:
template<class K, class V, class hash = Hash<K>>
class unordered_map
{
struct MapKeyofT
{
const K & amp; operator()(const pair<K, V> & amp; kv)
{
return kv.first;
}
};
private:
HashTable<K, pair<K, V>, MapKeyofT, hash> _ht;
};
Hash Table Iterator
First of all, it is clear that the unordered_map and unordered_set iterators are one-way, so the iterators of our internal hash table support + + operations.
We use an open hash structure, how to implement iterator ++?
The idea is to find a non-empty hash bucket first, + + is to traverse the bucket, so what if the bucket is traversed? We are going to the next non-empty bucket, so our iterator not only stores the address of the node, but also stores the address of the hash table.
Structure
template<class K,class T,class Ref,class Ptr,class KeyofT,class HashFunc>
struct HashTableIterator
{
typedef HashNode<T> Node;
typedef HashTableIterator<K, T, Ref, Ptr, KeyofT, HashFunc> self;
//Store the node pointer and the address of a hash table
Node* _node;
HashTable<K, T, KeyofT, HashFunc>* _pht;
HashTableIterator( Node* node, HashTable<K, T, KeyofT, HashFunc>* pht)
:_node(node)
,_pht(pht)
\t
};
operator!=and==
The iterator internally stores the node address, and you can directly use the node address to compare whether they are equal.
bool operator!=(const self & amp; it)const
{
return _node != it._node;
}
bool operator==(const self & amp; it)const
{
return _node == it._node;
}
operator + +
If the next node is not empty, traverse directly to the next node.
If empty, find a new non-empty bucket.
self & operator + + ()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Key of T kot;
HashFunc hf;
Node* cur = _node;
size_t index = hf(kot(cur->_data)) % _pht->_table.size();
index + + ;
while (index < _pht->_table. size())
{
if (_pht->_table[index])
{
break;
}
else
{
index + + ;
}
}
if (index == _pht->_table. size())
{
_node = nullptr;
}
else
{
_node = _pht->_table[index];
}
}
return *this;
}
Constructor
Since the hash table uses vector internally, we don’t need to explicitly write the constructor.
//Specify the compiler to generate the constructor by default HashTable() = default;
Copy Construction
HashTable(const HashTable<K, T, KeyofT, HashFunc> & amp; ht)
{
_table.resize(ht._table.size());
for (size_t i = 0; i < ht._table.size(); + + i)
{
Node* cur = ht._table[i];
while (cur)
{
Node* newnode = new Node(cur->_data);
newnode->_next = _table[i];
_table[i] = newnode;
cur = cur->_next;
}
}
}
Destructor
Traverse each hash bucket and release the nodes in it.
HashTable(const HashTable<K, T, KeyofT, HashFunc> & amp; ht)
{
_table.resize(ht._table.size());
for (size_t i = 0; i < ht._table.size(); + + i)
{
Node* cur = ht._table[i];
while (cur)
{
Node* newnode = new Node(cur->_data);
newnode->_next = _table[i];
_table[i] = newnode;
cur = cur->_next;
}
}
}
Copy construction
self & amp; operator=(self ht)
{
_table.swap(ht._table);
swap(_n, ht._n);
return *this;
}
Full code of the hash table
//open hash, open addressing method, hash bucket
namespace LinkHash
{
template<class T>
struct HashNode
{
T_data;
HashNode<T>* _next;
HashNode(const T & data)
:_data(data)
,_next(nullptr)
{
}
};
template
class HashTable;
template
struct HashTableIterator
{
typedef HashNode Node;
typedef HashTableIterator self;
//Store the node pointer and the address of a hash table
Node* _node;
HashTable* _pht;
HashTableIterator( Node* node, HashTable* pht)
:_node(node)
,_pht(pht)
{
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(operator*());
}
bool operator!=(const self & it)const
{
return _node != it._node;
}
bool operator==(const self & amp; it)const
{
return _node == it._node;
}
self & operator ++ ()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Key of T kot;
HashFunc hf;
Node* cur = _node;
size_t index = hf(kot(cur->_data)) % _pht->_table.size();
index + + ;
while (index < _pht->_table. size())
{
if (_pht->_table[index])
{
break;
}
else
{
index + + ;
}
}
if (index == _pht->_table. size())
{
_node = nullptr;
}
else
{
_node = _pht->_table[index];
}
}
return *this;
}
};
template>
class HashTable
{
typedef HashNode Node;
friend struct HashTableIterator;
typedef HashTable self;
public:
typedef HashTableIterator iterator;
typedef HashTableIterator const_iterator;
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);
}
const_iterator begin() const
{
for (size_t i = 0; i < _table. size(); + + i)
{
if (_table[i])
{
return const_iterator(_table[i], this);
}
}
return end();
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
//Specify the compiler to generate the constructor by default
HashTable() = default;
\t\t
HashTable(const HashTable & ht)
{
_table.resize(ht._table.size());
for (size_t i = 0; i < ht._table.size(); + + i)
{
Node* cur = ht._table[i];
while (cur)
{
Node* newnode = new Node(cur->_data);
newnode->_next = _table[i];
_table[i] = newnode;
cur = cur->_next;
}
}
}
~HashTable()
{
for (size_t i = 0; i < _table. size(); + + i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
self & operator=(self ht)
{
_table.swap(ht._table);
swap(_n, ht._n);
return *this;
}
size_t GetNextPrime(size_t num)
{
static const unsigned long __stl_prime_list[28] =
{
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
};
for (size_t i = 0; i < 28; + + i)
{
if (__stl_prime_list[i] > num)
{
return __stl_prime_list[i];
}
}
return __stl_prime_list[27];
}
bool erase(const K & key)
{
if (_table. empty())
{
return false;
}
Key of T kot;
HashFunc hf;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
Node* prev = nullptr;
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
{
_table[index] = cur->_next;
}
else
{
Node* next = cur->_next;
prev->_next = next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
iterator Find(const K & key)
{
if (_table. empty())
{
return iterator(nullptr, this);
}
Key of T kot;
HashFunc hf;
size_t index = hf(key) % _table.size();
Node* cur = _table[index];
while (cur)
{
if (kot(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return iterator(nullptr, this);
}
pair insert(const T & amp; data)
{
Key of T kot;
auto ret = Find(kot(data));
if (ret._node)
{
return make_pair(ret, false);
}
HashFunc hf;
if (_n == _table. size())
{
//Expansion
//size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2;
size_t newsize = GetNextPrime(_n);
vector newTable;
newTable.resize(newsize);
for (size_t i = 0; i < _table. size(); + + i)
{
if (_table[i])
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t index = hf(kot(cur->_data)) % newsize;
cur->_next = newTable[index];
newTable[index] = cur;
cur = next;
}
_table[i] = nullptr;
}
}
_table. swap(newTable);
}
size_t index = hf(kot(data)) % _table.size();
Node* newnode = new Node(data);
newnode->_next = _table[index];
_table[index] = newnode;
+ + _n;
return make_pair(iterator(newnode, this), true);
}
size_t size() const
{
return_n;
}
private:
vector _table;//storage node pointer
size_t _n=0;//Number of valid data
};
}
unordered_set package source code
namespace HashArea
{
template<class K, class hash = Hash<K>>
class unordered_set
{
struct SetKeyofT
{
const K & amp; operator()(const K & amp; key)
{
return key;
}
};
public:
typedef typename LinkHash::HashTable<K, K, SetKeyofT, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht. end();
}
iterator Find(const K & key)
{
return _ht. Find(key);
}
bool erase(const K & key)
{
return _ht. erase(key);
}
pair<iterator, bool> insert(const K & amp; key)
{
return _ht.insert(key);
}
private:
LinkHash::HashTable<K, K, SetKeyofT, hash> _ht;
};
\t
}
unordered_map package source code
namespace HashArea
{
template<class K, class V, class hash = Hash<K>>
class unordered_map
{
struct MapKeyofT
{
const K & amp; operator()(const pair<K, V> & amp; kv)
{
return kv.first;
}
};
public:
typedef typename LinkHash::HashTable<K, pair<K, V>, MapKeyofT, hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht. end();
}
bool erase(const K & key)
{
return _ht. erase(key);
}
pair<iterator, bool> insert(const pair<K, V> & kv)
{
return _ht.insert(kv);
}
iterator Find(const K & key)
{
return _ht. Find(key);
}
size_t size() const
{
return _ht. size();
}
V & amp; operator[](const K & amp; key)
{
auto ret = _ht.insert(make_pair(key, V()));
return ret.first->second;
}
private:
LinkHash::HashTable<K, pair<K, V>, MapKeyofT, hash> _ht;
};
}