706. 设计哈希映射

设计哈希映射

为了设计一个简单的哈希映射，可以使用哈希表数据结构。我们可以使用数组加链表解决哈希碰撞问题。以下是一个基于链表的哈希映射的实现。

设计思路

1. 哈希函数：使用取模运算 (key % bucket_size) 来确定键值对在哈希表中的位置。
2. 链表：在每个桶中使用链表来处理冲突。链表节点存储键值对。
3. 基本操作：
   • put(key, value): 插入或更新键值对。
   • get(key): 获取键对应的值，如果键不存在返回 -1。
   • remove(key): 删除键对应的键值对。

代码实现

class MyHashMap {
    constructor() {
        this.bucketSize = 1000;
        this.buckets = new Array(this.bucketSize).fill(null).map(() => new LinkedList());
    }

    _hash(key) {
        return key % this.bucketSize;
    }

    put(key, value) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        let node = bucket.head;
        while (node) {
            if (node.key === key) {
                node.value = value;
                return;
            }
            node = node.next;
        }
        bucket.append(new ListNode(key, value));
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        let node = bucket.head;
        while (node) {
            if (node.key === key) {
                return node.value;
            }
            node = node.next;
        }
        return -1;
    }

    remove(key) {
        const index = this._hash(key);
        const bucket = this.buckets[index];
        let node = bucket.head;
        let prev = null;
        while (node) {
            if (node.key === key) {
                if (prev) {
                    prev.next = node.next;
                } else {
                    bucket.head = node.next;
                }
                return;
            }
            prev = node;
            node = node.next;
        }
    }
}

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

class LinkedList {
    constructor() {
        this.head = null;
    }

    append(node) {
        if (!this.head) {
            this.head = node;
            return;
        }
        let curr = this.head;
        while (curr.next) {
            curr = curr.next;
        }
        curr.next = node;
    }
}

代码说明

1. 构造函数：

   • MyHashMap 初始化哈希映射，设置桶的大小 bucketSize，并创建 bucketSize 个链表来存储键值对。

2. 哈希函数：

   • _hash(key): 返回键 key 的哈希值，即 key % bucketSize。

3. 基本操作：

   • put(key, value): 计算键的哈希值，找到对应的桶，遍历桶中的链表。如果找到相同的键则更新值，否则在链表末尾添加新节点。
   • get(key): 计算键的哈希值，找到对应的桶，遍历链表查找键。如果找到返回对应的值，否则返回 -1。
   • remove(key): 计算键的哈希值，找到对应的桶，遍历链表查找键。如果找到则删除对应节点。

4. 链表实现：

   • ListNode: 链表节点类，包含 key，value 和 next 指针。
   • LinkedList: 简单链表类，包含 head 指针和 append(node) 方法。

使用示例

let hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
console.log(hashMap.get(1)); // 返回 1
console.log(hashMap.get(3)); // 返回 -1 (未找到)
hashMap.put(2, 1); // 更新已有的键 2
console.log(hashMap.get(2)); // 返回 1
hashMap.remove(2); // 删除键 2
console.log(hashMap.get(2)); // 返回 -1 (未找到)