当前位置:   article > 正文

数据结构 - 哈希表(unordered_map)_unorderedmap m_hash_code

unorderedmap m_hash_code

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

  1. 哈希表wiki
  2. c++中unordered_map的用法的详述
  3. 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(km1)
其中 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...(m1)称为线性探测(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(km/2)称为平方探测(Quadratic Probing)。相对线性探测,相当于发生冲突时探测间隔 d i = i 2 d_{i}=i^{2} di=i2个单元的位置是否为空,如果为空,将地址存放进去。
d i = 伪随机数序列 d_{i}=伪随机数序列 di=伪随机数序列,称为伪随机探测
 
2. 聚集(Cluster,也翻译做“堆积”):
在函数地址的表中,散列函数的结果不均匀地占据表的单元,形成区块,造成线性探测产生一次聚集(primary clustering)和平方探测的二次聚集(secondary clustering),散列到区块中的任何关键字需要查找多次试选单元才能插入表中,解决冲突,造成时间浪费。对于开放定址法,聚集会造成性能的灾难性损失,是必须避免的。

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

三、载荷因子:

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

四、C++ STL:

unordered_map :

#include<unordered_map>
  • 1

参数模板:

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;

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  1. key
    键值的类型。unordered_map中的每个元素都是由其键值唯一标识的。
  2. T
    映射值的类型。unordered_map中的每个元素都用来存储一些数据作为其映射值。
  3. Hash
    一种一元函数对象类型,它接受一个key类型的对象作为参数,并根据该对象返回size_t类型的唯一值。这可以是一个实现函数调用操作符的类,也可以是一个指向函数的指针(参见构造函数)。默认为 h a s h < K e y > hash<Key> hash<Key>
  4. Pred
    接受两个键类型参数并返回bool类型的二进制谓词。表达式pred (a, b), pred是这种类型的一个对象,a和b是键值,返回true,如果是应考虑相当于b。这可以是一个类实现一个函数调用操作符或指向函数的指针(见构造函数为例)。这默认为equal_to,它返回与应用相等操作符(a==b)相同的结果。
  5. 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 {};
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

unordered_map和map的区别:

map :
map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素。因此,对于map进行的查找、删除,添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉搜索树 (又名二叉查找树、二叉排序树–特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根结点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来。

unordered_map :
unordered_map内部实现了一个哈希表 (也叫散列表,通过把关键码值映射到Hash表中一个位置来访问记录,查找的时间复杂度可达到O(1),其在海量数据处理中有着广泛应用)。因此,其元素的排列顺序都是无序的。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码世界探险家/article/detail/61302
推荐阅读
相关标签
  

闽ICP备14008679号