文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

TypeScript基础数据结构哈希表HashTable教程

2023-02-05 15:01

关注

前言

哈希表是一种 非常重要的数据结构,几乎所有的编程语言都有 直接或者间接 的应用这种数据结构。

很多学习编程的人一直搞不懂哈希表到底是如何实现的,在这一章中,我们就一点点来实现一个自己的哈希表。通过实现来理解哈希表背后的原理和它的优势。

1. 哈希表介绍和特性

哈希表通常是基于数组进行实现的,相对于数组,他有很多优势:

PS: 树也是一种基础的数据结构,js 中没有树,我们下一章就会讲树

哈希表相对于数组的一些不足:

那么哈希表到底是什么?

我们上面说了哈希表的优势和不足,似乎还是没说它到底长什么样子?

这也是哈希表不好理解的地方,它不像数组、链表和树等可通过图形的形式表示其结构和原理。

哈希表结构就是数组,但它神奇之处在于对下标值的一种变换,这种变换我们可以称之为哈希函数,通过哈希函数可以获取HashCode。

2. 哈希表的一些概念

仍然需要解决的问题:

3. 地址冲突解决方案

解决冲突常见的两种方案:

3.1 方案一:链地址法

如下图所示:

数组还是链表?

3.2 方案二:开放地址法

开放地址法的主要工作方式是寻找空白的单元格来放置冲突的数据项。(了解即可,现在很少用到了)

据探测空白单元格位置方式的不同,可分为三种方法:

4. 哈希函数代码实现

好的哈希函数应该尽可能的让计算的过程变得简单,提高计算的效率。

设计好的哈希函数应该具有的优点:

下面我们就来实现一个哈希函数:


function hashFunc(key: string, max: number): number {
  // 1. 计算 hashCode cats => 60337 (27为底的时候)
  let hashCode = 0;
  const length = key.length;
  for (let i = 0; i < length; i++) {
    // 霍纳法则计算 hashCode
    hashCode = 31 * hashCode + key.charCodeAt(i);
  }
  // 2. 求出索引值
  const index = hashCode % max;
  return index;
}

5. 哈希表封装

经过前面这么多内容的铺垫,我们现在终于可以真正实现自己的哈希表了

5.1 整体框架 v1 版

class HashTable<T = any> {
  // 创建一个数组,用来存放链地址法中的链
  storage: [string, T][][] = [];
  // 定义数组的长度
  private length: number = 7;
  // 记录已经存放元素的个数
  private count: number = 0;
}

在上面代码中,我们定义了三个属性

5.2 添加 put 方法 v2 版

put 方法的作用是插入&修改数据

在哈希表中,插入和修改操作是同一个函数。

put(key: string, value: T) {
  // 1.根据key 获取数组中对应的索引值
  const index = this.hashFunc(key, this.length);
  // 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++) {
    const tuple = bucket[i];
    const tupleKey = tuple[0];
    if (tupleKey === key) {
      // 修改/更新的操作
      tuple[1] = value;
      isUpdate = true;
    }
  }
  // 5. 如果上面的代码没有进行覆盖,那么在该位置进行添加
  if (!isUpdate) {
    bucket.push([key, value]);
    this.count++
  }
}

测试:

const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);

上面 hashTable 的结构可以用下图来表示:(aaabbbccc 可能在一个 bucket 中,也可能不在,具体要看哈希函数得到的 index

5.3 添加 get 方法 v3 版

get 方法的作用是根据 key 获取对应的值

  get(key: string): T | undefined {
    // 1. 根据 key 获取索引值 index
    const index = this.hashFunc(key, this.length);
    // 2. 获取 bucket(桶)
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 对 bucket 进行遍历
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        return tupleValue;
      }
    }
    return undefined;
  }

测试:

  get(key: string): T | undefined {
    // 1. 根据 key 获取索引值 index
    const index = this.hashFunc(key, this.length);
    // 2. 获取 bucket(桶)
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 对 bucket 进行遍历
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        return tupleValue;
      }
    }
    return undefined;
  }

5.4 添加 delete 方法 v4 版

