赞
踩
面试问到哈希表,一时间发现很久不用该数据结构了,因此来梳理一下。
参考网址:
散列表(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 = 填入表中的元素个数 / 散列表的长度 α=填入表中的元素个数/散列表的长度
#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类型的唯一值。这可以是一个实现函数调用操作符的类,也可以是一个指向函数的指针(参见构造函数)。默认为 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类模板,它定义了最简单的内存分配模型,并且与值无关。
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 {};
}
};
map :
map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。因此,对于map进行的查找、删除,添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树 (又名二叉查找树、二叉排序树–特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根结点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来。
unordered_map :
unordered_map内部实现了一个哈希表 (也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序都是无序的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。