算法学习(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)

算法学习(JavaScript实现)

  • 哈希表的核心是哈希函数(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实现)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java常用算法手册

Java常用算法手册

2012-5 / 59.00元

《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏、密码学等领域中的应用;最后,列举了算法的一些常见面试题。书中知识点覆盖全面,结构安排紧凑,讲解详细,实例丰富。全书对每一个知识点都给出了相应的算法及应用实例,虽然这些例子都是以Java语言来编......一起来看看 《Java常用算法手册》 这本书的介绍吧!

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具