delete 方法的作用是根据 key 删除对应的值

  delete(key: string): T | undefined {
    // 1. 获取索引值的位置
    const index = this.hashFunc(key, this.length);
    // 2. 获取 bucket(桶)
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 对 bucket 进行遍历
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        bucket.splice(i, 1);
        this.count--;
        return tupleValue;
      }
    }
    return undefined;
  }

测试:

const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);
hashTable.delete('aaa')
console.log(hashTable.get("aaa")); // undefined
console.log(hashTable.get("bbb")); // 300
console.log(hashTable.get("ccc")); // 400

6. 哈希表的自动扩容

目前,我们是将所有的数据项放在长度为 7 的数组中,因为我们使用的是链地址法,loadFactor 可以大于 1,所以这个哈希表是可以无限制的插入新数据的。

但是,随着数据量的增多,每一个 index 对应的 bucket 会越来越长,也就造成效率的降低,所以在合适的情况对数组进行扩容是很有必要的。

loadFactor 译为装载因子。装载因子用来衡量 HashMap 满的程度

如何进行扩容?

扩容可以简单的将容量增大两倍,但是这种情况下,所有的数据项一定要同时进行修改(重新调用哈希函数)

1. 调整代码,添加 resize 方法

private resize(newLength) {
  // 设置新的长度
  this.length = newLength;
  // 获取原来所有的数据,并且重新放入到新的容量数组中
  // 1. 对数据进行的初始化操作
  const oldStorage = this.storage;
  this.storage = [];
  this.count = 0;
  // 2. 获取原来数据,放入新的数组中
  oldStorage.forEach((bucket) => {
    if (!bucket) return;
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      this.put(tuple[0], tuple[1]);
    }
  });
}

上面的 resize 方法的作用就对 哈希表进行扩容,但是我们应该如何使用 resize 方法呢?

答案就是,我们可以在 putdelete 方法的最后判断一下当前哈希表的 loadFactor,比如:

2. 修改 put 方法

  put(key: string, value: T) {
    // 1.根据key 获取数组中对应的索引值
    const index = this.hashFunc(key, this.length);
    console.log({ index });
    // 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++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      if (tupleKey === key) {
        // 修改/更新的操作
        tuple[1] = value;
        isUpdate = true;
      }
    }
    // 5. 如果上面的代码没有进行覆盖,那么在该位置进行添加
    if (!isUpdate) {
      bucket.push([key, value]);
      this.count++;
+     // 发现 loadFactor 比例已经大于 0.75,那么就直接扩容
+     const loadFactor = this.count / this.length;
+     if (loadFactor > 0.75) {
+       this.resize(this.length * 2);
+     }
    }
  }

3. 修改 delete 方法

  delete(key: string): T | undefined {
    // 1. 获取索引值的位置
    const index = this.hashFunc(key, this.length);
    // 2. 获取 bucket(桶)
    const bucket = this.storage[index];
    if (!bucket) return undefined;
    // 3. 对 bucket 进行遍历
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i];
      const tupleKey = tuple[0];
      const tupleValue = tuple[1];
      if (tupleKey === key) {
        bucket.splice(i, 1);
        this.count--;
+       // 发现 loadFactor 比例已经小于 0.75,那么就直接缩容
+       const loadFactor = this.count / this.length;
+       if (loadFactor < 0.25 && this.length > 7) {
+         this.resize(Math.floor(this.length / 2));
+       }
        return tupleValue;
      }
    }
    return undefined;
  }

测试:

const hashTable = new HashTable();
hashTable.put("aaa", 200);
hashTable.put("bbb", 300);
hashTable.put("ccc", 400);
hashTable.put("ddd", 500);
hashTable.put("eee", 600);
console.log(hashTable.storage.length); // 7
hashTable.put("fff", 600);
console.log(hashTable.storage.length); // 14
hashTable.delete("fff");
hashTable.delete("eee");
console.log(hashTable.storage.length); // 14
hashTable.delete("ddd");
console.log(hashTable.storage.length); // 7

以上就是TypeScript 基础数据结构哈希表 HashTable教程的详细内容,更多关于TypeScript 数据结构HashTable的资料请关注编程网其它相关文章!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