Algorithm-Pattern
  • Introduction
  • C & C++
    • C语言
      • C/C++编译器
      • 宏的使用
      • 编译过程
      • 指针 & 数组
      • 柔性数组
      • 函数指针 & 回调函数
      • C标准库之stdio
      • C标准库之string
      • C标准库之errno
      • C标准库之stdarg
      • C标准库之regex
    • C++基础语法
      • 自增(++) & 自减(--)
      • c语言到c++
      • 可变模板参数
      • 强制类型转换
      • C/C++类型转换的本质
      • 指针 & 引用
      • const的用法
      • static的用法
      • 重要的关键字(一)
      • 重要的关键字(二)
      • 内存申请和释放
      • 内联函数
      • 函数 & 运算符重载
      • 面向对象之封装
      • 构造函数 & 析构函数
      • 面向对象之继承
      • 面向对象之多态
      • 泛型编程
      • 异常
      • 再谈函数指针
    • C++并发编程
      • C++的锁
      • 并发与多线程
    • C++高级特性
      • 函数对象
      • 移动语义 & 完美转发
      • lambda表达式
      • RTTI技术
      • RAII技术
      • 智能指针
      • 模板的特化
      • C++静态库和动态库
      • 内存溢出和内存泄漏
    • STL基础
      • String
      • array/vector/list
      • deque/priority_queue
      • set/map
      • unordered_set/unordered_map
      • algorithm_1
      • functional
      • allocator
    • C++标准库
      • IO
      • Tuple
      • regex
      • bitset
      • numeric
    • STL深入源码
      • vector内部实现
      • deque内部实现
      • sort函数实现
    • 第三方库
      • JsonCpp
      • ProtoBuf
  • 数据结构
    • 线性表
    • 字符串
    • 栈和队列
    • 二叉树
    • 平衡二叉树
    • 平衡多路搜索树
    • 树结构的延申
    • 图
    • 二进制
    • 散列表
  • 算法基础
    • 排序算法
    • 查找算法
    • 数学问题
    • 并查集
    • 递归算法
    • 附加——主定理
    • Catalan数
  • 算法设计思想
    • 滑动窗口思想
    • BFS/DFS
    • 二分法
    • 回溯法
    • 贪心算法
    • 分治法
    • 动态规划
    • 分支限界算法
    • 有限状态机(FSM)
  • LeetCode系列
    • 死磕二叉树
    • 股票买卖问题
    • 打家劫舍问题
    • 跳跃游戏问题
    • 括号匹配问题
    • 石子游戏问题
    • 子序列问题
    • 数组 & 矩阵
    • 排列 & 组合
  • 经典算法问题
    • 几何问题
    • 区间问题
    • 背包问题
    • 石子堆问题
    • 表达式求值
  • 面试题
    • 数据结构和算法基础
    • 程序设计题
      • 实现双线程交替打印
      • C++实现读写锁
      • 实现阻塞队列
      • 实现环形队列
      • 实现线程池
      • 实现智能指针
      • 实现string类
      • 实现高性能local cache
      • 实现内存池
      • 生产者-消费者模型
      • 设计定时器
    • 经典的算法题
    • C++面试题总结
    • 面试算法题总结
由 GitBook 提供支持
在本页
  • 基础知识
  • 1、基本概念
  • 2、构造散列函数的方法
  • 3、解决冲突的方法
  • 例题
  • 1、TwoSum 问题

这有帮助吗?

  1. 数据结构

散列表

上一页二进制下一页排序算法

最后更新于4年前

这有帮助吗?

哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

基础知识

1、基本概念

若关键字为 ,则其值存放在 的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数,按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址,即 ,而 ,这种现象称为冲突(或碰撞,英语:Collision)。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数 和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数(Uniform Hash function),这就使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

2、构造散列函数的方法

直接定址法:取关键字或关键字的某个线性函数值为散列地址。即 或 , 其中为常数(这种散列函数叫做自身函数)

数字分析法:假设关键字是以r为基的数,并且哈希表中可能出现的关键字都是事先知道的,则可取关键字的若干数位组成哈希地址。

平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。

折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。

除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 即 , 。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对的选择很重要,一般取素数或,若选择不好,容易产生冲突。

