哈希顺序结构以及平衡树中元素关键码与其存储位置之间没有对应的关系因此在查找一个元素 时必须要经过关键码的多次比较比如平衡树要不断和节点值进行大小比较。这些结构搜索的效率取决于搜索过程中元素的比较次数。如果能不经过任何比较直接从表中得到要搜索的元素像数组直接访问下标一样会方便很多。 实现这种结构的关键是通过哈希函数使元素的存储位置与它的关键码之间能够建立一一映射的关系。哈希就是通过哈希函数产生关键码根据关键码存放数据的一种结构哈希函数有很多种这里介绍常见的除留余数法除留余数法当前哈希表容量为10现插入一个5让数值模容量即可找到需要存放的位置。模容量是为了防止越界如果传入20模10后得2仍在哈希容量范围内。假如待插入的数据取模得到的下标位置已经存放了数据这种情况被称为哈希冲突哈希函数设计的越精妙哈希冲突发生的可能性就越低但哈希冲突不可避免。哈希冲突示例闭散列开放定址法前面的除留余数法是通用的哈希函数但得到关键码后如何存储又分为多种方式其中一种方式叫闭散列在闭散列中哈希表的数据附带三种状态分别是EMPTY空,EXIST存在,DELETE被删除。为什么节点要有状态呢设想在哈希中查找元素时必然从关键码对应下标开始找如果下标处的内容为空说明可以产生这个关键码数据从来没有被插入后面更不可能存在相同关键码对应的数据。但“为空“实际上存在两种情况从未插入过数据或数据被删除下面示例被删除的数据如何导致误判找不到6这时如果将被删除处标记为DELETE,遍历时遇到DELETE就继续往后找就可以解决此问题而状态为EMPTY或DELETE的位置都可以插入这样子不会浪费状态已经删除数据的空间负载因子如果不扩容哈希表迟早会装满哈希冲突的解决又导致哈希效率下降所以引入负载因子用于判断什么时候扩容负载因子有效数据个数/当前容量如负载因子为0.6当前容量为10准备存放第7个有效数据时发现6/100.6达到负载因子扩容再将原先哈希表中的元素重新插入到扩容后的哈希表中。这样关键码与下标不匹配的数据有机会重新洗牌从而提高效率。见下图下标6因为被15占用导致6只能存到下标7所以6、7两个下标处存放的都是关键码不匹配的数据扩容后出现了下标15从而让15和6插入到正确的位置提高了哈希的效率。然而负载因子并不能随意设定负载因子越大尽可能不扩容空间利用率越高时间效率越低如前文所述存在大量不匹配数据拉链法闭散列最大的缺陷就是空间利用率低扩容后有些地方没存到数据这也是哈希的缺陷。而拉链法空间利用率更高因为哈希表不再直接用于存储数据而是存储链表如此一来哈希表下标和数据对应的关键码必然匹配此时效率取决于链表的长短拉链法的扩容10个指针即可存储所有无符号整形但链表也随之增长查找、删除等操作效率也会很低。所以和闭散列一样也需要通过扩容进行“洗牌”。拉链法负载因子设置为1即只要数据个数和桶的数量相同就进行扩容。按这个定义平均每个桶可以装一个数据实际上无法这么理想这正是时间效率最高的情况同时空间效率最低哈希的模拟实现哈希函数定义根据前文提到的除留余数法要得到关键码就要让传入值模容量但并不是所有传入值都支持这样的运算如string,同时也应当支持用户自定义哈希函数所以这里让哈希函数作为模板参数同时为string特别写一份根据ASCII码值生成关键码的哈希函数供用户直接使用//比较通用的哈希函数 templatetypename T class HashFunc { public: size_t operator()(const T Key) { return size_t(Key); } }; //为什么除了string以外的多数其它类型也能用上面仿函数呢因为size_t可以把负数、小数都换成正整数不然找不到数组索引 template//这里通过模板的特化对string做特别处理 class HashFuncstring { public: size_t operator()(const string Key) { size_t hash 0; for (auto i : Key) { hash 131 * hash i;//这个操作可以极大降低两个字符串ASCII码值之和结果相同的概率 } return hash; } };为什么哈希函数不能直接在hash里面定义如果哈希函数直接在hash中定义相当于锁死了该函数用户无法自定义这个函数哈希函数也无法处理自定义类型,即便不需要处理自定义类型有时对string比较大小的并不依据ASCII码值之和可能只需要对首字母进行大小比较这时也需要给予用户自定义权限。哈希表节点定义templateclass T class Hash_Node { public: Hash_Node(const Tkv):_value(kv) , _next(nullptr){} //delete node*会自动调用释放函数所以node不需要再写析构 Hash_Node() :_next(nullptr){} T _value; Hash_NodeT* _next; };哈希表成员变量如下templateclass K, class V,typename hashfunc class Hashtable { public: typedef Hash_NodepairK,V node; hashfunc func; private: vectornode*_table; size_t _n; size_t _capacity; };查找函数node* Find(const K Key) { for (auto i : _table) { node* cur i; while (cur) { if (cur-_value.first Key) { return i; } cur cur-_next; } } return nullptr; }插入函数因为拉链法节点顺序无需在意所以插入节点采用头插的方式代码简洁效率高bool Insert(const pairK, V kv) {//hash的Insert要的是 //先检查是否存在 if (Find(kv.first)) { return false; } //再检查扩容 if (_n_capacity) {负载因子为1就扩容 vectornode*temp; temp.resize(_capacity * 2); _capacity temp.size(); //用头插的方法比尾插快的多 for (auto i : _table) {//遍历原表每一个桶 node* cur i; while (cur) {//让cur一直往下走相当于把原表的节点直接拉到新表 node* next cur-_next; size_t pos func(cur-_value.first) % temp.size(); cur-_next temp[pos]; temp[pos] cur; cur next;//这里是合理的不会导致覆盖 } } swap(temp,_table); } size_t pos func(kv.first) % _capacity; node* input new node(kv); input-_next _table[pos]; _table[pos] input; _n; return true; }为什么扩容不复用Insert复用需要传值要再拷贝两次不划算不如直接把链表节点拿来用为什么扩容不创建一个新的哈希表最后直接交换哈希对象的指针?this指针默认是只读的不可能作为swap的参数删除函数//删除 bool Erase(const K Key) { //这里无法找到父亲节点所以不能复用find for (auto i : _table) { node* parent nullptr; node* cur i; while (cur) { //如果此桶只有一个节点,不能直接delete不然会造成断裂应当由table统一释放 //所以只能让它指向一个空桶next if (cur-_value.first Key) { if (parentnullptr) { node* temp cur; cur cur-_next; delete temp; } else { parent-_next cur-_next; delete cur; } return true; } parent cur; cur cur-_next; } } }为什么erase不能复用find?find只能找到当前节点如果要删除当前节点还要把当前节点的父亲和孩子节点连接起来所以不能复用。为什么桶只有一个值且该值为待删除值时不直接delete?这样做后续遍历哈希表的时候会发生访问错误因为这个桶的空间被释放了。所以要让待删除节点指向空节点这样桶里仍然存放有值。析构函数特别强调//数组里的node*所指向的内容要通过析构函数释放 ~Hashtable() { for (auto i : _table) { node* cur i; while (cur) { node* temp cur; cur cur-_next; delete temp; } } }为什么需要定义析构函数闭散列中的vector存储的是data类对象当哈希表生命周期结束的时候自动调用哈希表vector类ing的析构函数而哈希表中存储的是自定义data类又会自动调用data的析构函数。而哈希桶中的vector存储的是节点指针指针是一个普通类型系统只会把这些指针本身占用的空间释放而不会自动释放指针所指向的空间因此需要自定义析构函数释放各节点内指针指向的空间。unordered_map和unordered_set封装库函数中的unordered_map和unordered_set的使用类似于map和set,但底层结构为哈希模拟实现比较复杂需要清楚实现步骤按顺序走不然后面bug贼多实现顺序哈希表-unordered_map和unordered_set基本封装搭外壳,让哈希函数和keyofvalue跑通)-普通迭代器-const迭代器(难)-insert/find返回值-operator[]unordered_map和unordered_set对hash封装的模拟实现下面先给出除去函数实现的伪代码哈希表本身代码//hash.h #pragma once #include vector #include string #include utility // for pair using namespace std; namespace Hash_Bucket { // --- 1. 哈希函数 --- // 通用哈希函数模板 templatetypename T class HashFunc { public: size_t operator()(const T Key); }; // string 类型的特化版本 template class HashFuncstring { public: size_t operator()(const string Key); }; // --- 2. 节点类 --- templateclass T class Hash_Node { public: Hash_Node(const T kv); // 带值构造 Hash_Node(); // 默认构造 public: T _value; // 存储的数据对于 map 是 pair对于 set 是 K Hash_NodeT* _next; // 指向下一个节点的指针 }; // --- 3. 哈希表前置声明 --- templateclass K, class V, typename keyofvalue, typename hashfunc class Hashtable; // --- 4. 迭代器类 --- templateclass K, class V, class Ptr, class Ref, typename keyofvalue, typename hashfunc class Hash_Iterator { public: // 类型定义 typedef Hash_IteratorK, V, Ptr, Ref, keyofvalue, hashfunc Self; typedef Hash_NodeV node; typedef HashtableK, V, keyofvalue, hashfunc table; public: // 构造函数 Hash_Iterator(node* Node, const table* Table); Hash_Iterator(const Hash_Iterator it); // 运算符重载 Self operator(); // 前置 Ptr operator-(); // 箭头运算符 Ref operator*(); // 解引用 bool operator(const Self input); bool operator!(const Self input); public: // 成员变量 table* _table; // 指向所属的哈希表用于跨桶跳转 node* _node; // 指向当前节点 }; // --- 5. 哈希表主体 --- templateclass K, class V, typename keyofvalue, typename hashfunc HashFuncK class Hashtable { public: // 友元声明允许迭代器访问私有成员 templateclass K, class V, class Ptr, class Ref, typename keyofvalue, typename hashfunc friend class Hash_Iterator; // 类型定义 typedef Hash_IteratorK, V, V*, V, keyofvalue, hashfunc iterator; typedef Hash_IteratorK, V, const V*, const V, keyofvalue, hashfunc const_iterator; typedef Hash_NodeV node; public: // 构造与析构 Hashtable(); ~Hashtable(); // 核心功能接口 pairiterator, bool Insert(const V kv); // 插入数据 iterator Find(const K Key); // 查找数据 bool Erase(const K Key); // 删除数据 void Print(); // 打印调试 // 迭代器接口 iterator begin(); iterator end(); private: // 成员变量 vectornode* _table; // 桶数组指针数组 size_t _n; // 当前元素个数 size_t _capacity; // 桶的数量容量 }; }unordered_map伪代码// unorder_map.h #pragma once #include hash.h namespace unordermap { templateclass K, class V class unorder_map { public: // --- 1. 键值提取仿函数 --- // 用于告诉底层哈希表如何从 pairconst K, V 中拿到键 K class KeyOfValue { public: const K operator()(const pairconst K, V kv); }; // --- 2. 类型定义 --- // 复用底层 Hashtable 的迭代器 typedef typename Hash_Bucket::HashtableK, pairconst K, V, KeyOfValue::iterator iterator; typedef typename Hash_Bucket::HashtableK, pairconst K, V, KeyOfValue::const_iterator const_iterator; // --- 3. 核心功能接口 --- // 插入键值对 // 返回 pair迭代器, boolbool 表示插入是否成功 pairiterator, bool insert(const pairconst K, V input); // 下标访问运算符 // 如果键不存在则插入默认值如果存在则返回已有值的引用 V operator[](const K key); // --- 4. 迭代器接口 --- iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; private: // --- 5. 成员变量 --- // 底层实际维护数据的哈希表 // K: 键类型 // pairconst K, V: 存储的数据类型 // KeyOfValue: 键值提取策略 Hash_Bucket::HashtableK, pairconst K, V, KeyOfValue _table; }; }在实现过程中遇到的问题unordered_map和unordered_set的对比unordered_map的迭代器typedef typename Hash_Bucket::HashtableK, pairconst K,V, keyofvalue::iterator iterator; typedef typename Hash_Bucket::HashtableK, pair const K,V, keyofvalue::const_iterator const_iterator;unordered_set的迭代器typedef typename Hash_Bucket::HashtableK, K, keyofvalue::const_iterator iterator; typedef typename Hash_Bucket::HashtableK, K, keyofvalue::const_iterator const_iterator;unordered_map的iterator和const_iterator是有区别的分别对应哈希中的Iterator和const_iterator而set中的iterator和const_iterator都是哈希中的const_iterator。这是因为unordered_map根据是否被const修饰选择是否更改值而unordered_set只有键且不允许修改键。unordered_map迭代器要对key使用const修饰因为无论普通还是const迭代器都不能对键进行修改。insert为什么要先定义一个pair来接收hash层面的insert的返回值然后再把这个pair返回给set和map层面呢pairiterator,bool insert(K value) { pairtypename table::iterator,bool temp _table.Insert(value); return make_pair(iterator(temp.first), temp.second);//这里要再次转换 }因为_table.Insert定义在hash中而hash中的insert返回的是一个普通迭代器回到unordered_set和unordered_map层面unordered_map没有问题但unordered_set层面只有const_iterator所以要对拿到手的普通迭代器进行转换。hash内定义的迭代器typedef Hash_IteratorK, V, V*, V , keyofvalue, hashfunc iterator; typedef Hash_IteratorK, V, const V*, const V, keyofvalue, hashfunc const_iterator;unordered_set的迭代typedef typename Hash_Bucket::HashtableK, K, keyofvalue::const_iterator iterator; typedef typename Hash_Bucket::HashtableK, K, keyofvalue::const_iterator const_iterator;回到原来的问题为什么Insert不直接这样写呢pairiterator,bool insert(K value) { return _table.Insert(value); }返回值pair是一个类“iterator,bool”是它的模板参数如果模板参数不同传iterator和const_iterator定义出来的类的类型也是不同的编译器无法完成自动转换。也就是说类模板相同实例化对象的类型可以不相同。可能会想那iterator不能先被隐式转换成const_iterator吗同理iterator也是一个类定义普通迭代器和const迭代器时传给这个类的模板参数就不一样所以普通迭代器和const迭代器根本就不是一个类型所以编译器不会支持隐式类型转换。typedef Hash_IteratorK, V, V*, V , keyofvalue, hashfunc iterator;iterator的构造函数为什么是这样写的Hash_Iterator( node* Node, const table* Table):_table(Table),//这里为什么不能加consttable应当在成员定义时加上const _node(Node){} Hash_Iterator(const iterator it) :_table(it._table), _node(it._node) {//这里的构造对于普通迭代器是拷贝构造对于const迭代器是构造函数 }如前文所述普通迭代器并不支持编译器自动转换为const迭代器所以如果想用普通迭代器构造一个const迭代器就让普通迭代器作为构造函数的参数再手动转换这时问题转变为_table指针和_node指针转换const_table指针和const_node指针了指针是普通类型编译器支持自动转换。方括号重载实现insert以后就可以实现方括号重载对其进行复用了注意,set是没有方括号重载的。而unordered_map的方括号重载只有非const版本需要实现方括号重载这时候直接复用insert即可不用再像unordered_set一样先用一个pair去接收参数V operator[](const K key) { return _table.Insert(make_pair(key, V())).first-second; }其他问题1.在类中内部类、typedef以及static函数受访问限定符的限制吗?是的只有友元、struct类是不会受到访问限定符的约束。2.kov和func为什么要在函数中实例化而不是直接在类内部实例化成为类的成员呢这个还是有点说法的首先这些仿函数直接实例化为成员每个类对象被实例化的时候开销肯定会增加不划算。其次这些仿函数可能是有状态的直接实例化相当于不初始化不支持带参构造的仿函数。所以不如运行期间再实例化更加灵活且划算。3.关于什么时候要加typename之前我只关心模板参数可能需要增加typename,实际上只要是从别的作用域中调用成员都应该考虑是否要加typename因为编译器不能确定你调用的到底是类型还是函数声明。比如在unordered_map中定义的迭代器代码,复用了哈希中的迭代器的定义此时就需要加上一个typenametypedef typename table::iterator iterator;4.类定义是分先后的比如不能在类中宏定义一个后于该类定义的类5.auto操作的是副本所以要加上一个引用直接对auto修改无法改变容器内容6.用户不允许直接构造一个什么都不指向的迭代器必须有一个明确指向的对象所以迭代器不支持默认构造函数哈希的进一步优化极端场景下可能某个桶中存放的数据量过大这时考虑当桶中数据量达到一定值时将这个桶转换为一颗红黑树(也就是遍历链表构造红黑树)然后哈希表中原先的桶的节点指针链表头节点指针变成了树指针。经验总结这次模拟实现没有循序渐进比如在unorder_set和unorder_map的初步封装存在漏洞的情况下又去实现迭代器导致一直在挖坑找坑填坑花费的时间远超map和set的封装。在写项目之前要有一个大思路在每个阶段实现后要多调试。