程序员笔记 （六十五）unordered_map
（一）unordered_map 底层原理
unordered_map 内部采用 hashtable 的数据结构存储，容器中每个key 会通过特定的哈希运算（哈希函数）映射到一个特定的位置。
一般来说，hashtable是可能存在冲突的，即不同的key值经过哈希函数计算后得到相同的结果（多个key通过计算映射到同一个位置）。
上述问题解决方法为：在每个位置放一个桶（bucket），用于存放映射到此位置的元素， 在同一个位置的元素会按顺序链在后面。下图为哈希表结构。
unordered_map内部是一个hash_table（一般是一个vector结构）。
bucket_vector中每个元素对应一个桶，据了解-当桶内数据量在8以内使用链表来实现桶，当数据量大于8 则自动转换为红黑树结构 也就是有序map的实现结构。
hash_table中查询(插入、删除) 过程是：
1、得到 key、 hash 函数得到 hash 值；
3、找到桶号（一般都为 hash 值对桶数求模）；
4、在桶内使用链表或红黑树进行查询；
（二）
常见哈希函数：
I. 直接定址法
取关键字的某个线性函数为散列地址:
hash(key) = A*Key +B 或 hash(key) = A*Key
其中a和b为常数。
II. 除留余数法:
取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。
hash(key) = key % p, p < m
此外还有数字分析法 、平方取中法、折叠法等。
哈希冲突的解决：常用的主要有两种方法解决冲突：
I. 链接法
将所有哈希地址相同的结点链接在同一个单链表中。
II. 开放定址法:
当冲突发生时，使用某种探查(亦称探测)技术在hash_table中寻找下一个空的地址，只要hash_table足够大，总能找到空的地址。根据不同方法，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。
如果您发现该资源为电子书等存在侵权的资源或对该资源描述不正确等，可点击“私信”按钮向作者进行反馈；如作者无回复可进行平台仲裁，我们会在第一时间进行处理！
- 最近热门资源
- 银河麒麟桌面操作系统备份用户数据 123
- 统信桌面专业版【全盘安装UOS系统】介绍 116
- 银河麒麟桌面操作系统安装佳能打印机驱动方法 108
- 银河麒麟桌面操作系统 V10-SP1用户密码修改 101
- 最近下载排行榜
- 银河麒麟桌面操作系统备份用户数据 0
- 统信桌面专业版【全盘安装UOS系统】介绍 0
- 银河麒麟桌面操作系统安装佳能打印机驱动方法 0
- 银河麒麟桌面操作系统 V10-SP1用户密码修改 0
prtyaa 收益393.62元
zlj141319 收益217.85元
1843880570 收益214.2元
IT-feng 收益208.98元
风晓 收益208.24元
777 收益172.71元
Fhawking 收益106.6元
信创来了 收益105.84元
克里斯蒂亚诺诺 收益91.08元
技术-小陈 收益79.5元
