哈希函数
哈希函数
哈希的过程中需要使用哈希函数进行计算。
哈希函数是一种映射关系，根据数据的关键词 key ，通过一定的函数关系，计算出该元素存储位置的函数。
表示为：
几种常见的哈希函数（散列函数）构造方法
- 直接定址法
- 除留余数法
- 数字分析法
- 平方取中法
- 折叠法（叠加法）
- 随机数法
哈希冲突的解决
选用哈希函数计算哈希值时，可能不同的 key 会得到相同的结果，一个地址怎么存放多个数据呢？这就是冲突。
解决方法：
- 将所有关键字为同义词的结点链接在同一个单链表中
- 开放定址法
- 当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
- 线性探查法
- 二次探查法
- 双重散列法
- 当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 笺札！
相关推荐
2026-03-29
Brute Force算法
Brute Force算法 基本概念 Brute Force 算法：简称为 BF 算法，也可以叫做「朴素匹配算法」。 Brute Force 算法核心思想：将模式串 pp 依次与文本串 TT 的每个起点对齐，从左到右逐字符比对；相等则继续，不等则把对齐起点右移一位，直到匹配成功或遍历完文本。 算法步骤 设文本串T长度为n，模式串p长度为m 设T的每个七点0…n-m依次与p对齐，逐字符比较：如果相等则继续，不相等则起点右移一位、p归零 如果某次对齐能把p的全部字符匹配完，则返回该起点；否则无解 内部实现： 1234567891011121314def bruteForce(T:str,p:str)->int: n,m=len(T),len(p) i,j=0,0 while i < n and j < m: if T[i]==p[j]: i+=1 j+=1 else: i=i-j+1 j=0 if j==m: return i-j else: return -1 复杂度分析 BF 简单直观，但因不匹配时会完全回退、重...
2026-04-06
Boyer Moore 算法
Boyer Moore 算法 基本概念 Boyer Moore 算法（BM 算法）：由 Robert S. Boyer 和 J Strother Moore 于 1977 年提出，是一种高效的字符串搜索算法，实际应用中通常比 KMP 算法快 3~5 倍。 BM 算法核心思想：先对模式串 p 预处理，生成辅助表。在匹配过程中，如果文本串T某字符与模式串p不匹配，通过启发式规则，直接跳过不可能匹配的位置，将模式串整体向后滑动多位。 算法步骤 计算文本串T的长度n和模式串p的长度m。 对模式串p进行预处理，分别生成坏字符表bc_table和好后缀规则后移位数表 gs_table。 将模式串p的头部与文本串T的当前位置i对齐，初始i=0。每次从模式串的末尾（j=m−1）开始向前逐位比较： 如果 T[i+j]与 p[j]T[i+j]与 p[j]T[i+j]与 p[j]相等，则继续向前比较下一个字符。 如果模式串所有字符均匹配，则返回当前匹配的起始位置 ii。 如果 T[i+j]与p[j]T[i+j]与p[j]T[i+j]与p[j] 不相等： 分别根据坏字符表和好后缀表...
2026-04-06
Horspool 算法
Horspool 算法 基本概念 Horspool 算法是 Boyer-Moore 算法的一种简化版本，由 Nigel Horspool 于 1980 年提出。它仅使用 Boyer-Moore 算法中的“坏字符规则”，舍弃了“好后缀规则”，因此实现更简单，但在大多数实际场景中依然具有较高的效率。 核心思想：将模式串与文本串从左到右对齐，但从右向左进行字符比较。当发生不匹配时，根据文本串中当前对齐位置的字符（即造成失配的字符）在模式串中最右出现的位置，决定模式串向右移动的步数。这种跳跃策略能够跳过大量不可能匹配的位置，从而提升匹配速度。 算法步骤 预处理：构建一个位移表（也称坏字符表），记录模式串中每个字符在失配时应该移动的步数。 对于模式串 p 的长度 m，除最后一个字符外，每个字符 c 的位移值为 m - 1 - i，其中 i 是该字符在模式串中最后一次出现的位置（从 0 开始计数）。 对于不在模式串中的字符，位移值设为 m。 注意：若一个字符出现多次，只保留最右侧出现的位置。 匹配过程： 将模式串与文本串左端对齐，设文本指针 i = m - 1（指向文本串...
2026-03-29
KMP算法
KMP算法 基本概念 KMP 算法（全称 Knuth-Morris-Pratt 算法）：由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三位学者于 1977 年联合提出，并以他们的名字命名。 KMP 算法核心思想：在字符串匹配过程中，当文本串 TT 的某个字符与模式串 pp 发生不匹配时，充分利用已匹配的前缀信息，通过预处理得到的「部分匹配表」（即 next 数组），避免文本指针的回退，从而高效地减少不必要的比较次数，实现快速匹配。 算法步骤 next数组的构造 假设模式串为p。用left表示当前已知的最大相等前后缀的长度，right 表示当前正在处理的字符下标。初始时left = 0,right = 1 比较 p[left]p[left]p[left]和p[right]p[right]p[right]: 如果p[left]==p[right]p[left]==p[right]p[left]==p[right],当前前后缀可以继续延长。此时left+1,将next[right]next[right]next[right...
2026-04-06
Sunday 算法
Sunday 算法 基本概念 Sunday 算法是一种字符串匹配算法，由 Daniel M. Sunday 于 1990 年提出。它是对 Boyer-Moore 算法的简化与改进，仅使用一种启发式规则：当发生失配时，考察文本串中当前匹配窗口末尾的下一个字符（即 T[i+m]），并根据该字符在模式串中的最右出现位置决定模式串向右移动的步数。该规则通常能使模式串移动更远，从而在随机文本中获得极高的平均效率。 核心思想：匹配窗口从左向右滑动，但比较顺序通常从左到右（也可从右到左，但典型实现为从左到右）。当失配时，关注窗口之后的下一个字符 c，若 c 在模式串中出现，则将模式串向右移动，使 c 与模式串中该字符最后一次出现的位置对齐；否则，整个窗口跳过 c（即移动 m+1 位）。这种策略使算法在大部分情况下具有接近线性的时间性能。 算法步骤 预处理：构建一个位移表，记录模式串中每个字符最右边的位置（从 0 开始计数）。 对于模式串 p 中的每个字符 c，记录其最后出现的位置 lastPos[c]（若字符重复，只保留最右侧的索引）。 位移值（移动步数）的计算方法： 当失配...
2026-03-22
二分查找
二分查找 基本概念 二分查找算法（Binary Search Algorithm），又称折半查找或对数查找，是一种在有序数组中高效定位目标元素的方法。其核心思想是每次将查找区间缩小一半，从而快速锁定目标位置。 算法步骤 初始化：确定待查找的数据集合为有序数据 设置查找区间：定义查找的左右边界，初始时left指向数组起始位置，right指向数组末尾位置 计算中间下标：通过mid=(left+right)/2mid=(left+right)/2mid=(left+right)/2计算当前查找区间的中间下标mid 比较并缩小区间： 如果target==nums[mid]target==nums[mid]target==nums[mid],则找到目标，返回mid 如果target<nums[mid]target<nums[mid]target<nums[mid],目标在左半区间，更新右边界right=mid-1 如果target>nums[mid]target>nums[mid]target>nums[mid],目标在右半区间，更新左边界...
