亲宝软件园·资讯

展开

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

前端要努力QAQ 人气:0

前言

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

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

1. 哈希表介绍和特性

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

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

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

那么哈希表到底是什么?

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

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

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

2. 哈希表的一些概念

仍然需要解决的问题:

3. 地址冲突解决方案

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

3.1 方案一:链地址法

如下图所示:

数组还是链表?

3.2 方案二:开放地址法

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

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

4. 哈希函数代码实现

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

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

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

/**
 * 哈希函数,将 key 映射成 index
 * @param key 要转换的 key
 * @param max 数组的长度(最大的数值)
 * @returns
 */
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

加载全部内容

相关教程
猜你喜欢
用户评论