unordered_set/map 实现

####载荷因子
??闭散列表的载荷因子一般为0.75再超过可能会冲突越来越多，开散列表一般为1。
####闭散列

#include<iostream>
#include<vector>
using namespace std;
enum State
{EMPTY = 1,EXITS = 2,DELETE = 3,
};
const int _PrimeSize = 28;
static const unsigned int _PrimeList[_PrimeSize] =
{53ul, 97ul, 193ul, 389ul, 769ul,1543ul, 3079ul, 6151ul, 12289ul, 24593ul,49157ul, 98317ul, 196613ul, 393241ul, 786433ul,50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,1610612741ul, 3221225473ul, 4294967291ul
};
template<class K, class V>
struct HashNode
{K _key;V _value;State _state;HashNode():_state(EMPTY){}
};template<class K>
struct __HashFunc
{size_t operator()(const K& key){return key;}
};template<>
struct __HashFunc<string>
{static size_t BKDRHash(const char * str){unsigned int seed = 131; // 31 131 1313 13131 131313 unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF);}size_t operator()(const string& key){return BKDRHash(key.c_str());}
};template<class K, class V,class HashFunc=__HashFunc<K>>
class HashTable
{typedef HashNode<K,V> Node;
public:HashTable():_size(0), _tables(5){}bool Insert(const K& key, const V& value,bool flag=true){CheckCap();size_t index = _HashFunc(key); // index 的值是调用HashTable的成员函数size_t start = index;//得到的不会越界int i = 0;while (_tables[index]._state == EXITS&&_tables[index]._key!=key){if (flag){index = start + (1 << i++);}else{index++;}if (index >= _tables.size())index %= _tables.size();}if (_tables[index]._key == key)return false;_tables[index]._key = key;_tables[index]._value = value;_tables[index]._state = EXITS;_size++;return true;}Node* Find(const K& key){size_t index = _HashFunc(key);while (_tables[index]._key != key && (_tables[index]._state == DELETE || _tables[index]._state == EXITS)){index++;if (index == _tables.size())index = 0;}if (_tables[index]._key == key&&_tables[index]._state==EXITS)return &_tables[index];elsereturn nullptr;}bool Remove(const K& key){size_t index = _HashFunc(key);while (_tables[index]._key != key && (_tables[index]._state == DELETE || _tables[index]._state == EXITS)){++index;if (index == _tables.size())index == 0;}if (_tables[index]._state == EMPTY || _tables[index]._state==DELETE)return false;else{_tables[index]._state = DELETE;return true;}}
protected:unsigned int Getprimer(unsigned int x){for (auto&i : _PrimeList){if (x < i)return i;}return x;}void CheckCap(){if (_size * 10 / _tables.size()>7){HashTable<K, V, HashFunc> newtable;newtable._tables.resize(Getprimer(_tables.size()));for (auto & i : _tables){if (i._state == EXITS)newtable.Insert(i._key,i._value);}newtable._tables.swap(_tables);}}size_t _HashFunc(const K&key){return HashFunc()(key) % _tables.size();}
private:vector<Node> _tables;size_t _size;
};

###开散列

template<class K>
struct __HashFunc
{size_t operator()(const K& key){return key;}
};template<>
struct __HashFunc<string>
{static size_t BKDRHash(const char * str){unsigned int seed = 131; // 31 131 1313 13131 131313 unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF);}size_t operator()(const string& key){return BKDRHash(key.c_str());}
};template<class ValueType>
struct HashNode
{ValueType _valueField;HashNode<ValueType> * _next;HashNode(const ValueType& valueField):_valueField(valueField), _next(NULL){}
};
template<class ValueFiled>
struct KeyofValue
{auto operator()(ValueFiled value) ->decltype(value.first){return  value.first;}
};
template<class Key,class V, class ValueofKey, class HashFunc>
class HashTable
{typedef  V ValueType;typedef HashNode<V> Node;public:HashTable():_tables(Getprimer(0)),_size(Getprimer(0)){}bool Insert(const ValueType& valueField){ValueofKey Keyofvalue;int key = Keyofvalue(valueField);int index = _HashFunc(key);//调用成员函数_HashFunc完成不会越界Node* pCur = _tables[index];while (pCur){if (Keyofvalue(pCur->_valueField)==key)return false;}Node * NewNode = new Node(valueField);NewNode->_next = _tables[index];_tables[index] = NewNode;++_size;return true;}Node* Find(const Key& key){ValueofKey Keyofvalue;int index = _HashFunc(key);Node * pCur = _tables[index];while (pCur){if (Keyofvalue(pCur->_valueField) == key)return pCur;}return nullptr;}bool Remove(const Key& key){ ValueofKey Keyofvalue;int index = _HashFunc(key);Node * pCur = _tables[index];while (pCur){if (Keyofvalue(pCur->_valueField) == key){pCur->_valueField = _tables[index]->_valueField;Node * del = _tables[index];_tables[index] = _tables[index]->_next;delete del;--_size;return true;}}return false;}~HashTable(){for(auto & i :_tables){Node * pCur = i;Node * pNext = NULL;while(pCur){pNext = pCur->_next;delete pCur;pCur = pNext;}}}protected:size_t _HashFunc(const Key&key){return HashFunc()(key) % _tables.size();}unsigned int Getprimer(unsigned int x){for (auto&i : _PrimeList){if (x < i)return i;}return x;}void CheckCap(){ValueofKey valueofkey;if (_size==_tables.size()){HashTable<Key, V, HashFunc,HashFunc> newtable(Getprimer(_tables.size()));for (auto&i : _tables){Node * pCur = i;while (pCur){newtable.Insert(pCur->_valueField);pCur = pCur->_next;}}newtable._tables.swap(_tables);}}private:vector<Node*> _tables;size_t _size;
};

###Unordered__Map / Unordered_Set 实现

template<class K>
struct __HashFunc
{size_t operator()(const K& key){return key;}
};template<>
struct __HashFunc<string>
{static size_t BKDRHash(const char * str){unsigned int seed = 131; // 31 131 1313 13131 131313 unsigned int hash = 0;while (*str){hash = hash * seed + (*str++);}return (hash & 0x7FFFFFFF);}size_t operator()(const string& key){return BKDRHash(key.c_str());}
};template<class ValueType>
struct HashNode
{ValueType _valueField;HashNode<ValueType> * _next;HashNode(const ValueType& valueField):_valueField(valueField), _next(NULL){}
};template<class Key, class V, class ValueofKey, class HashFunc>
class HashTable
{typedef  V ValueType;typedef HashNode<V> Node;public:friend struct HashTableIterator<Key,V,ValueofKey,HashFunc>;typedef HashTableIterator<Key, V, ValueofKey, HashFunc> Iterator;HashTable():_tables(Getprimer(0)), _size(Getprimer(0)){}pair<Iterator, bool> Insert(const ValueType& valueField){ValueofKey Keyofvalue;int key = Keyofvalue(valueField);int index = _HashFunc(key);Node* pCur = _tables[index];while (pCur){if (Keyofvalue(pCur->_valueField) == key)return pair<Iterator, bool>(Iterator(NULL,this), false);}Node * NewNode = new Node(valueField);NewNode->_next = _tables[index];_tables[index] = NewNode;++_size;return std::pair<Iterator,bool>(Iterator(NewNode,this),true);}Iterator Find(const Key& key){ValueofKey Keyofvalue;int index = _HashFunc(key);Node * pCur = _tables[index];while (pCur){if (Keyofvalue(pCur->_valueField) == key)return Iterator(pCur,this);}return Iterator(nullptr,this);}bool Remove(const Key& key){ValueofKey Keyofvalue;int index = _HashFunc(key);Node * pCur = _tables[index];while (pCur){if (Keyofvalue(pCur->_valueField) == key){pCur->_valueField = _tables[index]->_valueField;Node * del = _tables[index];_tables[index] = _tables[index]->_next;delete del;--_size;return true;}}return false;}
protected:size_t _HashFunc(const Key&key){return HashFunc()(key) % _tables.size();}unsigned int Getprimer(unsigned int x){for (auto&i : _PrimeList){if (x < i)return i;}return x;}void CheckCap(){ValueofKey valueofkey;if (_size == _tables.size()){HashTable<Key, V, HashFunc, HashFunc> newtable(Getprimer(_tables.size()));for (auto&i : _tables){Node * pCur = i;while (pCur){newtable.Insert(pCur->_valueField);pCur = pCur->_next;}}newtable._tables.swap(_tables);}}
private:vector<Node*> _tables;size_t _size;
};template<class Key, class V, class ValueofKey, class HashFunc>
struct HashTableIterator
{typedef HashNode<V> Node;typedef HashTableIterator<Key, V, ValueofKey, HashFunc> Self;typedef HashTable<Key, V, ValueofKey, HashFunc> _HashTable;Node * _node;_HashTable * _hashTables;HashTableIterator(Node * node, _HashTable* hashTable):_node(node), _hashTables(hashTable){}V& operator*(){return _node->_valueField;}V* operator->(){return &(_node->_valueField);}bool operator==(const Self& s) const{return _node == s._node;}bool operator!=(const Self& s) const{return _node != s._node;}Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{ValueofKey valueofkey;size_t index = valueofkey(_node->_valueField);int size = _hashTables->_tables.size();_node = NULL;for (int i = index + 1; i < size; ++i){if (_hashTables->_tables[i]){_node = _hashTables->_tables[i];break;}}}return *this;}};template<class V>
struct _KeyOfValue
{const V& operator()(const V& value){return value;}
};template<class K,class V>
struct _PairKeyOfValue
{const K& operator()(const V& value){return value.first;}
};
template<class K ,class HashFunc=__HashFunc<K>>
class Unorderd_Set
{typedef HashTableIterator<K, K,_KeyOfValue<K>, HashFunc> Iterator;
public:Unorderd_Set():_Hashtable(){}Iterator Begin(){int size = _Hashtable._tables.size();for (int i = 0; i < size; ++i){if (_Hashtable._tables[i])return Iterator(_Hashtable._tables[i]);}return Iterator(NULL,&_Hashtable);}const Iterator End(){return Iterator(NULL, &_Hashtable);}const std::pair<Iterator, bool> Insert(K valueFiled){return _Hashtable.Insert(valueFiled);}const Iterator find(const K&key){return _Hashtable.Find(key);}bool Remove(const K& key){return _Hashtable.Remove(key);}
private:HashTable<K, K, _KeyOfValue<K>, HashFunc> _Hashtable;
};
template<class K, class V, class HashFunc = __HashFunc<K>>
class Unorderd_Map
{typedef std::pair<K,V> ValueFiled;typedef HashTableIterator<K, ValueFiled, _PairKeyOfValue<K,ValueFiled>, HashFunc> Iterator;
public:Unorderd_Map():_Hashtable(){}Iterator Begin(){int size = _Hashtable._tables.size();for (int i = 0; i < size; ++i){if (_Hashtable._tables[i])return Iterator(_Hashtable._tables[i],&_Hashtable);}return Iterator(NULL, &_Hashtable);}Iterator End(){return Iterator(NULL, &_Hashtable);}std::pair<Iterator, bool> Insert(ValueFiled &value){return _Hashtable.Insert(value);}Iterator find(const K&key){return _Hashtable.Find(key);}bool Remove(const K& key){return _Hashtable.Remove(key);}
private:HashTable<K, ValueFiled, _PairKeyOfValue<K,ValueFiled>, HashFunc> _Hashtable;
};

####最后思考下为什么要有keyofvalue
??答案就是节省内存，对于set 来说key就是value , 对于map来说 key是key value是 pair< key,value> 键值对，所以用keyofvalue 可以直接从 value中获取 key ，就没必要保存key了这个设计就是节省内存。