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

查看所有标签

猜你喜欢:

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

数据库系统概念

数据库系统概念

Abraham Silberschatz、Henry F. Korth、S. Sudarshan / 杨冬青、马秀莉、唐世渭 / 机械工业 / 2006-10-01 / 69.50元

本书是数据库系统方面的经典教材之一。国际上许多著名大学包括斯坦福大学、耶鲁大学、得克萨斯大学、康奈尔大学、伊利诺伊大学、印度理工学院等都采用本书作为教科书。我国也有许多所大学采用本书以前版本的中文版作为本科生和研究生的数据库课程的教材和主要教学参考书,收到了良好的效果。 本书调整和新增内容:调整了第4版的讲授顺序。首先介绍SQL及其高级特性,使学生容易接受数据库设计的概念。新增数据库设计的专......一起来看看 《数据库系统概念》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

随机密码生成器
随机密码生成器

多种字符组合密码

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具