面试问到哈希表，一时间发现很久不用该数据结构了，因此来梳理一下。
参考网址：
- 哈希表wiki
- c++中unordered_map的用法的详述
- unordered_map使用详解
一、定义：
散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
二、冲突：
冲突定义：
对不同的关键字可能得到同一散列地址，即
k
1
≠
k
2
k_{1}\neq k_{2}
k1?=k2?，而
f
(
k
1
)
=
f
(
k
2
)
f(k_{1})=f(k_{2})
f(k1?)=f(k2?)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。
冲突解决：
为了知道冲突产生的相同散列函数地址所对应的关键字，必须选用另外的散列函数，或者对冲突结果进行处理。而不发生冲突的可能性是非常之小的，所以通常对冲突进行处理。常用方法有以下几种：
?
1. 开放定址法:
越是质数，mod取余就越可能均匀分布在表的各处。
h
a
s
h
i
=
(
h
a
s
h
(
k
e
y
)
+
d
i
)
?
?
m
o
d
??
m
,
i
=
1
,
2...
k
?
(
k
≤
m
?
1
)
hash_{i}=(hash(key)+d_{i})\,{\bmod \,}m, i=1,2...k\,(k\leq m-1)
hashi?=(hash(key)+di?)modm,i=1,2...k(k≤m?1)，
其中
h
a
s
h
(
k
e
y
)
hash(key)
hash(key)为散列函数，
m
m
m为散列表长，
d
i
d_{i}
di?为增量序列，
i
i
i为已发生冲突的次数。
增量序列可有下列取法：
d
i
=
1
,
2
,
3...
(
m
?
1
)
d_{i}=1,2,3...(m-1)
di?=1,2,3...(m?1)称为线性探测(Linear Probing)；即
d
i
=
i
d_{i}=i
di?=i，或者为其他线性函数。相当于逐个探测存放地址的表，直到查找到一个空单元，把散列地址存放在该空单元。
d
i
=
±
1
2
,
±
2
2
,
±
3
2
.
.
.
±
k
2
(
k
≤
m
/
2
)
d_{i}=\pm 1^{2},\pm 2^{2},\pm 3^{2}...\pm k^{2} (k\leq m/2)
di?=±12,±22,±32...±k2(k≤m/2)称为平方探测(Quadratic Probing)。相对线性探测，相当于发生冲突时探测间隔
d
i
=
i
2
d_{i}=i^{2}
di?=i2个单元的位置是否为空，如果为空，将地址存放进去。
d
i
=
伪随机数序列
d_{i}=伪随机数序列
di?=伪随机数序列，称为伪随机探测。
?
2. 聚集（Cluster，也翻译做“堆积”）:
在函数地址的表中，散列函数的结果不均匀地占据表的单元，形成区块，造成线性探测产生一次聚集（primary clustering）和平方探测的二次聚集（secondary clustering），散列到区块中的任何关键字需要查找多次试选单元才能插入表中，解决冲突，造成时间浪费。对于开放定址法，聚集会造成性能的灾难性损失，是必须避免的。
- 单独链表法：将散列到同一个存储位置的所有元素保存在一个链表中。实现时，一种策略是散列表同一位置的所有冲突结果都是用栈存放的，新元素被插入到表的前端还是后端完全取决于怎样方便。
- 双散列。
- 再散列：
h
a
s
h
i
=
h
a
s
h
i
(
k
e
y
)
,
i
=
1
,
2...
k
。
h
a
s
h
i
hash_{i}=hash_{i}(key), i=1,2...k。hash_{i}
hashi?=hashi?(key),i=1,2...k。hashi?是一些散列函数。即在上次散列计算发生冲突时，利用该次冲突的散列函数地址产生新的散列函数地址，直到冲突不再发生。这种方法不易产生“聚集”（Cluster），但增加了计算时间。
建立一个公共溢出区
三、载荷因子:
α
=
填入表中的元素个数
/
散列表的长度
\alpha = 填入表中的元素个数 / 散列表的长度
α=填入表中的元素个数/散列表的长度
四、C++ STL:
unordered_map :
#include<unordered_map>
参数模板：
template < class Key,
class T,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator< pair<const Key,T> >
> class unordered_map;
- key
键值的类型。unordered_map中的每个元素都是由其键值唯一标识的。 - T
映射值的类型。unordered_map中的每个元素都用来存储一些数据作为其映射值。 - Hash
一种一元函数对象类型，它接受一个key类型的对象作为参数，并根据该对象返回size_t类型的唯一值。这可以是一个实现函数调用操作符的类，也可以是一个指向函数的指针(参见构造函数)。默认为
h
a
s
h
<
K
e
y
>
hash<Key>
hash<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)，其在海量数据处理中有着广泛应用）。因此，其元素的排列顺序都是无序的。
|