轻松做网站,做基础工程分包应上什么网站,配置网站域名,常见的微网站平台有哪些目录 介绍优缺点概念哈希函数快速的计算键类型键转索引霍纳法则 均匀的分布 哈希冲突链地址法开放地址法线性探测二次探测再哈希法 扩容/缩容实现哈希创建哈希表质数判断哈希函数插入修改获取数据删除数据扩容/缩容函数全部代码 哈希表#xff08;Hash Table#xff09;… 目录 介绍优缺点概念哈希函数快速的计算键类型键转索引霍纳法则 均匀的分布 哈希冲突链地址法开放地址法线性探测二次探测再哈希法 扩容/缩容实现哈希创建哈希表质数判断哈希函数插入修改获取数据删除数据扩容/缩容函数全部代码 哈希表Hash Table又称散列表是一种数据结构它使用键值对Key-Value Pair来存储数据并通过哈希函数将键映射到数组的特定位置从而实现高效的查找、插入和删除操作。哈希表通常被用在需要快速查找的场景例如数据库索引、缓存和符号表等
介绍
哈希表本质上就是一个数组只不过数组存放的是单一的数据而哈希表中存放的是键值对key - value pair 在哈希表中每个键key与一个值value相关联并且是通过键来查找值的 为了实现快速查找哈希表会通过一个哈希函数将键转换为一个哈希值 再将这个哈希值转换成一个索引用于存储或查找该键对应的值在数组中的位置
优缺点 优点 查找速度快在哈希函数设计合理的情况下哈希表可以在常数时间内完成查找、插入和删除操作 实现简单通过数组加链表或开放地址法可以轻松实现哈希表 缺点 空间浪费为了减少碰撞哈希表的容量通常要比实际存储的元素数量多造成了一定的空间浪费 不支持有序存储哈希表中元素的顺序与插入顺序无关不支持按序查找 哈希函数设计复杂哈希函数的设计对哈希表的性能至关重要设计不当的哈希函数会导致大量碰撞影响性能
概念
下面是哈希表中的一些概念后面也会具体学习 存储结构 哈希表通常由一个数组和一个哈希函数组成。数组的每个元素称为桶Bucket它可以存储一个或多个键-值对 哈希化Hashing是将输入数据通常是任意长度的通过哈希函数转换为固定长度的输出数组范围内下标的过程 哈希函数Hash Function 哈希函数将键转换成一个数组的索引即一个整数 哈希冲突Hash Collision 当不同的键被哈希函数映射到相同的索引时就发生了哈希冲突。常用的解决哈希冲突的方式有链地址法和开放地址法 装填因子Load Factor哈希表中存储的元素数量与数组大小总槽位数量的比率 哈希表的大小槽位数是固定的但存储的元素项数可以超过槽位数 装填因子表示哈希表空间的利用效率。较高的装填因子意味着表中存储的元素较多空间利用率高 当装填因子增加接近于 1 或更高 时哈希表的查找效率可能降低尤其是在使用开放地址法时冲突处理需要更多的探测次数 使用链地址法时装填因子的增加会导致链表长度增加从而提高平均查找时间 在动态哈希表中当装填因子超过某个阈值如 0.75通常会触发哈希表的扩容以减少冲突和提高性能 如果装填因子过低可能会导致缩容以节省空间 理想的装填因子 开放地址法理想的装填因子通常低于 1推荐在 0.5 到 0.75 之间以平衡空间利用和查找效率 链地址法装填因子可以超过 1因为多个元素可以存储在同一个槽中。通常装填因子在 0.7 到 1.0 是较好的选择但也可以更高具体取决于链表长度对性能的影响 扩容Rehashing当哈希表的装载因子超过设定值时可能需要进行扩容。扩容通常包括创建一个更大的数组并重新计算所有键的哈希值以将它们映射到新数组中 缩容缩容是指在数据量减少到一定程度时减少哈希表的容量以节省空间并提高内存利用效率
哈希函数
哈希函数将键转换成一个数组的索引即一个整数
设计好的哈希函数应该具备哪些优点呢 快速的计算哈希表的优势就在于效率所以快速获取到对应的hashCode非常重要 均匀的分布哈希表中无论是链地址法还是开放地址法当多个元素映射到同一个位置的时候都会影响效率优秀的哈希函数应该尽可能将元素映射到不同的位置让元素在哈希表中均匀的分布
快速的计算
下面的三个模块知识都是为了理解计算问题为了快速地获取对应的hashCode
键类型
归根结底哈希函数就是将键key转换为索引值能作为键key的类型有很多数字、字符串、对象等等我们这里主要是学习字符串作为键因为哈希表的键通常被实现为字符串主要是出于以下几个原因 一致性使用字符串作为键可以提供一致的方式来处理不同类型的键。即使是数字和其他类型最终也会转换为字符串进行存储 哈希函数哈希表使用哈希函数将键映射到数组的索引。字符串通常更易于处理因为它们可以直接进行哈希运算而其他类型如对象可能需要更多的处理步骤 易于比较字符串具有明确的比较规则这使得查找、插入和删除操作变得更简单和高效 空间效率在许多语言中字符串作为键的存储方式通常比对象或其他复杂类型更紧凑减少了内存使用 灵活性字符串可以表示各种信息能够轻松适应不同的场景例如数据库索引、字段名称等
键转索引
理解了键的类型我们能想到就是哈希函数要将字符串转换为数字那这有什么方法那 方法一将字符的 ASCII 值相加问题就是很多键最终的值可能都是一样的比如was/tin/give/tend/moan/tick都是43 方法二使用一个常数乘以键的每个字符的 ASCII 值得到的数字可以基本保证它的唯一性下面解释和别的单词重复率大大降低问题是得到的值太大了因为这个值是要作为索引的创建这么大的数组是没有意义的 其实我们平时使用的大于10的数字可以用一种幂的连乘来表示它的唯一性 比如7654 7*10³ 6*10² 5*10 4 单词也可以使用这种方案来表示比如 cats 3*27³ 1*27² 20*27 17 6033727是因为有27个字母 那么对于获取到的索引太大这个问题又出现了压缩算法即把幂的连乘方案中得到的巨大整数范围压缩到可接受的数组范围中 如何压缩呢 有一种简单的方法就是使用取余操作符它的作用是得到一个数被另外一个数整除后的余数 举个例子理解先来看一个小点的数字 范围压缩到一个小点的空间中假设把从0~199的数字压缩为从0~9的数字 我们能想到当一个数被10整除时余数一定在0~9之间比如13 % 10 3157 % 10 7 同理数组的索引是有限的比如从 0 到 n-1其中 n 是可接受的数组长度通过对进行取余操作可以将它们限制在这个范围内 设 hash 是通过哈希函数得到的键的哈希值n 是数组的长度索引可以通过 index hash % n 计算得出 在某些情况下哈希值可能是负数。为了确保得到的索引是非负的可以使用以下公式index ((hash % n) n) % n
霍纳法则
上面计算哈希值的时候使用的方式cats 3*27³ 1*27² 20*27 17 60337那么这种计算方式会进行几次乘法几次加法呢 我们可以抽象成一个表达式a(n)x^n a(n-1)x^(n-1) ... a(1)x a(0) 乘法次数n (n-1) ... 1 n(n 1)/2 加法次数n次 时间复杂度O(N²) 通过变换可以得到一种快得多的算法即解决这类求值问题的高效算法霍纳法则在中国被称为秦九韶算法 Pn(x) a(n)x^n a(n-1)x^(n-1) ... a(1)x a(0) (((a(n)x a(n−1))x a(n−2))x ⋯)x a1)x a0 下面我们用具体数字理解一下 乘法次数n次 加法次数n次 时间复杂度从 O(N²) 降到了 O(N)
均匀的分布 在设计哈希表时已经处理映射到相同下标值的情况链地址法或者开放地址法文章后面详细讲解 但是无论哪种方案都是为了提高效率最好的情况还是让数据在哈希表中均匀分布 因此需要在使用常量的地方尽量使用质数 比如哈希表的长度和N次幂的底数(我们之前使用的是27) 为什么他们使用质数会让哈希表分布更加均匀呢 质数和其他数相乘的结果相比于其他数字更容易产生唯一性的结果减少哈希冲突 Java中的HashMap的N次幂的底数选择的是31比较常用的数是31或37是经过长期观察分布结果得出的 举个例子 如果使用 10 作为模数数组长度取模那么所有以 0 或 5 结尾的数都会被映射到同一个槽位 但如果使用质数 11则可以有效地避免这种情况因为 11 没有因数是 2 或 5它能使得键值分布更加均匀
哈希冲突
比如经过哈希化后demystify和melioration得到的下标相同那怎么放入数组中那就是当不同的键被哈希函数映射到相同的索引时就发生了哈希冲突。常用的解决哈希冲突的方式有链地址法和开放地址法
链地址法
链地址法是一种比较常见的解决冲突的方案(也称为拉链法) 每个哈希表的槽bucket可以存储多个元素。当多个键被哈希到同一个索引时链地址法会将这些元素存储在一个链表或其他数据结构中 链地址法的核心思想是将每个数组元素作为一个桶桶内存储多个键值对。通常使用链表或数组来实现 一旦发现重复将重复的元素插入到链表的首端或者末端即可 当查询时先根据哈希化后的下标值找到对应的位置再取出链表依次查询找寻找的数据 效率 哈希表中共有 N 个数据项有 arraySize 个槽位每个槽位中的链表长度大致相同怎么计算每个链表的平均长度 假设arraySize 10哈希表中有 10 个槽位N 50哈希表中有 50 个数据项平均每个链表中大约有 5 个数据项通过将总的数据项数 N 除以槽位数 arraySize 来得到公式就是装填因子loadFactor 当用链地址法实现哈希表时查找一个元素的过程分为两部分 计算哈希值并定位到槽位这一步是一个常数时间操作通常是 1 次操作不依赖链表的长度 遍历链表查找元素如果多个元素在同一个槽位上哈希表会在这个槽位的链表中查找元素。查找的平均次数是链表长度的一半通常是 loadFactor / 2 因此成功可能只需要查找链表的一半即可1 loadFactor/2不成功可能需要将整个链表查询完才知道不成功1 loadFactor 链地址法相对来说效率是好于开放地址法的所以在真实开发中使用链地址法的情况较多 它不会因为添加了某元素后性能急剧下降比如在Java的HashMap中使用的就是链地址法
开放地址法
开放地址法的主要工作方式是当发生哈希冲突时寻找数组中的下一个空槽来存储冲突的元素比如下图中插入38时应该在05的位置但被49占了那么38应该放在哪个位置有三种探索空槽的方式线性探测、二次探测和再哈希法
线性探测
线性探测Linear Probing是每次发生冲突时检查下一个空白的槽index (hashFunc(key) i) % tableSize; // i 是冲突次数 插入38时 经过哈希化得到的index 5但是在插入的时候发现该位置已经有了49 线性探测就是从index 1位置开始一点点查找空的位置来放置38 查询38时 首先经过哈希化得到index 5看5的位置结果和查询的数值是否相同 相同那么就直接返回不相同就线性查找从index 1位置开始查找和38一样的 注意查询过程有一个约定就是查询到空位置就停止 删除38时 删除操作一个数据项时不可以将这个位置下标的内容设置为null为什么呢 因为将它设置为null可能会影响之后查询其他操作 通常删除一个位置的数据项时可以将它进行特殊处理(比如设置为-1) 当看到-1位置的数据项时就知道查询时要继续查询但是插入时这个位置可以放置数据 效率公式来自于Knuth(算法分析领域的专家现代计算机的先驱人物) 问题 线性有一个比较严重的问题就是聚集 比如在没有任何数据的时候插入的是22-23-24-25-26那么意味着下标值0-1-2-3-4的位置都有元素这种一连串填充单元就叫做聚集 聚集会影响哈希表的性能无论是插入/查询/删除都会影响比如我们插入一个38会发现连续的单元都不允许放置数据并且在这个过程中需要探索多次
二次探测
二次探测Quadratic Probing根据冲突次数的平方来确定下一个槽的位置 index (hashFunc(key) i^2) % tableSize 优化线性问题 线性探测可以看成是步长为1的探测比如从下标值x开始那么线性测试就是x1x2x3依次探测 二次探测对步长做了优化比如从下标值x开始x1²x2²x3²这样就可以一次性探测比较长的距离比避免那些聚集带来的影响 效率 问题 二次探测依然存在问题比如连续插入的是32-112-82-2-192那么依次累加的时候步长的相同的 也就是这种情况下会造成步长不一样的一种聚集还是会影响效率
再哈希法
再哈希Double Hashing使用第二个哈希函数计算步长确定下一个槽的位置 index (hashFunc1(key) i * (constant - (hashFunc2(key) % constant))) % tableSize 优化二次探测问题 二次探测的算法产生的探测序列步长是固定的: 1-4-9-16依此类推 把键用另外一个哈希函数再做一次哈希化用这次哈希化的结果作为步长 第二次哈希化需要具备如下特点: 和第一个哈希函数不同(不要再使用上一次的哈希函数了, 不然结果还是原来的位置) 不能输出为0(否则将没有步长每次探测都是原地踏步算法就进入了死循环) 计算机专家已经设计出一种工作很好的哈希函数stepSize constant - (hanshFunc(key) % constant)constant是质数且小于数组的容量 效率
扩容/缩容 为什么扩容/缩容 随着数据量的增多每一个index对应的bucket会越来越长也就造成效率的降低所以在合适的情况对数组进行扩容比如扩容两倍 当哈希表的装填因子元素数量与哈希表容量的比值低于某个阈值时会考虑缩容以节省空间并提高内存利用效率 如何进行扩容/缩容 扩容可以简单的将容量增大两倍但是这种情况下所有的数据项一定要同时进行修改(重新调用哈希函数来获取到不同的位置) 比如hashCode 12的数据项在arraySize 8的时候放index 4的位置在arraySize 16的时候放index 12的位置 缩容时通常将哈希表容量减小为当前容量的一半并重新计算并分配所有现有元素的位置 这是一个耗时的过程但是如果数组需要扩容那么这个过程是必要的 什么情况下扩容/缩容 比较常见的情况是 loadFactor 0.75的时候进行扩容比如Java的哈希表就是在装填因子大于0.75的时候对哈希表进行扩容 通常会设置一个下限装填因子比如 0.25低于此值时触发缩容但也要避免过度缩容通常会设置一个较小的、合理的最小容量比如 7 或 8以保证哈希表即使在元素很少时也保持一定的容量从而避免频繁地扩容和缩容
实现哈希
上面学了那么多的理论和公式我们要用代码自己实现一个哈希表在实现之前我们先理清楚实现的方案和结构这样当我们实现操作方法时才能更清晰的知道要做什么 方案使用链地址法处理冲突 链地址法的核心思想是将每个数组元素作为一个桶桶内存储多个键值对 通常使用链表或数组来实现我们使用数组实现因为数组是js/ts已经提供给我们的数据结构想用链表后面自己练习吧需要自己再实现链表结构参考文章https://blog.csdn.net/qq_45730399/article/details/143408205 用上面方案实现的存储结构如下[[[key1, value1], [key2, value2]], [[key3, value3]]] 哈希表的桶中每个元素还是一个数组桶这个数组桶中放的是多个键值对元组[key1, value1]为什么使用数组包裹键值对而不是对象{key1: value1} 键值对元组数组[[key1, value1], [key2, value2]] 轻松处理多个相同键名对应不同值的情况访问时可以直接通过遍历数组查找特定键的元组逻辑清晰比如在 get(name) 时只需查找数组中第一项等于 name 的元组取第二项作为值 对象数组[{key1: value1}, {key2: value2}] 对象中每个键只能出现一次意味着如果需要存储相同键名的不同值 查找某个键的值时需要遍历整个数组并访问对象的属性 需要额外的逻辑来查找特定的键因为每个对象的结构不一致效率较低
创建哈希表
定义三个属性
storage作为数组数组中存放相关的元素count表示当前已经存在了多少数据length用于标记数组中一共可以存放多少个元素
class HashTableT any {storage: [string, T][][] []; // [[[key1, value1], [key2, value2]], [[key3, value3]]]private count: number 0; // 已经存在了多少数据private length: number 11; // 数组中一共可以存放多少个元素
}
const hashTable new HashTable()质数判断
上面理论知识我们也解析了为什么要用质数既然要用质数就需要判断一个数是不是质数质数表示大于1的自然数中只能被1和自己整除的数 简单实现 isPrime(num: number): boolean {for (let i 2; i num; i) {if (num % i 0) return false;}return true;
}高效实现 只需要检查它是否能被小于等于其平方根的数整除这是因为如果 num 能被一个大于其平方根的数整除那么另一个因数必定小于其平方根 isPrime(num: number): boolean {const sqrt Math.sqrt(num)for (let i 2; i sqrt; i) {if (num % i 0) return false}return true
}哈希函数
hashFunc(key: string): number {let code 0;for (let i 1; i key.length; i) {code 31 * code key.charCodeAt(i); // 使用霍纳法则}return code % this.length;
}插入修改
put(key: string, value: T): void {// 1.根据key获取数组中对应的索引值const index this.hashFunc(key);// 2.取出索引值对应位置的数组(桶)let bucket this.storage[index];// 3.判断bucket是否有值if (!bucket) {bucket [];this.storage[index] bucket;}// 4.确定已经有一个数组了, 但是数组中是否已经存在key是不确定的let isUpdate false;for (let i 0; i bucket.length; i) {if (bucket[i][0] key) {bucket[i][1] value;isUpdate true;break;}}if (!isUpdate) {bucket.push([key, value]);this.count;}
}获取数据
get(key: string): T | undefined {// 1.根据key获取索引值indexconst index this.hashFunc(key);// 2.获取bucket(桶)const bucket this.storage[index];if (!bucket) return undefined;// 3.对bucket进行遍历for (let i 0; i bucket.length; i) {if (bucket[i][0] key) return bucket[i][1];}return undefined;
}删除数据
delete(key: string): T | null {// 1.根据key获取索引值indexconst index this.hashFunc(key);// 2.获取bucket(桶)const bucket this.storage[index];if (!bucket) return null;// 2.删除key项for (let i 0; i bucket.length; i) {let tuple bucket[i];if (tuple[0] key) {bucket.splice(i, 1);this.count--;return tuple[1];}}return null;
}扩容/缩容函数
resize(): void {// 装填因子大于0.75时扩容length两倍const isReduce this.count / this.length 0.75;const isExpand this.count / this.length 0.25;const newLength isReduce? this.getPrime(this.length * 2) : isExpand? this.getPrime(this.length / 2): this.length;if(newLength this.length) return// 扩容/缩容后清空数据并再次循环数据重新put进哈希表let oldStorage this.storage;this.storage [];this.count 0;this.length newLength;oldStorage.forEach((bucket) {if (!bucket) return;bucket.forEach((f) {this.put(f[0], f[1]);});});
}全部代码
class HashTableT any {storage: [string, T][][] []; // [[[key1, value1], [key2, value2]], [[key3, value3]]]private count: number 0; // 已经存在了多少数据private length: number 7; // 数组中一共可以存放多少个元素// 判断质数private isPrime(num: number): boolean {const sqrt Math.floor(Math.sqrt(num));for (let i 2; i sqrt; i) {if (num % i 0) return false;}return true;}// 获取质数private getPrime(num: number): number {let prime Math.floor(num);while (!this.isPrime(prime)) {prime;}return prime;}// 哈希函数private hashFunc(key: string): number {let code 0;for (let i 0; i key.length; i) {code 31 * code key.charCodeAt(i); // 使用霍纳法则}return code % this.length;}// 扩容/缩容private resize(newLength: number): void {// 扩容/缩容后清空数据并再次循环数据重新put进哈希表let oldStorage this.storage;this.storage [];this.count 0;this.length this.getPrime(newLength) 7 ? 7 : this.getPrime(newLength);oldStorage.forEach((bucket) {if (!bucket) return;bucket.forEach((f) {this.put(f[0], f[1]);});});}// 插入/修改数据put(key: string, value: T): void {// 1.根据key获取数组中对应的索引值const index this.hashFunc(key);// 2.取出索引值对应位置的数组(桶)let bucket this.storage[index];// 3.判断bucket是否有值if (!bucket) {bucket [];this.storage[index] bucket;}// 4.确定已经有一个数组了, 但是数组中是否已经存在key是不确定的let isUpdate false;for (let i 0; i bucket.length; i) {if (bucket[i][0] key) {bucket[i][1] value;isUpdate true;break;}}if (!isUpdate) {bucket.push([key, value]);this.count;if (this.count / this.length 0.75) {this.resize(this.length * 2); // 扩容处理}}}// 获取数据get(key: string): T | null {// 1.根据key获取索引值indexconst index this.hashFunc(key);// 2.获取bucket(桶)const bucket this.storage[index];if (!bucket) return null;// 3.对bucket进行遍历for (let i 0; i bucket.length; i) {if (bucket[i][0] key) return bucket[i][1];}return null;}// 删除数据delete(key: string): T | null {// 1.根据key获取索引值indexconst index this.hashFunc(key);// 2.获取bucket(桶)const bucket this.storage[index];if (!bucket) return null;// 2.删除key项for (let i 0; i bucket.length; i) {let tuple bucket[i];if (tuple[0] key) {bucket.splice(i, 1);this.count--;if (this.length 7 this.count / this.length 0.25) {this.resize(this.length / 2); // 缩容处理}return tuple[1];}}return null;}
}const hashTable new HashTable();
hashTable.put(aaa, 100);
hashTable.put(aaa, 200);
hashTable.put(bbb, 300);
hashTable.put(ccc, 400);
hashTable.put(abc, 111);
hashTable.put(cba, 222);
console.log(111, hashTable.storage);
/*
111 [[ [ bbb, 300 ] ],[ [ aaa, 200 ], [ cba, 222 ] ],4 empty items,[ [ ccc, 400 ], [ abc, 111 ] ]]
*/// 如果loadFactor 0.75进行扩容操作
hashTable.put(nba, 333);
hashTable.put(mba, 444);
console.log(222, hashTable.storage);
/* 222 [2 empty items,[ [ mba, 444 ] ],3 empty items,[ [ bbb, 300 ] ],4 empty items,[ [ nba, 333 ] ],1 empty item,[ [ ccc, 400 ] ],[ [ cba, 222 ] ],[ [ abc, 111 ] ],[ [ aaa, 200 ] ]]
*/hashTable.delete(nba);
hashTable.delete(mba);
hashTable.delete(abc);
hashTable.delete(cba);
hashTable.delete(aaa);
console.log(333, hashTable.storage); // 333 [ [ [ bbb, 300 ] ], 5 empty items, [ [ ccc, 400 ] ] ]
