706.设计哈希映射

链接：706.设计哈希映射
难度：Easy
标签：设计、数组、哈希表、链表、哈希函数
简介：不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

题解 1 - typescript

• 编辑时间：2021-07-24
• 执行用时：204ms
• 内存消耗：48.8MB
• 编程语言：typescript
• 解法介绍：利用链表解决哈希冲突。

class LinkedListNode {
  constructor(
    public val: [number, number],
    public prev: LinkedListNode | null = null,
    public next: LinkedListNode | null = null
  ) {}
}
class LinkedList {
  private head = new LinkedListNode([0, 0]);
  private last: LinkedListNode | null = null;
  private getNode(key: number): LinkedListNode | null {
    let p: LinkedListNode = this.head;
    while (p.next) {
      if (p.next.val[0] === key) return p;
      p = p.next;
    }
    return null;
  }
  contains(key: number): boolean {
    return this.getNode(key) !== null;
  }
  put(key: number, value: number): void {
    let node = this.getNode(key);
    if (node !== null) {
      node.next!.val[1] = value;
      return;
    }
    node = new LinkedListNode([key, value]);
    if (this.last === null) this.head.next = node;
    else this.last.next = node;
    this.last = node;
  }
  get(key: number): number {
    const node = this.getNode(key);
    if (node === null) return -1;
    return node.next!.val[1];
  }
  remove(key: number): void {
    const node = this.getNode(key);
    if (node === null) return;
    if (this.last === node.next) this.last = node;
    node.next = node.next!.next;
  }
}
const SIZE = 1000;
class MyHashMap {
  private list = new Array(SIZE).fill(0).map(_ => new LinkedList());
  private hash(key: number) {
    return key % SIZE;
  }
  put(key: number, value: number): void {
    this.list[this.hash(key)].put(key, value);
  }
  get(key: number): number {
    return this.list[this.hash(key)].get(key);
  }
  remove(key: number): void {
    return this.list[this.hash(key)].remove(key);
  }
}

题解 2 - python

• 编辑时间：2024-04-15
• 执行用时：422ms
• 内存消耗：64.12MB
• 编程语言：python
• 解法介绍：利用双数组存键值对。

class MyHashMap:
    def __init__(self):
        self.iarr = [False] * (10 ** 6 + 1)
        self.varr = [-1] * (10 ** 6 + 1)
    def put(self, key: int, value: int) -> None:
        self.iarr[key] = True
        self.varr[key] = value
    def get(self, key: int) -> int:
        return self.varr[key] if self.iarr[key] else -1
    def remove(self, key: int) -> None:
        self.iarr[key] = False

题解 3 - python

• 编辑时间：2024-04-15
• 执行用时：112ms
• 内存消耗：19.11MB
• 编程语言：python
• 解法介绍：map。

class MyHashMap:
    def __init__(self):
        self.map = {}
    def put(self, key: int, value: int) -> None:
        self.map[key] = value
    def get(self, key: int) -> int:
        return self.map[key] if key in self.map else -1
    def remove(self, key: int) -> None:
        if key in self.map:
            del self.map[key]