算法学习(JavaScript实现)
栏目: JavaScript · 发布时间: 5年前
内容简介:这一章节内容主要是 HashTable,中文即哈希表,散列表等等。HashTable 是编程中日常使用,不可或缺的一个数据结构,本章节最终会代码实现一个简单哈希表,来解释哈希表相关的重要概念。对前端同学而言,哈希表是个每天用但说起来可能陌生的概念。说每天用,是因为在 JavaScript 中,对象(对若干个元素(key-value对),如果我们想通过 key 来找到对应的 value,通常情况下,我们需要遍历所有元素,一一比较 key,来找到对应的 value。这个时间复杂度是
一、HashTable (哈希函数,哈希表的简单实现)
这一章节内容主要是 HashTable,中文即哈希表,散列表等等。HashTable 是编程中日常使用,不可或缺的一个数据结构,本章节最终会代码实现一个简单哈希表,来解释哈希表相关的重要概念。
对前端同学而言,哈希表是个每天用但说起来可能陌生的概念。说每天用,是因为在 JavaScript 中,对象( {}
)的底层实现即哈希表,我们也经常用对象来做缓存等各种用法,利用其查找时间复杂度为 O(1) 的特性。
1. 为什么需要 hash table (元素查找的时间复杂度)
对若干个元素(key-value对),如果我们想通过 key 来找到对应的 value,通常情况下,我们需要遍历所有元素,一一比较 key,来找到对应的 value。这个时间复杂度是 O(n) 。
然后我们假设这些元素是有序的,那么通过二分查找,时间复杂度可以降到 O(log n) 。
那么有没有更好的方法呢?这就是 hash table 出现的原因,它可以达到 O(1) 的时间复杂度。
2. 什么是 hash table?
哈希表是一种用于存储键值对(key-value pairs)的数据结构,它可以实现key到value的映射,一般情况下查找的时间复杂度是 O(1) 。
- 哈希表的核心是哈希函数(hash function),它可以接收 key 作为参数(一般是字符串),然后返回一个数字(通常作为 index 去找到对应的 bucket,bucket 里存储了一个或多个 value)。
- 哈希函数应该尽可能均匀的把不同的 key 映射到不同的 bucket(即产出不同的 index)。最差情况下,如果所有的 key 都得到相同的 index,那么哈希表就退化成一个链表了(取决于 bucket 的实现)。
- bucket 指什么?理想情况下,如果每个 key 都得到一个唯一的 index,那么这时候一个bucket对应一个元素,我们通过哈希函数可以一步取到 value;但通常这是不可能的,即 key -- > index 的映射肯定会有冲突的,所以一个 bucket 可能会有多个元素。
3. 哈希表的简单实现
/** * 哈希函数,接收字符串返回数字 * https: //github.com/darkskyapp/string-hash * * @param str 字符串 * @returns number,32位整数,0~4294967295 */ function hash(str) { var hash = 5381, i = str.length; while (i) { hash = (hash * 33) ^ str.charCodeAt(--i); } /* JavaScript does bitwise operations (like XOR, above) on 32-bit signed * integers. Since we want the results to be always positive, convert the * signed int to an unsigned by doing an unsigned bitshift. */ return hash >>> 0; } class HashTable { static hash(key) { return hash(key) } constructor() { this.buckets = []; } set(key, value) { const index = HashTable.hash(key); let bucket = this.buckets[index]; // 直接使用数组来处理哈希函数冲突的问题 if (!bucket) { this.buckets[index] = bucket = []; } if (!bucket.some(el => el.key === key)) { bucket.push({ key, value }); } } get(key) { const index = HashTable.hash(key); const bucket = this.buckets[index]; if (!bucket) return; let result; bucket.some(el => { if (el.key === key) { result = el.value; return true; } return false; }); return result; } }
以上是一个简单的哈希表实现,还有很多细节没有考虑,比如:
-
填装因子
(填装因子 = 哈希表的元素数量 / 哈希表的位置总数)
。根据经验,一旦填装因子大于 0.7,我们就需要调整哈希表的长度。 -
buckets 数组这里没有规定长度,如果考虑 buckets 的长度,那么我们就要对哈希函数返回的值进行取余操作。
参考:
以上所述就是小编给大家介绍的《算法学习(JavaScript实现)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 图算法|Dijkstra算法python实现
- 算法:经典排序算法的 Go 实现
- js实现数据结构及算法之排序算法
- 算法 - 06 | 链表(上):如何实现LRU缓存淘汰算法?
- Twitter雪花算法SnowFlake算法的java实现
- js实现多种排序算法(算法导论第二章)
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Java常用算法手册
2012-5 / 59.00元
《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏、密码学等领域中的应用;最后,列举了算法的一些常见面试题。书中知识点覆盖全面,结构安排紧凑,讲解详细,实例丰富。全书对每一个知识点都给出了相应的算法及应用实例,虽然这些例子都是以Java语言来编......一起来看看 《Java常用算法手册》 这本书的介绍吧!