https://blog.csdn.net/yangxuan0261/article/details/52090128
深入剖析 std::unordered_map 的实现原理之 Hash冲突、退化
c++ 实现hashmap - myd620 - 博客园 (cnblogs.com) 好文章
// gnu 实现template<typename _Key, typename _Tp,typename _Hash = hash<_Key>,typename _Pred = equal_to<_Key>,typename _Alloc = allocator<std::pair<const _Key, _Tp>>>class unordered_map{typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc> _Hashtable;_Hashtable _M_h; // 内部的唯一成员变量： hashtable//... }c++ vector的底层实现
c++简单String类实现
最终实现unordered_map的代码：
#include<bits/stdc++.h>
using namespace std;template<class Key, class Value>
class HashNode{public:Key _key;Value _value;HashNode* next;HashNode(Key key, Value value){_key=key;_value=value;next=NULL;}~HashNode(){}
};template<class Key, class Value, class HashFunc>
class HashMap
{public:HashMap(int size);~HashMap();void insert(const Key& key, const Value& value);bool del(const Key& key);Value& find(const Key& key);Value& operator [](const Key& key);private:HashFunc hash;HashNode<Key, Value> **table;//因为是数组，所以两个*，一个*代表指针数组int _size;Value valueNull;
};template<class Key, class Value, class HashFunc>
HashMap<Key, Value, HashFunc>::HashMap(int size):_size(size)
{table=new HashNode<Key, Value>* [size];for(int i=0; i<size; i++){table[i] = NULL;}
}template<class Key, class Value, class HashFunc>
HashMap<Key, Value, HashFunc>::~HashMap()
{for(int i=0; i<_size; i++){HashNode<Key, Value>* node = table[i];while(node){HashNode<Key, Value> *tmp=node;node = node->next;delete tmp;}}delete table;
}template<class Key, class Value, class HashFunc>
void HashMap<Key, Value, HashFunc>::insert(const Key& key, const Value& value)
{int index = hash(key)%_size;HashNode<Key, Value> *node = table[index];while(node){if(node->_key == key){return;//insert以第一次插入的value为准}node = node->next;}node = new HashNode<Key, Value>(key, value);node->next=table[index];table[index]=node;
}template<class Key, class Value, class HashFunc>
Value& HashMap<Key, Value, HashFunc>::find(const Key &key)
{int index = hash(key) % _size;HashNode<Key, Value> *node = table[index];while(node){if(node->_key == key){return node->_value;}node = node->next;}node = new HashNode<Key, Value>(key,valueNull);node->next = table[index];table[index] = node;return table[index]->_value;
}template<class Key, class Value, class HashFunc>
Value& HashMap<Key, Value, HashFunc>::operator[](const Key& key)
{return find(key);
}template<class Key, class Value, class HashFunc>
bool HashMap<Key, Value, HashFunc>::del(const Key& key)
{int index = hash(key) % _size;HashNode<Key, Value> *node = table[index];HashNode<Key, Value> *preNode = NULL;while(node){if(node->_key == key){if(preNode == NULL){table[index] = node->next;}else{preNode->next = node->next;}delete node;return true;}else{preNode = node;node = node->next;}}return false;
}class HashFunc
{public:int operator()(const string& key){int hash=0;for(int i = 0; i < key.size(); i++){hash=hash<<7^key[i];}return (hash&0x7fffffff);}
};int main()
{HashMap<string, string, HashFunc> hashmap(10);hashmap.insert("aaaa","1111");hashmap.insert("bbbb","2222");cout<<"after insert:"<<endl;cout<<hashmap.find("aaaa")<<endl;cout<<hashmap.find("bbbb")<<endl;if(hashmap.del("aaaa")){cout<<"remove is ok!"<<endl;}cout<<hashmap.find("aaaa")<<endl;hashmap["cccc"]="3333";hashmap["dddd"]="4444";cout<<"after = assign:"<<endl;cout<<hashmap["cccc"]<<endl;cout<<hashmap.find("dddd")<<endl;return 0;
}
最初版代码：
#include<bits/stdc++.h>
using namespace std;template<class Key, class Value>
class HashNode
{
public:Key _key;Value _value;HashNode *next;HashNode(Key key, Value value){_key = key;_value = value;next = NULL;}~HashNode(){}/*HashNode& operator=(const HashNode& node){_key = node._key;_value = node._value;next = node.next;return *this;}*/
};template <class Key, class Value, class HashFunc>
class HashMap
{
public:HashMap(int size);~HashMap();bool insert(const Key& key, const Value& value);bool del(const Key& key);Value& find(const Key& key);Value& operator [](const Key& key);private:HashFunc hash;//EqualKey equal;HashNode<Key, Value> **table;unsigned int _size;Value ValueNULL;
};template <class Key, class Value, class HashFunc>
HashMap<Key, Value, HashFunc>::HashMap(int size) : _size(size),hash()
{table = new HashNode<Key, Value>*[_size];for (unsigned i = 0; i < _size; i++)table[i] = NULL;
}template <class Key, class Value, class HashFunc>
HashMap<Key, Value, HashFunc>::~HashMap()
{for (unsigned i = 0; i < _size; i++){HashNode<Key, Value> *currentNode = table[i];while (currentNode){HashNode<Key, Value> *temp = currentNode;currentNode = currentNode->next;delete temp;}}delete table;
}template <class Key, class Value, class HashFunc>
bool HashMap<Key, Value, HashFunc>::insert(const Key& key, const Value& value)
{int index = hash(key)%_size;HashNode<Key, Value> * node = new HashNode<Key, Value>(key,value);node->next = table[index];table[index] = node;return true;
}template <class Key, class Value, class HashFunc>
bool HashMap<Key, Value, HashFunc>::del(const Key& key)
{unsigned index = hash(key) % _size;HashNode<Key, Value> * node = table[index];HashNode<Key, Value> * prev = NULL;while (node){if (node->_key == key){if (prev == NULL){table[index] = node->next;}else{prev->next = node->next;}delete node;return true;}prev = node;node = node->next;}return false;
}template <class Key, class Value, class HashFunc>
Value& HashMap<Key, Value, HashFunc>::find(const Key& key)
{unsigned index = hash(key) % _size;if (table[index] == NULL){HashNode<Key, Value> * node = new HashNode<Key, Value>(key,ValueNULL);node->next = table[index];table[index] = node;//cout<<"---2"<<endl;return table[index]->_value;}else{HashNode<Key, Value> * node = table[index];while (node){if (node->_key == key)return node->_value;node = node->next;}}
}template <class Key, class Value, class HashFunc>
Value& HashMap<Key, Value, HashFunc>::operator [](const Key& key)
{//cout<<"---1"<<endl;return find(key);
}class HashFunc
{
public:int operator()(const string & key ){int hash = 0;for(int i = 0; i < key.length(); ++i){hash = hash << 7 ^ key[i];}return (hash & 0x7FFFFFFF);}
};class EqualKey
{
public:bool operator()(const string & A, const string & B){if (A.compare(B) == 0)return true;elsereturn false;}
};int main()
{HashMap<string, string, HashFunc> hashmap(100);hashmap.insert("hello", "world");hashmap.insert("why", "dream");hashmap.insert("c++", "good");hashmap.insert("welcome", "haha");cout << "after insert:" << endl;cout << hashmap.find("welcome").c_str() << endl;cout << hashmap.find("c++").c_str() << endl;cout << hashmap["why"].c_str() << endl;cout << hashmap["hello"].c_str() << endl;if (hashmap.del("hello"))cout << "remove is ok" << endl; //remove is okcout << hashmap.find("hello").c_str() << endl; //not exist print NULLhashmap["what"] = "love";cout << hashmap["what"].c_str() << endl;hashmap["where"] = "beijing";cout << hashmap["where"].c_str() << endl;cout<<"------"<<hashmap["you"]<<endl;cout<<"#######"<<hashmap["what"]<<endl;return 0;
}
