开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构 - 哈希表（unordered_map) -> 正文阅读

[数据结构与算法]数据结构 - 哈希表（unordered_map)

面试问到哈希表，一时间发现很久不用该数据结构了，因此来梳理一下。
参考网址：

哈希表wiki
c++中unordered_map的用法的详述
unordered_map使用详解

一、定义：

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

二、冲突：

冲突定义：

对不同的关键字可能得到同一散列地址，即 $k_{1}\neq k_{2}$ ，而 $f(k_{1})=f(k_{2})$ ，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。

冲突解决：

为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：
?
1. 开放定址法:
越是质数，mod取余就越可能均匀分布在表的各处。
$hash_{i}=(hash(key)+d_{i})\,{\bmod \,}m, i=1,2...k\,(k\leq m-1)$ ，
其中 $ha s h (k ey)$ 为散列函数， $m$ 为散列表长， $d_{i}$ 为增量序列， $i$ 为已发生冲突的次数。
增量序列可有下列取法： $d_{i}=1,2,3...(m-1)$ 称为线性探测(Linear Probing)；即 $d_{i}=i$ ，或者为其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。
$d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2)$ 称为平方探测(Quadratic Probing)。相对线性探测，相当于发生冲突时探测间隔 $d_{i}=i^{2}$ 个单元的位置是否为空，如果为空，将地址存放进去。
$d_{i}=伪随机数序列$ ，称为伪随机探测。
?
2. 聚集（Cluster，也翻译做“堆积”）:
在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。

单独链表法：将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。
双散列。
再散列： $hash_{i}=hash_{i}(key), i=1,2...k。hash_{i}$ 是一些散列函数。即在上次散列计算发生冲突时，利用该次冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法不易产生“聚集”（Cluster），但增加了计算时间。
建立一个公共溢出区

三、载荷因子:

$\alpha = 填入表中的元素个数 / 散列表的长度$

四、C++ STL:

unordered_map :

#include<unordered_map>

参数模板：

template < class Key,                                    // unordered_map::key_type
           class T,                                      // unordered_map::mapped_type
           class Hash = hash<Key>,                       // unordered_map::hasher
           class Pred = equal_to<Key>,                   // unordered_map::key_equal
           class Alloc = allocator< pair<const Key,T> >  // unordered_map::allocator_type
           > class unordered_map;

key
键值的类型。unordered_map中的每个元素都是由其键值唯一标识的。
T
映射值的类型。unordered_map中的每个元素都用来存储一些数据作为其映射值。
Hash
一种一元函数对象类型，它接受一个key类型的对象作为参数，并根据该对象返回size_t类型的唯一值。这可以是一个实现函数调用操作符的类，也可以是一个指向函数的指针(参见构造函数)。默认为 $ha s h < Key >$ 。
Pred
接受两个键类型参数并返回bool类型的二进制谓词。表达式pred (a, b), pred是这种类型的一个对象,a和b是键值,返回true,如果是应考虑相当于b。这可以是一个类实现一个函数调用操作符或指向函数的指针(见构造函数为例)。这默认为equal_to，它返回与应用相等操作符(a==b)相同的结果。
Allloc
用于定义存储分配模型的allocator对象的类型。默认情况下，使用allocator类模板，它定义了最简单的内存分配模型，并且与值无关。

使用样例：

LeetCode: 两数之和

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

unordered_map和map的区别：

map :
map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自动排序的功能，因此map内部的所有元素都是有序的，红黑树的每一个节点都代表着map的一个元素。因此，对于map进行的查找、删除，添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树（又名二叉查找树、二叉排序树–特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根结点的键值）存储的，使用中序遍历可将键值按照从小到大遍历出来。
?
unordered_map :
unordered_map内部实现了一个哈希表（也叫散列表，通过把关键码值映射到Hash表中一个位置来访问记录，查找的时间复杂度可达到O(1)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序都是无序的。