当前位置：网站首页>Hash hash
Hash hash
2022-06-12 18:35:00 【This one again】
List of articles
unordered_set
#include<iostream>
#include<vector>
#include<unordered_set>
#include<set>
#include<time.h>
using namespace std;
void test_time()
{
int n = 1000000;
vector<int> v;
srand(time(0)); // Initialize the random number generator
for (int i = 0; i < n; ++i)
{
v.push_back(rand()); // Random number generator
}
set<int> s;
size_t begin1 = clock();// The number of milliseconds when the process reaches here after running
for (auto e : v)
{
s.insert(e);
}
size_t end1 = clock();
cout << "set : " << end1 - begin1 << endl;
unordered_set<int> us;
size_t begin2 = clock();
for (auto e : v)
{
us.insert(e);
}
size_t end2 = clock();
cout << "unordered_set : " << end2 - begin2 << endl;
}
int main()
{
test_time();
}
set : 9065
unordered set : 3835
961. In length 2N Find duplicates in the array of N Secondary elements
An array of integers nums , The array has the following properties :
nums.1ength == 2* n .
nums contain n + 1 A different element rums There is exactly one element repeating in n Time
Find and return duplicates n The next element .
Input ：nums = [1,2,3,3] Output ：3
349. Intersection of two arrays
Two arrays nums1 and nums2, Return their intersection . Each element of the output must be unique .
Input : nums1 = [1,2,2,1],nums2 = [2,2] Output :[2]
387. The first unique character in the string
character string s, Find its first non repeating character , And return its index . If it doesn't exist , Then return to -1.
s Contains only lowercase letters , Input :s = “leetcode” Output :0
class Solution {
public:
int firstUniqChar(string s){
int hash[26] = {
0 };//26 Letters
for (auto ch : s)//O(N)
{
hash[ch - 'a']++;// Initialize to 0, Relative mapping in hash mode
}
for (int i = 0; i < s.size(); ++i)//O(N)
{
if (hash[s[i] - 'a'] == 1)//O(1)
//[] The different meaning of ： The innermost layer []: Function call , Outer layer []: Array dereference
return i;
}
return -1;
}
};
STL The algorithm in is seldom used in practice
Closed hash Linear detection
set-> HashTable<K, K>
map<K, V>-> HashTable<K, pair<K, V>>
HashTable.h:
namespace Close
{
enum State
{
EMPTY,
EXIST,
DELETE
// The meaning of deleting a state ： Avoid interfering with subsequent searches ; Pseudo delete ： No value deleted , Just change the status , Do not change the structure
};// enumeration ： Set of constants
template<class T>
struct HashNode// There are values in the node 、 state
{
State _state = EMPTY;// Built in types are initialized with default values
T _t;
};
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
// Template specialization
template<>
struct Hash < string >
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash = hash * 131 + ch; // String hash algorithm
}
return hash;
}
};
// Use red and black trees to encapsulate map and set It's the same , The type of storage controlled by the second template parameter is K, still pair<const K,V>
template<class K, class T, class HashFunc = Hash<K>>
//K yes string when , Need to put K Convert to plastic , Use template specialization
class HashTable
{
public:
bool Insert(const T& t)
{
if (_tables.size() == 0 || _size * 10 / _tables.size() == 7)// or
{
size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;// Simply copy the original data to the new space load factor Load factor
//newsize It is not right , Data that may have been in conflict , Due to the expansion of space , It is no longer a conflict ; We should open up a space , Recalculate the above data , Then put it in this space , Then release the original space , Open a new one 2 Times vector
/* Method 1：vector<hashnode<t>> newtables; newtables.resize(newsize); Data on original space _tables, Recalculate and put it in the corresponding new space for (size_t i = 0; i < _tables.size(); ++i) { if (_tables[i]._state == exist) { // The linear probe finds the position in the new table } } newtables.swap(_tables);*/
HashTable<K, T, HashFunc> newht;// Method 2： Define hash table objects
newht._tables.resize(newsize);// Class through objects
for (auto& e : _tables)
{
// Traverse the old table , Old table this No change , Once it is changed, the mapping relationship will be disordered
if (e._state == EXIST)
{
newht.Insert(e._t); // Insert data into newht, Reuse conflict detection logic
// Just do it all over again , Recalculate position , In a new table , No capacity increase will occur again , Enough space
}
}
_tables.swap(newht._tables);
}
// Data redundancy is not allowed
HashNode<T>* ret = Find(t);
if (ret)
return false;
HashFunc hf;// functor HashFunc Purpose ： Turn into int,
// At the beginning , There are no elements in your hash table , So there will be modules 0, Error situation
size_t start = hf(t) % _tables.size();
size_t index = start; // It is convenient to modify during secondary detection
// Linear detection , Find an empty place
size_t i = 1;
while (_tables[index]._state == EXIST) // We should look for the next empty position
{
index = start + i;
index %= _tables.size();
++i;
}
// Jumping out of a loop is two things 1.EMPTY 2. DELETE In both cases, you can put values in
_tables[index]._t = t;// Put the value in
_tables[index]._state = EXIST;// modify state
_size++;
return true;
}
HashNode<T>* Find(const K& key)//vecter Every data in the is HashNode
{
HashFunc hf;
size_t start = hf(key) % _tables.size();// call string Of operator(), To int After that, we can take the model and calculate
size_t index = start;
size_t i = 1;
while (_tables[index]._state != EMPTY)
{
if (_tables[index]._t == key && _tables[index]._state == EXIST) // Because the value that may be found is deleted
{
return &_tables[index];//_tables Every data in the is node, Address fetch , The return address
}
index = start + i;
index %= _tables.size();
++i;
}
return nullptr;
}
bool Erase(const K& key)
{
HashNode<T>* ret = Find(key);
if (ret == nullptr)
{
return false;
}
else
{
// Pseudo delete
ret->_state = DELETE;
return true;
}
}
private:
vector<HashNode<T>> _tables;// Custom type ： Adjust your copy structure ; Deep copy by vector complete ： Benefits of using libraries , Space by vector The open , Out of the scope, call your own destructor （ Compiler generated by default ）, Each location stores HashNode;vector Store nodes
size_t _size = 0; // Number of valid data , There is no space , This is not initialization , Built in type ： Value copy
};
}
void TestHashTable()
{
HashTable<int, int> ht;// Itself is int when , There is no need to pass the first 3 Parameters
ht.Insert(5);
ht.Insert(15);
ht.Insert(16);
ht.Insert(17);
ht.Insert(25);
ht.Insert(35);
ht.Insert(45);
ht.Insert(55);
struct StrHash// functor
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
}
return hash;
}
};
HashTable<string, string, StrHash> strht;// Shaping is a finite number , The string is infinite , Method 1： functor
HashTable<string, string> strht;// Method 2： Template specialization , If there is specialization, use specialization
strht.Insert("sort");
strht.Insert("insert");
#include "HashTable.h"
#include "unordered_map.h"
#include "unordered_set.h"
int main()
{
//testop();
//Close::TestHashTable();
bit::test_unordered_set();
return 0;
}
Hash Hash bucket
Complexity ：O（1）
HashTable.h：
namespace Open
{
size_t GetNextPrime(size_t prime)
{
static 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
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}
return primeList[i];
}
template<class T>
struct HashLinkNode
{
T _t;
HashLinkNode<T>* _next;
HashLinkNode(const T& t)
: _t(t)
, _next(nullptr)
{
}
};
template<class K>
struct Hash
{
size_t operator()(const K& key)
{
return key;
}
};
// specialized
template<>
struct Hash < string >
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
//hash += ch;
hash = hash * 131 + ch;
}
return hash;
}
};
// Pre declaration of class template , reason ： When constructing iterators , need HashTable, But the template is not specialized , Can't find
template<class K, class T, class KeyOfT, class hash>
class HashTable;
// For encapsulated iterators ,++ Will go to the bottom of the barrel 1 Nodes , When there are no more nodes in the bucket , Need to go to the next 1 a hash Mapping location
template<class K, class T, class Ref,class Ptr ,class KeyOfT, class hash>
struct HashIterator
{
//friend template class HashTable;// error ： Friends are reversed , Not here
typedef HashIterator<K, T, Ref,Ptr,KeyOfT, hash> Self;
typedef HashLinkNode<T> Node;
Node* _node;
HashTable<K, T, KeyOfT, hash>* _pht;
// Pointer to hash table ：_pht, Purpose ： When traversing the hash table , When 1 Pass traversal completed , Find it 1 A bucket that needs to be traversed
HashIterator(Node* node, HashTable<K, T, KeyOfT, hash>* pht)
// Constructors : Pass on node、 Hashtable HashTable; Pass on vectcor complex ,
:_node(node)
, _pht(pht)
{
}
Ref operator*()
{
return _node->_t;
}
Ptr operator->()
{
return &(_node->_t);
}
bool operator!=(const Self& s) const // Common object 、const All objects can be adjusted
{
return _node != s._node;
}
// about operator++（ In front of ++） Come on , After adding, the pointer of an iterator is still returned
//1. The current bucket still has data , Continue to go
//2. The current bucket has no data , Jump to the next bucket , From the first
Self operator++()//（ Hashtable ） A one-way iterator does not --
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfT kot;
// A barrel has been used up , Find the next bucket , With the current bucket, we can calculate index Location , Need one hash surface
// To calculate the index The original position of , It's all gone , Calculate from his next position
size_t index = _pht->HashFunc(kot(_node->_t),_pht->_tables.size());// The size of the table _pht->_tables.size()
++index;
while (index < _pht->_tables.size())
{
if (_pht->_tables[index])
{
// This bucket is not empty , Start traversing the bucket ; There is no 1 Pointers to nodes
_node = _pht->_tables[index];
break;// Find it 1 It's a bucket
}
else
{
++index;
}
}
//while The end is possible 1.break Jump out 2. The cycle is over , Distinguish between the two situations
if (index == _pht->_tables.size())
{
// Not found 1 A barrel
_node = nullptr;
}
}
return *this;// Return is yourself
}
};
template<class K,class T,class KeyOfT,class hash = Hash<K>>
class HashTable
{
typedef HashLinkNode<T> Node;
friend struct HashIterator < K, T, T&, T*, KeyOfT, hash > ;
public:
typedef HashIterator<K, T, T&,T*,KeyOfT, hash> Iterator;
typedef HashIterator<K, T, const T&, const T*, KeyOfT, hash> Const_Iterator;
Iterator Begin()// Get the first 1 In a bucket 1 Number
{
for (size_t i = 0; i < _tables.size(); ++i)
{
// I don't know 1 Where are the barrels , We need to find number one 1 A barrel
if (_tables[i])// If it is not empty, the... Is found 1 A barrel
{
//_tables[i]: Node pointer , With this structure 1 An iterator
return Iterator(_tables[i],this); //this： Point to HashTable The pointer to
}
}
// If there is no data in the hash table , Then the return nullptr It's also true
return End();
}
Iterator End()
{
return Iterator(nullptr,this);
}
size_t HashFunc(const K& key, size_t n)// Calculate subscript
{
hash hf;
size_t ki = hf(key);//K To int
return ki % n;
}
pair<Iterator, bool> Insert(const T& t)
{
// Hash / The hash bucket load factor is controlled at 1, If it's full, add , Higher space utilization
// I have many conflicts , It will only affect yourself , Do not affect others
KeyOfT kot;
// Control the load factor == 1 Increase capacity when
if (_size == _tables.size())
{
size_t newsize = GetNextPrime(_tables.size());// Get prime number , Effective verification can improve efficiency
vector<Node*> newtables;
newtables.resize(newsize,nullptr);
// Loop through each hash bucket , Reconnect
for (size_t i = 0; i < _tables.size(); ++i)
{
// The nodes in the old table are directly removed and hung in the new table
Node* cur = _tables[i];
while (cur)
{
// Select head insert , When inserting the end of a single linked list , Tail finding required
Node* next = cur->_next;// Save in advance cur Of next, prevent cur Be linked to the new table , Cannot find... In old table next
size_t index = HashFunc(kot(cur->_t),newtables.size());// Recalculate the position in the new table created
cur->_next = newtables[index];// Head insertion
newtables[index] = cur;
cur = next;
}
_tables[i] = nullptr;// The old table pointer points to null
}
newtables.swap(_tables);
}// All data to be reinserted 1 Time
// You need to get the position of the subscript
size_t index = HashFunc(kot(t),_tables.size());//kot： hold T Inside key extracted , And then to int
// do map Of key Compare the size of the support 、 do unordered_map Of key To support mold taking
// Key value redundancy is not allowed , lookup t Is here or not , Find the location first , Then we are traversing the entire hash bucket
Node* cur = _tables[index];
while (cur)
{
if (kot(cur->_t) == kot(t))
{
// Return if present , Insert if it doesn't exist
return make_pair(Iterator(cur,this), false);
}
cur = cur->_next;
}
// The hash table initially stores NULL, When there is a hook at the bottom , The stored will be changed to 1 The address of the node
// Insert the head into the linked list bucket
Node* newnode = new Node(t);
newnode->_next = _tables[index];
_tables[index] = newnode;
return make_pair(Iterator(newnode,this), true);
}
//Find It is through Key Looking for
Iterator Find(const K& key)
{
KeyOfT kot;
size_t index = HashFunc(key,_tables.size());
Node* cur = _tables[index];
// Now? hash Position found in table , And then traverse the whole hash bucket
while (cur)
{
if (kot(cur->_t) == key)
{
return Iterator(cur,this);
}
cur = cur->_next;
}
return End();
}
bool Earse(const K& key)
{
KeyOfT kot;
size_t index = HashFunc(key, _tables.size());// Mapping location index
// Delete a single linked list
Node* prev = nullptr;
Node* cur = _tables[index];
// Now? hash Position found in table , And then traverse the whole hash bucket
while (cur)
{
if (kot(cur->_t) == key)
{
// Just delete
if (prev == nullptr)
{
// It indicates that the header is deleted
_tables[index] = cur->_next; // The first linked list is found directly
}
else
{
prev->_next = cur->_next;
}
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
vector<Node*> _tables;//vector Li Cun Node* Node pointer 
size_t _size = 0;// Number of valid data
};
}
unordered_set.h
Based on open hash
#pragma once
#include "HashTable.hpp"
//map and set equally , There is nothing in itself , Various operations are implemented on the basis of red black tree
//unordered_set and unordered_map They are all hashing HashTable Based on the
namespace bit
{
template<class K,class hash = Open::Hash<K>>
class unordered_set
{
struct SetKOfT
{
const K& operator()(const K& k)
{
return k;
}
};
public:
typedef typename Open::HashTable<K, K, SetKOfT, hash>::Iterator iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
iterator find(const K& key)
{
return _t.Find(key);
}
bool earse(const K& key)
{
return _t.Earse(key);
}
pair<iterator, bool> insert(const K& k)
{
return _t.Insert(k);
}
private:
Open::HashTable<K, K, SetKOfT, hash> _t;
};
void test_unordered_set()
{
bit::unordered_set<int> us;
us.insert(1);
us.insert(54);
us.insert(58);
us.insert(59);
us.insert(21);
us.insert(22);
us.insert(23);
us.insert(24);
for (auto& e : us)
{
cout << e << " ";
}
cout << endl;
unordered_set<int>::iterator it = us.find(22);
cout << *it << endl;
us.earse(24);
us.earse(21);
us.earse(22);
for (auto& e : us)
{
cout << e << " ";
}
cout << endl;
}
}
unordered_map.h
#pragma once
#include"HashTable.hpp"
namespace bit
{
template<class K,class V,class hash = Open::Hash<K>>// Based on open hash
class unordered_map
{
struct MapKOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename Open::HashTable<K, pair<const K, V>, MapKOfT, hash>::Iterator iterator;
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _ht.Insert(kv);
}
iterator begin()
{
return _ht.Begin();
}
iterator end()
{
return _ht.End();
}
iterator find(const K& key)
{
return _ht.Find(key);
}
bool earse(const K& key)
{
return _ht.Earse(key);
}
V& operator[](const K& key)
{
pair<iterator,bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
Open::HashTable<K, pair<const K, V>, MapKOfT,hash> _ht;
};
void test_unordered_map()
{
bit::unordered_map<int, int> um;
um.insert(make_pair(1, 1));
um.insert(make_pair(2, 1));
um.insert(make_pair(3, 1));
unordered_map<int,int>::iterator it = um.begin();
while (it != um.end())
{
cout << it->first << ":"<<it->second<<endl;
++it;
}
bit::unordered_map<string,string> dict;
dict["hash"] = " Hash ";
dict["sort"] = " Sort ";
dict["insert"] = " Insert ";
dict["find"] = " lookup ";
for (auto& e : dict)
{
cout << e.first << ":" << e.second << endl;
}
cout <<endl;
dict.earse("hash");
dict.earse("find");
for (auto& e : dict)
{
cout << e.first << ":" << e.second << endl;
}
}
}
边栏推荐
- Gospel of audio and video developers, rapid integration of AI dubbing capability
- VirtualLab基础实验教程-4.单缝衍射
- Title 68: there are n integers, so that the previous numbers are moved backward m positions, and the last m numbers become the first m numbers
- Difference between rxjs of() and of ({})
- Title 54: take 4 ~ 7 bits of an integer a from the right end.
- 2022.6.12-----leetcode. eight hundred and ninety
- Still using Microsoft office, 3 fairy software, are you sure you don't want to try?
- Leetcode491 increasing subsequence
- 机器学习系列（5）：朴素贝叶斯
- Gossip about the 88 of redis source code
猜你喜欢
C language practice (4) -- multiplication and division of large numbers
GD32F4xx控制DGUS 变量显示
Machine learning series (3): logistic regression
VirtualLab basic experiment tutorial -4 Single slit diffraction
MYSQL:Expression ＃4 of SELECT list is not in GROUP BY clause and contains nonaggregated column
The difference between user status and system status in CRM
Review of MySQL (I): go deep into MySQL
VirtualLab基础实验教程-4.单缝衍射
迄今微软不同时期发布的SQL Server各版本之间的大致区别，供参考查阅
机器学习系列（5）：朴素贝叶斯
随机推荐
js两数之和
Review of MySQL (10): three paradigms of database
Introduction to reinforcement learning and analysis of classic items 1.3
VirtualLab basic experiment tutorial -6 Blazed grating
Basic SQL statement - select (single table query)
SCI Writing - Methodology
torch.where的新用法（很老但是大家忽略的用法）
GD32F4xx控制DGUS触控按键
js快速排序
JS get the start and end dates of this week according to the nth week of the N year
VirtualLab基础实验教程-5.泊松亮斑
Partial scratch and corrosion detection of bolts and screws based on Halcon
leetcode 300. Longest increasing subsequence
Comparison of disk mapping tools for network disk and object cloud storage management
机器学习系列（3）：Logistic回归
Review of MySQL (VIII): Transactions
配送交付时间轻量级预估实践-笔记
美团智能配送系统的运筹优化实战-笔记
Summary of interview questions
Eve-ng installation (network device simulator)