详解JavaScript实现哈希表

什么是哈希表

哈希表是一种常见的数据结构，它可以提供快速的插入、查找和删除操作，其时间复杂度为 O(1) 。

哈希表的主要思想是将数据元素经过哈希（hash）函数的映射后，存储到一个数组中。哈希函数 将插入的元素映射到一个数组下标上，这个下标对应的元素就是这个元素所对应的值。在查找时，再使用同样的哈希函数，得到元素所对应的下标，即可查找到这个元素。

哈希函数的实现

哈希函数的实现是哈希表的核心。常用的哈希函数有很多种，这里介绍一种简单的哈希函数：取余法。

取余法的思路是将元素的值除以哈希表的大小，得到的余数就是元素的哈希值。例如，如果哈希表的大小为 10，插入元素 20，则 20 % 10 = 0，即元素的哈希值为 0。

以下是一个用取余法实现的哈希函数的示例：

function hash(key, length) {
  return key % length;
}

哈希冲突的处理

在哈希表中，不同的元素可能会映射到同一个下标上，这种现象称为哈希冲突。哈希冲突通常有两种处理方法：

• 拉链法（链地址法）：将哈希值相同的元素保存在同一个链表中。当查找一个元素时，首先找到对应的链表，然后在链表中进行线性查找。插入和删除操作也是同样的方式，在链表中进行插入和删除。
• 开放地址法：当发生哈希冲突时，通过某种方法寻找下一个可用的位置，然后将元素插入到该位置。查找元素时，也需要按照一定的规则寻找后续位置。

以下是一个使用拉链法处理哈希冲突的示例：

class HashTable {
  constructor() {
    this.table = new Array(137);
    for (let i = 0; i < this.table.length; ++i) {
      this.table[i] = new LinkedList();
    }
  }

  put(data) {
    const pos = this.hash(data);
    this.table[pos].append(data);
  }

  get(key) {
    const pos = this.hash(key);
    return this.table[pos].find(key);
  }

  hash(data) {
    let total = 0;
    for (let i = 0; i < data.length; ++i) {
      total += data.charCodeAt(i);
    }
    return total % this.table.length;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  append(data) {
    const node = new Node(data);
    let current = this.head;
    if (current === null) {
      this.head = node;
    } else {
      while (current.next !== null) {
        current = current.next;
      }
      current.next = node;
    }
  }

  find(key) {
    let current = this.head;
    while (current !== null) {
      if (current.data.key === key) {
        return current.data.value;
      }
      current = current.next;
    }
    return null;
  }
}

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

使用哈希表的示例

以下是一个使用哈希表统计单词数量的示例：

const words = 'the quick brown fox jumped over the lazy dog'.split(' ');
const counter = new Map();
for (const word of words) {
  if (counter.has(word)) {
    counter.set(word, counter.get(word) + 1);
  } else {
    counter.set(word, 1);
  }
}
console.log(counter);

另一个使用哈希表实现 LRU 缓存淘汰算法的示例：

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (this.cache.has(key)) {
      const value = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key, value);
      return value;
    }
    return -1;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      const keyToDelete = this.cache.keys().next().value;
      this.cache.delete(keyToDelete);
    }
    this.cache.set(key, value);
  }
}

以上就是详解 JavaScript 实现哈希表的完整攻略，希望对你有所帮助。