哈希表算法实现

Question

class HashTable {
  private data: Array<LinkedList>;
  private size: number;
  private count: number = 0;
  private loadFactor: number = 0.75;

  constructor(size: number) {
    this.data = new Array(size);
    this.size = size;
  }

  private _hash(key: string): number {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * i) % this.size;
    }
    return hash;
  }
  private _resize(): void {
    const newSize = this.size * 2;
    const newData = new Array(newSize);

    for (let i = 0; i < this.size; i++) {
      if (this.data[i]) {
        const linkedList = this.data[i]
        let node = linkedList.head
        while(node) {
          const [key, value] = node.value;
          const index = this._hash(key);
          if (!newData[index]) {
            newData[index] = new LinkedList();
          }
          newData[index].append([key, value]);
          node = node.next;
        }
      }
    }

    this.data = newData;
    this.size = newSize;
  }

  public set(key: string, value: any): void {
    const index = this._hash(key);
    if (!this.data[index]) {
      this.data[index] = new LinkedList();
    }
    this.count++;
    this.data[index].append([key,value])
    if (this.count / this.size >= this.loadFactor) {
      this._resize();
    }
  }

  public get(key: string): any | undefined {
    const index = this._hash(key);
    if (!this.data[index]) {
      return undefined;
    }
   
    return this.data[index].find((item) => item[0] === key)?.[1];
  }

  public remove(key: string): void {
    const index = this._hash(key);
    if (!this.data[index]) {
      return;
    }
    return this.data[index].remove((node) => node.value[0] === key);
  }
}

class LinkedListNode {
  public value: any;
  public next: LinkedListNode | null;

  constructor(value: any) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
   head: LinkedListNode | null;
   tail: LinkedListNode | null;

  constructor() {
    this.head = null;
    this.tail = null;
  }

  public append(value: any): void {
    const node = new LinkedListNode(value);
    if (!this.head) {
      this.head = node;
    } else {
      this.tail!.next = node;
    }
    this.tail = node;
  }

  public find(
    predicate: (node: LinkedListNode) => boolean
  ): LinkedListNode | null {
    let node = this.head;
    while (node) {
      if (predicate(node)) {
        return node;
      }
      node = node.next;
    }
    return null;
  }

  public remove(predicate: (node: LinkedListNode) => boolean): void {
    let node = this.head;
    let prev: LinkedListNode | null = null;
    while (node) {
      if (predicate(node)) {
        if (!prev) {
          this.head = node.next;
        } else {
          prev.next = node.next;
        }
        if (node === this.tail) {
          this.tail = prev;
        }
      }
      prev = node;
      node = node.next;
    }
  }
}

_hash 方法来计算哈希值，然后使用链表 data 来存储键值对实现了动态扩容。