数据结构之HashMap

HashMap的结构，是数组+链表+红黑树的结构。当链表长度大于8时，转为红黑树结构。HashMap是线程不安全的。

模拟实现一个HashMap

在我面试微软时，有一道题目是用JavaScript模拟实现一个HashMap。当时不了解HashMap是什么。所以现在重新模拟实现HashMap，没有红黑树的结构，也没有线程安全的保证。存粹是为了学习。

// 链表的节点
class Node {
  constructor(key, value, next = null) {
    this.key = key;
    this.value = value;
    this.next = next;
  }
}

// HashMap
class HashMap {
  constructor(size = 16) {
    this.size = 0;
    this.table = [];

    for (let i = 0; i < size; i++) {
      this.table[i] = [null, 0];
    }
  }

  hashConversion(key) {
    let keyCode = 0;

    for(const item of key) {
      keyCode += item.charCodeAt(0)
    }

    return keyCode % this.table.length;
  }

  set(key, value) {
    const index = this.hashConversion(key);
    const indexValue = this.table[index][0];

    if (indexValue === null) {
      this.table[index][0] = new Node(key, value);
      this.table[index][1] += 1;
      this.size += 1;

      return;
    }

    let currentBefore = null;
    let current = indexValue;

    while (current) {
      if (current.key === key) {
        current.value = value;
        break;
      } else {
        currentBefore = current;
        current = current.next;
      }
    }

    if (current === null) {
      currentBefore.next = new Node(key, value);
      this.table[index][1] += 1;
      this.size += 1;
    }
  }

  get(key) {
    let result = null;
    const index = this.hashConversion(key);
    const indexValue = this.table[index][0];

    if (indexValue === null) {
      return result;
    }

    let current = indexValue;

    while (current) {
      if (current.key === key) {
        result = current.value;
        break;
      }
    }

    return result;
  }

  remove(key) {
    const index = this.hashConversion(key);
    const indexValue = this.table[index][0];

    if (indexValue === null) {
      return;
    }

    let currentBefore = null;
    let current = indexValue;

    while (current) {
      if (current.key === key) {
        if (currentBefore === null) {
          this.table[index][0] = current.next;
        } else {
          currentBefore.next = current.next;
        }

        this.table[index][1] -= 1;
        this.size -= 1;
        break;
      } else {
        currentBefore = current;
        current = current.next;
      }
    }
  }
}