js实现hashtable

实现哈希表的基本结构

哈希表（Hash Table）通过键值对存储数据，利用哈希函数将键映射到特定索引。JavaScript 中可通过对象或 Map 实现，但手动实现能更深入理解原理。

class HashTable {
  constructor(size = 32) {
    this.buckets = new Array(size);
    this.size = size;
  }
}

定义哈希函数

哈希函数将键转换为索引。简单实现可采用字符编码求和后取模。

_hash(key) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % this.size;
}

处理冲突的方法

冲突发生时（不同键映射到同一索引），常用链地址法（数组+链表）或开放寻址法。以下采用链地址法：

class HashNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

插入键值对

检查索引位置是否存在节点，若无则直接插入，否则遍历链表更新或追加节点。

set(key, value) {
  const index = this._hash(key);
  if (!this.buckets[index]) {
    this.buckets[index] = new HashNode(key, value);
  } else {
    let currentNode = this.buckets[index];
    while (currentNode) {
      if (currentNode.key === key) {
        currentNode.value = value; // 更新现有键
        return;
      }
      if (!currentNode.next) break;
      currentNode = currentNode.next;
    }
    currentNode.next = new HashNode(key, value); // 追加新节点
  }
}

获取键对应的值

根据哈希找到索引，遍历链表查找匹配的键。

get(key) {
  const index = this._hash(key);
  let currentNode = this.buckets[index];
  while (currentNode) {
    if (currentNode.key === key) {
      return currentNode.value;
    }
    currentNode = currentNode.next;
  }
  return undefined;
}

删除键值对

找到节点后，如果是链表头则直接替换，否则调整前驱节点的指针。

delete(key) {
  const index = this._hash(key);
  let currentNode = this.buckets[index];
  let prevNode = null;
  while (currentNode) {
    if (currentNode.key === key) {
      if (!prevNode) {
        this.buckets[index] = currentNode.next; // 删除头节点
      } else {
        prevNode.next = currentNode.next; // 删除中间节点
      }
      return true;
    }
    prevNode = currentNode;
    currentNode = currentNode.next;
  }
  return false;
}

完整示例代码

class HashNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.next = null;
  }
}

class HashTable {
  constructor(size = 32) {
    this.buckets = new Array(size);
    this.size = size;
  }

  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.size;
  }

  set(key, value) {
    const index = this._hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = new HashNode(key, value);
    } else {
      let currentNode = this.buckets[index];
      while (currentNode) {
        if (currentNode.key === key) {
          currentNode.value = value;
          return;
        }
        if (!currentNode.next) break;
        currentNode = currentNode.next;
      }
      currentNode.next = new HashNode(key, value);
    }
  }

  get(key) {
    const index = this._hash(key);
    let currentNode = this.buckets[index];
    while (currentNode) {
      if (currentNode.key === key) {
        return currentNode.value;
      }
      currentNode = currentNode.next;
    }
    return undefined;
  }

  delete(key) {
    const index = this._hash(key);
    let currentNode = this.buckets[index];
    let prevNode = null;
    while (currentNode) {
      if (currentNode.key === key) {
        if (!prevNode) {
          this.buckets[index] = currentNode.next;
        } else {
          prevNode.next = currentNode.next;
        }
        return true;
      }
      prevNode = currentNode;
      currentNode = currentNode.next;
    }
    return false;
  }
}

使用示例

const table = new HashTable();
table.set('name', 'Alice');
table.set('age', 25);
console.log(table.get('name')); // 输出: Alice
table.delete('age');
console.log(table.get('age')); // 输出: undefined