[Data Structure] hash table

HashTable-Hash Table/Hash Table is a data structure that directly accesses the memory storage location based on the key.
It uses a key value function to map the required data to the position in the table to access the data. This mapping function is called a hash function, and the array that stores the records is called a hash table.
Several methods of constructing a hash table
1. Direct addressing method-take a linear function of the keyword as the hash address, Hash (Key) = Key or Hash (Key) = A*Key + B, A and B are constants.
2. Divide and leave the remainder method-take the key value divided by a number p not greater than the hash table length m as the hash address. Hash (Key) = Key% P.
3. Square taking the middle method
4. Folding method
5. Random number method

6. Mathematical analysis method

Here realizes the construction of dividing and leaving remainder method Hash table

Except the remainder function

size_t _HashFunc (const K& key) {return key%_table.size(); }

Implement hash table,

#include#include #include using namespace std;enum Status{ EMPTY, EXIST, DELETE,};templatestruct HashTableNode{ K _key; V _value; Status _status; HashTableNode(const K& key=K(),const V& value=V()) :_key(key) ,_value(value) ,_status(EMPTY) () };templateclass HashTable{ typedef HashTableNode Node;public: HashTable() :_size(0) {_table.resize(_GetNextPrime(0));} ~HashTable() {} bool Insert(const K& key,const V& value) {Checksize(); size_t index=_HashFunc(key); while (_table[index]._status==EXIST) {if(_table[index]._key= =key) return false; ++index; if(index==_table.size()) index=0;} _table[index]._key=key; _table[index]._value=value; _table[index]._status =EXIST; _size++; return true;} Node* Find(const K& key) {if(_table.empty()) {return NULL;} for (size_t i=0;i<_table.size();i++) {if (_table[i]._status==EXIST&&_table[i]._key==key) return &_table[i]; else continue;} return NULL;} bool Remove(const K& key) {if (_table.empty()) { return false;} Node* del=Find(key); if(del->_status==EXIST) {del->_status=DELETE; return true;} else return false;} void display() {if(_table.size ()==0) {return;} for (size_t i=0;i<_table.size();i++) {cout<<" key:"<<_table[i]._key<<" value:"< <_table[i]._value<<" status:"<<_table[i]._status<=8) {size_t newsize=_GetNextPrime(_table.size()); H ashTable hash; hash._table.resize(newsize); for (size_t i=0;i<_table.size();i++) {if(_table[i]._status==EXIST) {hash.Insert(_table[i ]._key,_table[i]._value);}} this->Swap(hash);}} 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,1996613ul, 391241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,50331653ul,100663319ul,20131061112ul457ul,402653ul,100663319ul,20131061112ul ,429496729ul }; for (size_t i=0;i<_PrimeSize;i++) {if(_PrimeList[i]>num) return _PrimeList[i];} return 429496729ul;} void Swap(HashTable& hs) {_table.swap(hs._table); swap(_size,hs._size); }protected: vector _table; size_t _size;}; void testHash(){ HashTable hash; for (size_t i =0;i<20;i++) {hash.Insert(i,i);} for (size_t i=10;i<30;i++) {hash.Insert(i,i);} hash.display(); hash.R emove(3); hash.Remove(7); hash.display();}