【JavaScript 算法】哈希表：快速查找与存储

空白诗

发布于 2024-07-20 12:38:49

710

发布于 2024-07-20 12:38:49

文章被收录于专栏：【全栈开发之路】

哈希表（Hash Table）是一种非常高效的数据结构，用于实现快速的查找和存储操作。通过使用哈希函数将数据映射到数组中的某个位置，哈希表能够在常数时间内完成插入、删除和查找操作。

一、哈希表的基本概念

哈希表是一种基于数组的数据结构，它通过哈希函数将键值对映射到数组的某个位置。当发生哈希冲突（即不同的键映射到同一个位置）时，可以使用链地址法或开放地址法来解决。

哈希函数

哈希函数是哈希表的核心组件，它负责将输入（键）转换为数组中的索引位置。一个好的哈希函数应该尽可能地将输入均匀地分布到哈希表中。

哈希冲突

哈希冲突是指不同的键通过哈希函数映射到相同的数组位置。解决哈希冲突的常用方法包括：

链地址法：在每个数组位置存储一个链表，所有映射到同一位置的键值对都存储在该链表中。
开放地址法：当发生冲突时，按照一定的规则寻找下一个空闲位置来存储键值对。

二、哈希表的实现

下面将通过 JavaScript 实现一个简单的哈希表。

哈希函数的实现

首先，我们需要实现一个简单的哈希函数，该函数接受一个字符串并返回一个数组索引。

/**
 * 简单哈希函数，将字符串转换为数组索引
 * @param {string} key - 需要哈希的键
 * @param {number} tableSize - 哈希表的大小
 * @returns {number} - 哈希值
 */
function hashFunction(key, tableSize) {
  let hash = 0;
  // 遍历键的每个字符
  for (let i = 0; i < key.length; i++) {
    // 计算哈希值
    hash = (hash + key.charCodeAt(i) * i) % tableSize;
  }
  return hash;
}

链地址法实现哈希表

接下来，我们使用链地址法来实现哈希表。每个数组位置存储一个链表，用于解决哈希冲突。

class HashTable {
  constructor(size = 50) {
    // 初始化哈希表数组
    this.table = new Array(size);
    this.size = size;
  }

  /**
   * 插入键值对到哈希表
   * @param {string} key - 键
   * @param {*} value - 值
   */
  set(key, value) {
    const index = hashFunction(key, this.size);
    // 如果当前位置没有链表，则创建一个空链表
    if (!this.table[index]) {
      this.table[index] = [];
    }
    // 插入键值对到链表中
    this.table[index].push([key, value]);
  }

  /**
   * 从哈希表获取值
   * @param {string} key - 键
   * @returns {*} - 值，如果键不存在则返回 undefined
   */
  get(key) {
    const index = hashFunction(key, this.size);
    // 如果当前位置没有链表，返回 undefined
    if (!this.table[index]) return undefined;
    // 遍历链表查找对应的键值对
    for (let pair of this.table[index]) {
      if (pair[0] === key) return pair[1];
    }
    return undefined;
  }

  /**
   * 从哈希表删除键值对
   * @param {string} key - 键
   * @returns {boolean} - 如果删除成功返回 true，否则返回 false
   */
  remove(key) {
    const index = hashFunction(key, this.size);
    // 如果当前位置没有链表，返回 false
    if (!this.table[index]) return false;
    // 遍历链表查找并删除对应的键值对
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i][0] === key) {
        this.table[index].splice(i, 1);
        return true;
      }
    }
    return false;
  }
}

// 示例：使用哈希表
const ht = new HashTable();
ht.set('name', 'Alice');
ht.set('age', 25);
console.log(ht.get('name')); // 输出 'Alice'
console.log(ht.get('age')); // 输出 25
ht.remove('name');
console.log(ht.get('name')); // 输出 undefined

在上述代码中，我们实现了一个简单的哈希表，并使用链地址法解决哈希冲突。通过 set 方法插入键值对，通过 get 方法查找值，通过 remove 方法删除键值对。