赞
踩
1. unordered_map是存储pair<key, value>,通过key查找value
2.unordered_map对数据的存储没有特定的排序顺序。
3. unordered_map搜索比map快,但它遍历效率比较慢。
4. 它的迭代器至少是前向迭代器,不支持反向迭代器。
1.存储数据没有顺序
2.查找效率高,遍历效率低
3.没有重复值
4.插入效率高
5.不支持修改操作,可以先删除再插入
插入规则:对插入的值进行size()大小的取模,eg.14%10=4 头插到下标为4的节点处。
当size()大小==插入节点的个数 就进行扩容
结构:
哈希桶结构:有一个size()大小的顺序表,表中节点存储的是插入节点的指针Node*。
Node结构体能存储数据值,还可以保存下个节点的指针。
- template<class T>
- struct HashNode
- {
- T _data;
- HashNode<T>* _next;
-
- HashNode(const T& data)
- :_data(data)
- , _next(nullptr)
- {}
- };
-
- template<class K, class T, class KeyOfT, class Hash = HashFunc<K>>
- class HashTable
- {
- template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash >
- friend struct HashIterator;
-
- typedef HashNode<T> Node;
- private:
- vector<Node*> _tables;
- size_t _n;
- };
_tables顺序表 _n记录插入的个数 Node插入节点结构 T存储数据类型
KeyOfT用于从T类型中取出key值 Hash将key值转换为一一对应的int值
这里定义的Node结构,它没有自己的析构函数,我们要手动释放空间。
vector<list<T>> vector list都有自己的析构,自动调用就可以。
- HashTable()
- {
- _tables.resize(10, nullptr);
- }
- ~HashTable()
- {
- for (size_t i = 0; i < _tables.size(); i++)
- {
- Node* cur = _tables[i];
- while (cur)
- {
- Node* next = cur->_next;
- delete cur;
- cur = next;
- }
- _tables[i] = nullptr;
- }
- }
1.利用find()进行去重。
2.负载因子==1就需要进行扩容。
3.KeyOfTf取出key,再用Hash转换对应int再取模找到映射位置,进行头插。
- pair<Iterator, bool> Insert(const T&data)
- {
- Hash hs;
- KeyOfT kof;
- //去重
- Iterator it = Find(kof(data));
- if (it != End())
- {
- return make_pair(it,false);
- }
- //扩容
- if (_n == _tables.size())
- {
- vector<Node*> newtable(_tables.size() * 2, nullptr);
- //将原哈希表存在的值重新定位插入
- for (size_t i = 0; i < _tables.size(); i++)
- {
- Node* cur = _tables[i];
- size_t newi = hs(kof(data)) % newtable.size();
- while (cur)
- {
- Node* next = cur->_next;
- cur->_next = newtable[newi];
- newtable[newi] = cur;
- cur = next;
- }
- _tables[i] = nullptr;
- }
-
- //交换哈希表的vector 新建哈希表出了作用域自动销毁
- _tables.swap(newtable);
- }
- size_t Hashi = hs(Hash(data)) % _tables.size();
-
- //头插
- KeyOfT kof;
- Node* cur = new Node(kof(data));
- cur->_next = _tables[Hashi];
- _tables[Hashi] = cur;
- _n++;
- return make_pair(Iterator(cur,this), true);
- }
查找值,先找到它映射的位置,再对整个桶进行遍历。找到返回对应位置,反之返回空。
- Iterator* Find(const K& key)
- {
- KeyOfT kof;
- Hash sh;
- size_t Hashi = hs(key) % _tables.size();
- Node* cur = _tables[Hashi];
- while (cur)
- {
- if (kof(cur->_data) == key)
- return Iterator(cur,this);
- else cur = cur->_next;
- }
- return Iterator(nullptr, this);
- }
先通过映射找到对应桶的位置,再遍历找。
1.被删除节点是头节点,没有上一个节点。删除节点后,顺序表中存入它的下一个节点的指针。
2.不是头节点,有上一个节点。让它的prev 指向 next 再删除。
记得--_n
没找到返回fasle
- bool Erase(const K& key)
- {
- Hash hs;
- size_t Hashi = hs(key) % _tables.size();
- Node* prev = nullptr;
- Node* cur = _tables[Hashi];
- Node* next = cur->_next;
- while (cur)
- {
- KeyOfT kof;
- if (kof(cur->_data) == key)
- {
- //头节点就是要删除节点
- if (cur == _tables[Hashi])
- _tables[Hashi] = next;
- else
- prev->_next = next;
-
- delete cur;
- _n--;
- return true;
- }
- //找该桶的下一个节点
- prev = cur;
- cur = next;
- next = cur->_next;
- }
- return false;
- }
顺序表中每个桶之间是不连续的。迭代器中只有指向Node的指针,遍历完一个桶后,就找不到下一个桶的位置了。
因此还需要顺序表,通过顺序表找到下一个桶的位置。
因为要访问HashNode HashTable结构,但它们的实现在HashIterator的后面,况且HashTable实现也需要迭代器。因此需要前置声明让编译器知道有HashNode HashTable。
- //前置声明
- template<class T>
- struct HashNode;
- template<class K, class T, class KeyOfT, class Hash >
- class HashTable;
- //迭代器
- template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash = HashFunc<K>>
- struct HashIterator
- {
- typedef HashNode<T> Node;
- typedef HashIterator< K, T, Ref,Ptr, KeyOfT, Hash > Self;
-
- Node* _node;
- HashTable< K, T, KeyOfT, Hash >* _pht;
-
- HashIterator(Node*node, HashTable< K, T, KeyOfT, Hash >*pht)
- :_node(node)
- ,_pht(pht)
- {}
-
- Self& operator++()
- {
- //该桶还没遍历完
- if (_node->_next)
- {
- _node = _node->_next;
- }
- //遍历完找下一个桶
- else
- {
- KeyOfT kot;
- Hash sh;
- size_t hashi = sh(kot(_node->data)) % _pht->_tables.size();
- hashi++;
- while (hashi < _pht->_tables.size())
- {
- //有桶 遍历桶
- if (_pht->_tables[hashi])
- {
- _node = _pht->_tables[hashi];
- break;
- }
- //没有++找下一个位置
- else
- hashi++;
- }
- //整个顺序表遍历结束 返回end()
- if (hashi == _pht->_table.size())
- _node = nullptr;//end()
- }
- return *this;
- }
-
- Ref operator*()
- {
- return _node->_data;
- }
-
- Ptr operator->()
- {
- return &_node->_data;
- }
- bool operator!=(const Self& s)
- {
- return _node != s._node;
- }
-
- };
因为set的key值不能修改所以传const K
- #include"HashTables.h"
-
- namespace wws
- {
- template<class K, class Hash = HashFunc<K>>
- class unordered_set
- {
- struct SetKeyOfT
- {
- const K& operator()(const K& key)
- {
- return key;
- }
- };
- public:
- typedef typename HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
- typedef typename HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;
-
-
- iterator begin()
- {
- return _ht.Begin();
- }
-
- iterator end()
- {
- return _ht.End();
- }
-
- const_iterator begin() const
- {
- return _ht.Begin();
- }
-
- const_iterator end() const
- {
- return _ht.End();
- }
-
- pair<iterator, bool> insert(const K& key)
- {
- return _ht.Insert(key);
- }
-
- iterator Find(const K& key)
- {
- return _ht.Find(key);
- }
-
- bool Erase(const K& key)
- {
- return _ht.Erase(key);
- }
-
- private:
- HashTable<K, K, SetKeyOfT, Hash> _ht;
- };
- }
-
-
-
map key不能修改 但value可以修改 所以传pair<const K,V>
- #include"HashTables.h"
-
-
- namespace wws
- {
- template<class K, class V, class Hash = HashFunc<K>>
- class unordered_map
- {
- struct MapKeyOfT
- {
- const K& operator()(const pair<K, V>& kv)
- {
- return kv.first;
- }
- };
- public:
- typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
- typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;
-
- iterator begin()
- {
- return _ht.Begin();
- }
-
- iterator end()
- {
- return _ht.End();
- }
-
- const_iterator begin() const
- {
- return _ht.Begin();
- }
-
- const_iterator end() const
- {
- return _ht.End();
- }
-
- pair<iterator, bool> insert(const pair<K, V>& kv)
- {
- return _ht.Insert(kv);
- }
-
- V& operator[](const K& key)
- {
- pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
-
- return ret.first->second;
- }
-
- iterator Find(const K& key)
- {
- return _ht.Find(key);
- }
-
- bool Erase(const K& key)
- {
- return _ht.Erase(key);
- }
- private:
- HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;
- };
- }
- #include"string"
- #include"vector"
- #include<iostream>
- using namespace std;
-
-
- template<class K>
- struct HashFunc
- {
- size_t operator()(const K& key)
- {
- return (size_t)key;
- }
- };
-
- // 特化
- template<>
- struct HashFunc<string>
- {
- size_t operator()(const string& key)
- {
- size_t hash = 0;
- for (auto e : key)
- {
- hash *= 31;
- hash += e;
- }
-
- return hash;
- }
- };
- //前置声明
- template<class T>
- struct HashNode;
- template<class K, class T, class KeyOfT, class Hash >
- class HashTable;
- //迭代器
- template<class K, class T, class Ref,class Ptr,class KeyOfT, class Hash = HashFunc<K>>
- struct HashIterator
- {
- typedef HashNode<T> Node;
- typedef HashIterator< K, T, Ref,Ptr, KeyOfT, Hash > Self;
-
- Node* _node;
- HashTable< K, T, KeyOfT, Hash >* _pht;
-
- HashIterator(Node*node, HashTable< K, T, KeyOfT, Hash >*pht)
- :_node(node)
- ,_pht(pht)
- {}
-
- Self& operator++()
- {
- //该桶还没遍历完
- if (_node->_next)
- {
- _node = _node->_next;
- }
- //遍历完找下一个桶
- else
- {
- KeyOfT kot;
- Hash sh;
- size_t hashi = sh(kot(_node->data)) % _pht->_tables.size();
- hashi++;
- while (hashi < _pht->_tables.size())
- {
- //有桶 遍历桶
- if (_pht->_tables[hashi])
- {
- _node = _pht->_tables[hashi];
- break;
- }
- //没有++找下一个位置
- else
- hashi++;
- }
- //整个顺序表遍历结束 返回end()
- if (hashi == _pht->_table.size())
- _node = nullptr;//end()
- }
- return *this;
- }
-
- Ref operator*()
- {
- return _node->_data;
- }
-
- Ptr operator->()
- {
- return &_node->_data;
- }
- bool operator!=(const Self& s)
- {
- return _node != s._node;
- }
-
- };
-
-
-
-
-
- template<class T>
- struct HashNode
- {
- T _data;
- HashNode<T>* _next;
-
- HashNode(const T& data)
- :_data(data)
- , _next(nullptr)
- {}
- };
-
- template<class K, class T,class KeyOfT, class Hash = HashFunc<K>>
- class HashTable
- {
- template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash >
- friend struct HashIterator;
-
- typedef HashNode<T> Node;
-
- public:
- typedef HashIterator< K, T, T&, T* , KeyOfT, Hash > Iterator;
- typedef HashIterator< K, T, const T&,const T*, KeyOfT, Hash > ConstIterator;
-
- Iterator Begin()
- {
- for (size_t i = 0; i < _tables.size(); i++)
- {
- if (_tables[i])
- return Iterator(_tables[i], this);
- }
- return Iterator(nullptr, this);
- }
- Iterator End()
- {
- return Iterator(nullptr, this);
- }
- ConstIterator Begin() const
- {
- for (size_t i = 0; i < _tables.size(); i++)
- {
- if (_tables[i])
- return Iterator(_tables[i], this);
- }
- return Iterator(nullptr, this);
- }
- ConstIterator End() const
- {
- return Iterator(nullptr, this);
- }
-
- HashTable()
- {
- _tables.resize(10, nullptr);
- }
- ~HashTable()
- {
- for (size_t i = 0; i < _tables.size(); i++)
- {
- Node* cur = _tables[i];
- while (cur)
- {
- Node* next = cur->_next;
- delete cur;
- cur = next;
- }
- _tables[i] = nullptr;
- }
- }
- pair<Iterator, bool> Insert(const T&data)
- {
- Hash hs;
- KeyOfT kof;
- Iterator it = Find(kof(data));
- if (it != End())
- {
- return make_pair(it,false);
- }
- //扩容
- if (_n == _tables.size())
- {
- vector<Node*> newtable(_tables.size() * 2, nullptr);
- //将原哈希表存在的值重新定位插入
- for (size_t i = 0; i < _tables.size(); i++)
- {
- Node* cur = _tables[i];
- size_t newi = hs(kof(data)) % newtable.size();
- while (cur)
- {
- Node* next = cur->_next;
- cur->_next = newtable[newi];
- newtable[newi] = cur;
- cur = next;
- }
- _tables[i] = nullptr;
- }
-
- //交换哈希表的vector 新建哈希表出了作用域自动销毁
- _tables.swap(newtable);
- }
- size_t Hashi = hs(Hash(data)) % _tables.size();
-
- //头插
- KeyOfT kof;
- Node* cur = new Node(kof(data));
- cur->_next = _tables[Hashi];
- _tables[Hashi] = cur;
- _n++;
- return make_pair(Iterator(cur,this), true);
- }
- Iterator* Find(const K& key)
- {
- KeyOfT kof;
- Hash sh;
- size_t Hashi = hs(key) % _tables.size();
- Node* cur = _tables[Hashi];
- while (cur)
- {
- if (kof(cur->_data) == key)
- return Iterator(cur,this);
- else cur = cur->_next;
- }
- return Iterator(nullptr, this);
- }
- bool Erase(const K& key)
- {
- Hash hs;
- size_t Hashi = hs(key) % _tables.size();
- Node* prev = nullptr;
- Node* cur = _tables[Hashi];
- Node* next = cur->_next;
- while (cur)
- {
- KeyOfT kof;
- if (kof(cur->_data) == key)
- {
- //头节点就是要删除节点
- if (cur == _tables[Hashi])
- _tables[Hashi] = next;
- else
- prev->_next = next;
-
- delete cur;
- _n--;
- return true;
- }
- //找该桶的下一个节点
- prev = cur;
- cur = next;
- next = cur->_next;
- }
- return false;
- }
- private:
- vector<Node*> _tables;
- size_t _n;
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。