Table of Contents
HashTable.h:
Test.cpp:
MyUnorderedSet.h:
HashTable.h:
#pragma once
#include<iostream>
#include<vector>
#include<utility>//pair header file
#include<assert.h>
#include<string>
using namespace std;
namespace CLOSEHASH
{
enum State
{
EMPTY, //empty
EXIST, //exists
DELETE //Delete
};
template<class T>
struct HashData
{
T_data;
State _state; //Represents data status
HashData()
:_state(EMPTY)
,_data(0)
{}
};
template<class K, class T, class KeyOfT>
classHashTable
{
typedef HashData<T> HashData;
public:
bool Insert(const T & data)
{
KeyOfTkoft;
//1. Capacity increase: The capacity needs to be increased when inserted for the first time or when the load factor is >= 0.7.
if (_tables.capacity() == 0 || _num * 10 / _tables.capacity() == 7)
{
//A. Capacity increase-traditional idea
//vector<HashData> newtables;
//size_t newcapacity = _tables.capacity() == 0 ? 10 : _tables.capacity() * 2;
//newtables.resize(newcapacity);//open space + automatically initialized to 0
Copy the old space data to the new space
//for (size_t i = 0; i < _tables.capacity(); + + i)
//{
// if (_tables[i]._state == EXIST)
// {
// size_t index = koft(_tables[i]._data) % newtables.capacity();
// while (newtables[index]._state == EXIST)
// {
// index + + ;
// if (index == newtables.capacity())
// {
//index = 0;//When you reach the end, you have to return to the beginning to find the position
// }
// }
// newtables[index] = _tables[i];
// }
//}
//_tables.swap(newtables);
//B. Capacity increase - simple idea
HashTable<K, T, KeyOfT> newht;
size_t newcapacity = _tables.capacity() == 0 ? 10 : _tables.capacity() * 2;
newht._tables.resize(newcapacity);
for (size_t i = 0; i < _tables.capacity(); + + i)
{
if (_tables[i]._state == EXIST)
{
newht.Insert(_tables[i]._data);//Insert each data in the original hash table into the new hash table using Insert
}
}
_tables.swap(newht._tables);//Swap the two vectors
}
//1. Linear detection
//size_t index = koft(data) % _tables.capacity();//Calculate the location to be mapped
//while (_tables[index]._state == EXIST)
//{
// if (koft(_tables[index]._data) == koft(data))
// {
// return false;//If the same data exists
// }
// + + index;
// if (index == _tables.capacity())
// {
// index = 0;
// }
//}
//2. Second detection
size_t start = koft(data) % _tables.capacity();
size_t index = start;
int i = 1;
while (_tables[index]._state == EXIST)
{
if (koft(_tables[index]._data) == koft(data))
{
return false;
}
index = start + i * i;
+ + i;
index %= _tables.capacity();
}
//Insert data
_tables[index]._data = data;
_tables[index]._state = EXIST;
+ + _num; //Number of valid data + +
\t\t\t
return true;
}
HashData* Find(const K & amp; key)
{
KeyOfTkoft;
size_t index = key % _tables.capacity();
while(_tables[index]._state != EMPTY)
{//As long as it exists or is deleted, continue to search down.
if (koft(_tables[index]._data) == key)
{
if (_tables[index]._state == EXIST)
return & amp;_tables[index];//The values are equal and exist
else
return nullptr;//The values are equal but in the deleted state, indicating that they have been deleted
}
+ + index;//If not found, continue searching
index %= _tables.capacity();
}
return nullptr;
}
bool Erase(const K & amp; key)
{
HashData* ret = Find(key);
if (ret)
{
ret->_state = DELETE;//Use status to represent deletion status
--_num; //--The number of valid elements
return true;
}
else
{
return false;
}
}
private:
vector<HashData> _tables;
size_t _num = 0; //How many valid numbers are stored in the table, which is not equal to the capacity
};
}
namespace OPENHASH
{
template<class T>
struct HashNode
{
T_data;
HashNode<T>* _next;
HashNode(const T & data)
:_data(data)
, _next(nullptr)
{}
};
//Preliminary statement: In order to allow the iterator of the hash table to use the hash table
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
template<class K, class T, class KeyOfT, class Hash>
struct __HashTableIterator
{
typedef __HashTableIterator<K, T, KeyOfT, Hash> Self;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HashNode<T> Node;
Node* _node;//The node pointer is stored in the iterator
HT* _pht; //Object pointer
__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
{
// If a bucket is finished, go down to find the next bucket and continue traversing
KeyOfTkoft;
//First calculate which bucket I am currently in
size_t i = _pht->HashFunc(koft(_node->_data)) % _pht->_tables.capacity();
+ + i;//Next bucket
for (; i < _pht->_tables.capacity(); + + i)
{ //Find a bucket that is not empty
Node* cur = _pht->_tables[i];
if (cur)
{ //If this bucket is not empty
_node = cur;
return *this;
}
}
_node = nullptr;//If no bucket with data is found, the pointer is set to empty, consistent with end()
return *this;
}
}
bool operator!=(const Self & amp; s)
{
return _node != s._node;
}
};
template<class K>
struct_Hash
{
const K & amp; operator()(const K & amp; key)
{
return key;//You can take the modulo and return it directly
}
};
//Specialization
template<>
struct _Hash<string>
{
size_t operator()(const string & amp; key)
{
//Use BKDR Hash algorithm
size_t hash = 0;
for (size_t i = 0; i < key.size(); + + i)
{
hash *= 131; //BKDR
hash + = key[i];//Add the ASCII code value of each letter in the string
}
return hash;
}
};
template<class K, class T, class KeyOfT, class Hash>
classHashTable
{
typedef HashNode<T> Node;
public:
friend struct __HashTableIterator<K, T, KeyOfT, Hash>;//Because the iterator needs to access the private member _tables of the hash table
typedef __HashTableIterator<K, T, KeyOfT, Hash> iterator;
//begin() returns the first node of the first bucket that is not empty
iterator begin()
{
for (size_t i = 0; i < _tables.capacity(); + + i)
{
if (_tables[i])
{
return iterator(_tables[i], this);//If found, construct an anonymous object and return it
}
}
return end();//If not found in each bucket, return end()
}
iterator end()
{
return iterator(nullptr, this);
}
size_t HashFunc(const K & amp; key)
{
Hash hash;
return hash(key);//Use functor to convert key value into integer
}
size_t GetNextPrime(size_t num)
{
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
};
\t\t\t
for (size_t i = 0;; i < PRIMECOUNT; + + i)
{
if (primeList[i] > num)
return primeList[i];
}
return primeList[PRIMECOUNT - 1];//If num is larger than all the data in my table, the last one in the table will be returned by default
}
pair<iterator, bool> Insert(const T & amp; data)
{
KeyOfTkoft;
//1. Determine whether to increase capacity
if (_tables.capacity() == _num)
{ //If the balance factor of open hashing is 1, the capacity will be increased, and the first insertion will also increase the capacity.
//size_t newcapacity = _tables.capacity() == 0 ? 10 : _tables.capacity() * 2;
size_t newcapacity = GetNextPrime(_tables.capacity());
vector<Node*> newtables;
newtables.resize(newcapacity, nullptr);//Open new space + initialization for new vector
//Recalculate the mapping position of the data in the old table in the new table
for (size_t i = 0; i < _tables.capacity(); + + i)
{ //If it is the first time to increase the capacity, it will not enter the for loop, so there is no need to worry about whether the initial data of the table is nullptr
//Each bucket in the hash table is a singly linked list, so examine the head insertion of the singly linked list
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t index = HashFunc(koft(cur->_data)) % newtables.capacity();//Recalculate the mapping position
//Head plug
cur->_next = newtables[index];
newtables[index] = cur;
\t\t\t\t\t\t
cur = next;
}
_tables[i] = nullptr;//Map to new table and set to empty
}
_tables.swap(newtables);//vector exchange of old and new tables
}
size_t index = HashFunc(koft(data)) % _tables.capacity();//Calculate the new mapping position
//1. First find whether this element is in the hash table
Node* cur = _tables[index];//You can determine which bucket it is by knowing the mapping position
while (cur)
{
if (koft(cur->_data) == koft(data))
return make_pair(iterator(cur, this), false);//If the same data is found, the insertion fails
else
cur = cur->_next;
}
//2. Insert the head into this bucket
Node* newnode = new Node(data);//Open a new node
//Head plug
newnode->_next = _tables[index];
_tables[index] = newnode;
+ + _num;//The number of valid elements in the hash table + +
return make_pair(iterator(newnode, this), false);
}
Node* Find(const K & amp; key)
{
KeyOfTkoft;
size_t index = HashFunc(key) % _tables.capacity();//Calculate the mapping position first
Node* cur = _tables[index];
while (cur)
{
if (koft(cur->_data) == key)
return cur;
else
cur = cur->_next;
}
return nullptr;//If the bucket is not found, it will return empty.
}
bool Erase(const K & amp; key)
{
assert(_tables.capacity() > 0); //Delete only if there is space
KeyOfTkoft;
size_t index = HashFunc(key) % _tables.capacity();
Node* cur = _tables[index];
Node* prev = nullptr; //Record the previous position of cur
while (cur)
{
if (koft(cur->_data) == key)
{
if (prev == nullptr)
{ //If it is header deletion
_tables[index] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
--_num;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;//The data to be deleted does not exist at all
}
~HashTable()
{
Clear();
//We don’t need to release the vector because it is a custom type. When the hash table needs to be cleaned, the vector will also be automatically cleaned.
}
void Clear()
{
for (size_t i = 0; i < _tables.capacity(); + + i)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;//set to nullptr after clearing the data
}
}
private:
vector<Node*> _tables; //When using vector, you must include the std library, otherwise it cannot be used
size_t _num = 0; //The number of valid elements, not the capacity
};
}
Test.cpp:
#include"HashTable.h"
#include"MyUnorderedMap.h"
#include"MyUnorderedSet.h"
template<class K>
struct SetKeyOfT
{
const K & amp; operator()(const K & amp; key)
{
return key;
}
};
void TestCloseHash()
{
CLOSEHASH::HashTable<int, int, SetKeyOfT<int>> ht;
//CLOSEHASH::HashTable<int, int, MapKeyOfT<int, int>> ht2;
ht.Insert(2);
ht.Insert(4);
ht.Insert(14);
ht.Insert(24);
ht.Insert(26);
ht.Insert(16);
ht.Erase(14);
ht.Erase(2);
CLOSEHASH::HashData<int>* data = ht.Find(4);
}
void TestOpenHash1()
{
using OPENHASH::_Hash;
OPENHASH::HashTable<int, int, SetKeyOfT<int>, _Hash<int>> ht;
//OPENHASH::HashTable<int, int, MapKeyOfT<int, int>> ht2;
ht.Insert(2);
ht.Insert(4);
ht.Insert(14);
ht.Insert(24);
ht.Insert(26);
ht.Insert(16);
ht.Erase(14);
ht.Erase(2);
OPENHASH::HashNode<int>* Node = ht.Find(4);
/*ht2.Insert(make_pair(1,1));
ht2.Insert(4);
ht2.Insert(14);
ht2.Insert(24);
ht2.Insert(26);
ht2.Insert(16);
ht2.Erase(14);
ht2.Erase(2);
HashNode<int>* Node2 = ht2.Find(4);*/
}
void TestOpenHash2()
{
using OPENHASH::_Hash;
OPENHASH::HashTable<string, string, SetKeyOfT<string>,_Hash<string>> ht;
ht.Insert("sort");
ht.Insert("futile");
ht.Insert("plight");
cout << ht.HashFunc("abcd") << endl;
cout << ht.HashFunc("aadd") << endl;
}
int main()
{
//TestCloseHash();
//TestOpenHash1();
//TestOpenHash2();
//mz::test_unordered_set();
mz::test_unordered_map();
return 0;
}
MyUnorderedSet.h:
#pragma once
#include"HashTable.h"
using namespace OPENHASH;
namespace mz
{
using OPENHASH::_Hash;
template<class K, class Hash = _Hash<K>>
class unordered_set
{
struct SetKOfT
{
const K & amp; operator()(const K & amp; k)
{
return k;
}
};
public:
//Adding typename tells the compiler that this is a type. Let me go through it first, and then look for it after it is instantiated.
//Because the template has not been instantiated, it does not accept you using a type in the template, so typename must be used.
typedef typename HashTable<K, K, SetKOfT, Hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const K & amp; k)
{
return _ht.Insert(k);
}
private:
HashTable<K, K, SetKOfT, Hash> _ht;
};
void test_unordered_set()
{
unordered_set<int> s;
s.insert(1);
s.insert(5);
s.insert(4);
s.insert(2);
unordered_set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
+ + it;
}
cout << endl;
}
}
MyUnorderedMap.h:
#pragma once
#include"HashTable.h"
using namespace OPENHASH;
namespace mz
{
using OPENHASH::_Hash;
template<class K, class V, class Hash = _Hash<K>>//General template parameters are controlled by the upper layer
class unordered_map
{
struct MapKOfT
{
const K & amp; operator()(const pair<K, V> & amp; kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<K,V>, MapKOfT, Hash>::iterator iterator;
iterator begin()
{
return _ht.begin();
}
\t\t
iterator end()
{
return _ht.end();
}
pair<iterator, bool> insert(const pair<K, V> & amp; kv)
{
return _ht.Insert(kv);
}
V & amp; operator[](const K & amp; key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<K, V>, MapKOfT, Hash> _ht;//The bottom layer is a hash table
};
void test_unordered_map()
{
unordered_map<string, string> dict;
dict.insert(make_pair("factual", "real"));
dict.insert(make_pair("fringe", "violation"));
dict.insert(make_pair("intermittent", "intermittent"));
dict["prerequisite"] = "prerequisite";
dict["reduce to"] = "at";
//unordered_map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
+ + it;
}
cout << endl;
}
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56870 people are learning the system