705.设计哈希集合

链接：705.设计哈希集合
难度：Easy
标签：设计、数组、哈希表、链表、哈希函数
简介：设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

题解 1 - typescript

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

class LNode {
  constructor(
    public key: number,
    public value: number,
    public prev: LNode | null = null,
    public next: LNode | null = null
  ) {}
  remove() {
    if (this.prev) this.prev.next = this.next;
    if (this.next) this.next.prev = this.prev;
  }
}
class HashLinkedList {
  private head = new LNode(0, 0);
  private last: LNode = this.head;
  private map = new Map<number, LNode>();
  private count = 0;
  constructor(private capacity: number) {}
  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.moveLast(node);
    return node.value;
  }
  put(key: number, value: number): void {
    let node = this.map.get(key);
    if (!node) {
      this.map.set(key, (node = new LNode(key, value, this.last)));
      this.last.next = node;
      this.last = node;
      if (++this.count > this.capacity) {
        const first = this.head.next!;
        this.map.delete(first.key);
        this.head.next = first.next!;
        first.next!.prev = this.head;
      }
    } else {
      node.value = value;
      this.moveLast(node);
    }
  }
  private moveLast(node: LNode) {
    if (this.last === node) return;
    node.remove();
    node.prev = this.last;
    this.last.next = node;
    node.next = null;
    this.last = node;
  }
}
class LRUCache {
  private list: HashLinkedList;
  constructor(capacity: number) {
    this.list = new HashLinkedList(capacity);
  }
  get(key: number): number {
    return this.list.get(key);
  }
  put(key: number, value: number): void {
    this.list.put(key, value);
  }
}

题解 2 - python

• 编辑时间：2024-04-14
• 执行用时：94ms
• 内存消耗：22.09MB
• 编程语言：python
• 解法介绍：哈希存储。

class MyHashSet:
    def __init__(self):
        self.set = set()
    def add(self, key: int) -> None:
        self.set.add(key)
    def remove(self, key: int) -> None:
        if self.contains(key):
            self.set.remove(key)
    def contains(self, key: int) -> bool:
        return key in self.set

题解 3 - python

• 编辑时间：2024-04-14
• 执行用时：217ms
• 内存消耗：43.05MB
• 编程语言：python
• 解法介绍：利用bitmap存储。

class BitMap:
    def __init__(self, n: int):
        self.size = 64
        self.buckets = [0] * n
    def add(self, key: int):
        self.set(key // self.size, key % self.size, True)
    def remove(self, key: int):
        self.set(key // self.size, key % self.size, False)
    def contains(self, key: int):
        return self.get(key // self.size, key % self.size)
    def set(self, bucket: int, loc: int, val: bool):
        if val:
            self.buckets[bucket] |= 1 << loc
        else:
            self.buckets[bucket] = self.buckets[bucket] & ~(1 << loc)
    def get(self, bucket: int, loc: int):
        return bool((self.buckets[bucket] >> loc) & 1)
    
class MyHashSet:
    def __init__(self):
        self.bm = BitMap(10 ** 6 + 1)
    def add(self, key: int) -> None:
        self.bm.add(key)
    def remove(self, key: int) -> None:
        self.bm.remove(key)
    def contains(self, key: int) -> bool:
        return self.bm.contains(key)