福建人力资源建设网站,wordpress布局怎么看,建筑行业招聘网站排行榜,免费ppt模板下载软件有哪些系列文章目录
STL源码剖析笔记——迭代器 STL源码剖析笔记——vector STL源码剖析笔记——list STL源码剖析笔记——deque、stack#xff0c;queue STL源码剖析笔记——Binary Heap、priority_queue STL源码剖析笔记——AVL-tree、RB-tree、set、map、mutiset、mutimap STL源…系列文章目录
STL源码剖析笔记——迭代器 STL源码剖析笔记——vector STL源码剖析笔记——list STL源码剖析笔记——deque、stackqueue STL源码剖析笔记——Binary Heap、priority_queue STL源码剖析笔记——AVL-tree、RB-tree、set、map、mutiset、mutimap STL源码剖析笔记——哈希表、unordered_set、unordered_map、unordered_mutiset、unordered_mutimap 文章目录 系列文章目录1. hashtable线性探测二次探测开链法哈希表扩容闭散列开散列 2. unordered_set3. unordered_mutiset4. unordered_map5. unordered_mutimap 1. hashtable 哈希表hashtable是一种常见的数据结构它和红黑树、AVL一样是用来存储数据的。红黑树和AVL查找数据的时间复杂度是O(lgN) 是对数平均时间。但哈希表的查找效率具有常数平均时间复杂度是O(1) 哈希表的底层是通过数组hash function来实现常数时间查找效率。首先我们假设哈希表创建了一个大小为10的空间。 数据的存放通过hash function来决定具体采用除留余数法 根据这个规则可以将7911对应存入数组 但此时如果再想插入17会发现位置已经被7给占了这就是发生了哈希冲突。主要有三种方式来解决哈希冲突 1.线性探测 2.二次探测 3.开链法 线性探测和二次探测属于闭散列开链法属于开散列。
线性探测
线性探测就是发现当前位置被占之后顺序向后找直到找到一个空的位置如果到数组尾部仍未找到则回到头部从头找 但线性探测有一些无法避免的缺点 聚集 线性探测法容易导致聚集clustering现象。聚集指的是哈希表中形成连续的、紧密聚集的元素这使得在插入元素时发生冲突的概率进一步增加。聚集可能导致更多的线性探测进而影响性能。
性能下降 随着哈希表的填充因子增加线性探测法的性能可能下降。填充因子是指已经存储的元素数量与哈希表大小的比率。填充因子增加会导致冲突的概率上升进而增加线性探测的次数。
删除困难 在使用线性探测法的散列表中删除元素可能比较困难。删除操作通常需要标记被删除的元素否则会影响后续查找。而线性探测法对删除操作的支持相对较弱。
不适用于高负载因子 当哈希表的负载因子较高时即填充因子接近1线性探测法的性能可能急剧下降。高负载因子会导致更频繁的冲突线性探测的探测次数增多使得查找、插入和删除的效率都降低。
二次探测 二次探测的思路和线性探测一样但这次查找的步长变为了指数如果hash function计算出来的位置为H并且发生了冲突就依次尝试H 1²、H 2²、H 3²、H 4²······ 二次探测缓解了线性探测的聚集问题但也有一定的缺点
周期性聚集 二次探测法可能导致周期性聚集问题。如果哈希表的大小是某个4k3形式的素数而二次探测的步长为2的幂例如1, 4, 9, 16等那么在一定条件下会形成周期性的聚集。这可能导致更多的冲突和性能下降。
容易形成死循环 在某些情况下特定的哈希表状态可能导致二次探测进入死循环。例如如果哈希表中的某个位置发生冲突而附近的位置也都被占用那么二次探测可能永远无法找到空槽。
删除困难 与线性探测法一样二次探测法在删除操作上也可能比较困难。删除元素可能需要特殊的标记以确保在查找时能够正确地处理已删除的槽。
不适用于高负载因子 当哈希表的负载因子较高时二次探测法的性能可能下降。高负载因子增加了冲突的概率进而增加了二次探测的次数。
开链法 STL中的哈希表采用开链法解决哈希冲突问题开链法在每个单元维护一个单向链表发生冲突的元素直接接到链表上。同时将数组替换为vector方便空间扩充。hashtable只有前向迭代器一个单元的list最后的元素指向下一个单元即下一个list的头。
哈希表扩容
闭散列 我们定义一个负载因子来表示当前散列表的满溢程度 负载因子α 元素个数 / 数组长度 负载因子越高当前散列表发生哈希冲突的概率越高则整体效率越低。一般来说负载因子超过0.5时要考虑增容。扩容后由于数组长度发生变化原数组中的所有元素要重新插入到新哈希表中。
开散列 桶的个数是一定的随着元素的不断插入每个桶中元素的个数不断增多极端情况下可能会导致一个桶中链表节点非常多会影响的哈希表的性能因此在一定条件下需要对哈希表进行增容。开散列最好的情况是每个哈希桶中刚好挂一个节点再继续插入元素时每一次都会发生哈希冲突因此在元素个数刚好等于桶的个数时可以给哈希表增容。 扩容后由于桶的长度发生变化原数组中的所有元素要重新插入到新哈希表中。 对于整形数据可以直接进行取模运算但是如果要存的数据是字符串的类型呢我们要自己配套实现一个仿函数如果是int就自己实现int类型的仿函数如果是string就自己实现string类型的仿函数。然后用仿函数去计算。
2. unordered_set unordered_set的底层实现容器是hashtable哈希表可以进行高效的搜索、插入和删除操作时间复杂度是O(1)unordered_set不允许两个元素有相同的键值。 unordered_set与set相比拥有更高的操作效率set的操作效率是O(logn)但存入unordered_set是无序的不能保证输入进来数据的顺序 unordered_set的操作基本上都是对底层哈希表操作的引用
begin() 和 end()返回指向容器中第一个元素和最后一个元素之后的位置的迭代器。size()返回容器中元素的数量。empty()检查容器是否为空。如果为空返回 true否则返回 false。max_size()返回容器可以容纳的最大元素数量。insert()将元素插入到容器中。如果元素已经存在则不会插入。emplace()构造并插入元素。与 insert() 类似但可以直接使用构造函数参数避免额外的复制或移动操作。erase()从容器中删除指定的元素。clear()删除容器中的所有元素。find()查找容器中是否存在具有指定键的元素。如果找到则返回指向该元素的迭代器否则返回指向容器结尾的迭代器。count()返回具有指定键的元素的数量。对于 unordered_set结果只能是 0 或 1。bucket_count()返回容器中的桶数量。load_factor()返回容器的负载因子。负载因子是元素数量与桶数量的比值。max_load_factor()返回或设置容器的最大负载因子。当实际负载因子超过最大负载因子时容器会自动增加桶数量。rehash()设置容器的桶数量。当桶数量增加时容器将重新分配其元素以保持合适的负载因子。reserve()设置容器的最小桶数量以便容纳指定数量的元素而无需重新哈希。3. unordered_mutiset unordered_multiset的特性以及用法和unordered_set完全相同唯一的差别在于它允许键值重复(即插入重复的值)。
4. unordered_map unordered_map的的底层实现容器是hashtable哈希表可以进行高效的搜索、插入和删除操作时间复杂度是O(1)map的所有元素都是pair,同时拥有实值(value)和键值(key)。pair的第一元素被视为键值, 第二元素被视为实值。map不允许两个元素拥有相同的键值。 unordered_map与map相比拥有更高的操作效率map的操作效率是O(logn)但存入unordered_map是无序的不能保证输入进来数据的顺序 unordered_map的操作基本上都是对底层哈希表操作的引用
begin() 返回指向容器中第一个键值对的正向迭代器。
end() 返回指向容器中最后一个键值对之后位置的正向迭代器。
cbegin() 和 begin() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。
cend() 和 end() 功能相同只不过在其基础上增加了 const 属性即该方法返回的迭代器不能用于修改容器内存储的键值对。
empty() 若容器为空则返回 true否则 false。
size() 返回当前容器中存有键值对的个数。
max_size() 返回容器所能容纳键值对的最大个数不同的操作系统其返回值亦不相同。
at(key) 返回容器中存储的键 key 对应的值如果 key 不存在则会抛出 out_of_range 异常。
find(key) 查找以 key 为键的键值对如果找到则返回一个指向该键值对的正向迭代器反之则返回一个指向容器中最后一个键值对之后位置的迭代器如果 end() 方法返回的迭代器。
count(key) 在容器中查找以 key 键的键值对的个数。
equal_range(key) 返回一个 pair 对象其包含 2 个迭代器用于表明当前容器中键为 key 的键值对所在的范围。
emplace() 向容器中添加新键值对效率比 insert() 方法高。
emplace_hint() 向容器中添加新键值对效率比 insert() 方法高。
insert() 向容器中添加新键值对。
erase() 删除指定键值对。
clear() 清空容器即删除容器中存储的所有键值对。
swap() 交换 2 个 unordered_map 容器存储的键值对前提是必须保证这 2 个容器的类型完全相等。
bucket_count() 返回当前容器底层存储键值对时使用桶一个线性链表代表一个桶的数量。
max_bucket_count() 返回当前系统中unordered_map 容器底层最多可以使用多少桶。
bucket_size(n) 返回第 n 个桶中存储键值对的数量。
bucket(key) 返回以 key 为键的键值对所在桶的编号。
load_factor() 返回 unordered_map 容器中当前的负载因子。负载因子指的是的当前容器中存储键值对的数量size()和使用桶数bucket_count()的比值即 load_factor() size() / bucket_count()。
max_load_factor() 返回或者设置当前 unordered_map 容器的负载因子。
rehash(n) 将当前容器底层使用桶的数量设置为 n。
reserve() 将存储桶的数量也就是 bucket_count() 方法的返回值设置为至少容纳count个元不超过最大负载因子所需的数量并重新整理容器。
hash_function() 返回当前容器使用的哈希函数对象。5. unordered_mutimap unordered_multimap的特性以及用法和unordered_map完全相同唯一的差别在于它允许键值重复(即插入重复的值)。
