当前位置：网站首页>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;
}
}
}
边栏推荐
- TypeScript类型声明文件（三）
- Review of MySQL (10): three paradigms of database
- 在思科模擬器Cisco Packet Tracer實現自反ACL
- The difference between user status and system status in CRM
- 2022.6.12-----leetcode. eight hundred and ninety
- Mysql -＞＞符号用法 Json相关
- To understand Devops, you must read these ten books!
- 机器学习在美团配送系统的实践：用技术还原真实世界-笔记
- VirtualLab basic experiment tutorial -6 Blazed grating
- 用一个性能提升了666倍的小案例说明在TiDB中正确使用索引的重要性
猜你喜欢
Virtual Lab Basic Experiment tutoriel - 4. Diffraction à fente unique
Typescript common types (I)
![Free measurement of rectangular card [manual drawing ROI] Based on Halcon](/img/c5/d9109ed4024aff521e1788c63bff4e.png)
Free measurement of rectangular card [manual drawing ROI] Based on Halcon
Introduction to reinforcement learning and analysis of classic items 1.3
Machine learning series (5): Naive Bayes
Partial scratch and corrosion detection of bolts and screws based on Halcon
VirtualLab basic experiment tutorial -4 Single slit diffraction
在思科模拟器Cisco Packet Tracer实现自反ACL
Gd32f4xx controls dgus touch keys
深圳3月14日起全市停工停业7天居家办公心得|社区征文
随机推荐
Pytest automated testing framework (II)
JS quick sort
JS dichotomy
GD32F4xx 与符合DLT645的电能表通信_2
MySQL数据库（28）：变量 variables
HTTP cache ＜ strong cache and negotiation cache ＞
The difference between user status and system status in CRM
VirtualLab基礎實驗教程-4.單縫衍射
Review of MySQL (V): Joint table query and sub query
js两数之和
Basic SQL statement - select (single table query)
Gossip about the source code of redis 89
VirtualLab basic experiment tutorial -4 Single slit diffraction
Review of MySQL (4): sorting operation
Title 37: sorting 10 numbers
C language practice (4) -- multiplication and division of large numbers
"Big fat • small lesson" - talk about big file segmentation and breakpoint sequel
JS中的栈（含leetcode例题）＜持续更新~＞
Introduction to reinforcement learning and analysis of classic items 1.3
Common methods and examples of defect detection based on Halcon