3、解决冲突的方法

1、拉链法

如果再要插入元素20,则在下标为6的位置存储表头,而表的内容是13和20。这种方法的特点是需要另外分配新的单元来存储散列到同一个位置的数据。

查找的时候,除了根据计算出来的散列值找到对应位置外,还需要在链表上进行搜索。而在单链表上的查找速度是很慢的。因此可以考虑其他搜索速度较快的数据结构,就可以大大提高搜索速度。另外散列函数如果设计得好,冲突的概率其实也会很小。

2、开放定址法

而开放定址法的思想是,如果冲突发生,就选择另外一个可用的位置。而开放定址法中也有常见的几种策略。

  • 线性探测法

但这种方式的一个问题是,可能造成一次聚集,因为一旦冲突发生,为了处理冲突就会占用下一个位置,而如果冲突较多时,就会出现数据都聚集在一块区域。这样就会导致任何关键字都需要多次尝试才可能解决冲突。

  • 平方探测法

顾名思义,如果说前面的探测函数是 F(i)=i×7F(i)=i\times 7F(i)=i×7 ,那么平方探测法就是F(i)=i2×7F(i)=i^2\times 7F(i)=i2×7。 但是这也同样会产生二次聚集问题。

  • 双散列

为了避免聚集,在探测时选择跳跃式的探测,即再使用一个散列函数,用来计算探测的位置。假设前面的散列函数为hash1(X),用于探测的散列函数为hash2(X),那么一种流行的选择是F(i)=i×hash2(X)F(i)=i\times hash2(X)F(i)=i×hash2(X),即第一次冲突时探测hash1(X)+hash2(X)的位置,第二次探测hash1(X)+2hash2(X)的位置。

可以看到,无论是哪种开放定址法,它都要求表足够大。

3、再散列

散列表可以认为是具有固定大小的数组,那么如果插入新的数据时散列表已满,或者散列表所剩容量不多该怎么办?这个时候就需要再散列,常见做法是,建立一个是原来两倍大小的散列表,将原来表中的关键字重新散列到新表中。(参考Redis中再散列的方式)

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

vector<int> twoSum(vector<int>& nums, int target) {
    std::unordered_map<int, int> ihash;
    for(int i = 0;i < nums.size(); ++i){
        int tar = target - nums[i];
        if(ihash.count(tar) && ihash[tar] != i)
        {
            return std::vector<int>{ihash[tar], i}; // 不能反过来
        }
        ihash[nums[i]] = i;  // 必须在后面加进去,否则会被覆盖
    }
    return std::vector<int>{};
}

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。

std::vector<std::vector<int>> HashTable::threeSum(std::vector<int>& nums)
{
    sort(nums.begin(), nums.end()); // 为了去重
    int len = nums.size();
    vector<vector<int>> result;
    for(int i = 0; i < len; ++i){
        std::unordered_map<int, int> ihash;
        for(int j = i + 1;j < len; ++j){
            int tar = 0 - nums[i] - nums[j];
            if(ihash.count(tar) && ihash[tar] != j)
            {
                vector<int> temp{nums[i], nums[ihash[tar]], nums[j]};
                result.push_back(temp); //反过来
                int t = nums[j];
                while(++j < len && t == nums[j]);  // 去重
                --j;
            }
            ihash[nums[j]] = j;
        }
        int t = nums[i];
        while(++i < len && t == nums[i]); // 去重
        --i;
    }
    return result;
}

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。注意:答案中不可以包含重复的四元组。

分离链接法的做法是将同一个值的关键字保存在同一个表中。例如,对于前面:

还是以前面的为例:

如果此时再要插入20,则20 % 7 = 6,但是6的位置已有元素,因此探测下一个位置(6+1)%7,在这里就是下标为0的位置。因此20的存储位置如下:

例题

1、

✏️
🖋️
TwoSum 问题
3Sum
4Sum
✏️
🖋️
🖋️
🖋️
f(k)
f(k)
k
k
k1≠k2
f(k1)=f(k2)
hash(k)=k
hash(k)=a \cdot k+b
a b
hash(k)=k\,{\bmod {\,}}p
p\leq m
p
m
p