706. 设计哈希映射

题目描述

不借助任何语言自带的哈希表库，自己实现一个整数到整数的映射类 MyHashMap。

MyHashMap()：创建空映射。put(key, value)：写入键值对；若 key 已存在，就把它的值改为 value。get(key)：返回 key 对应的值，key 不存在时返回 -1。remove(key)：若 key 存在就删除这个键值对，否则什么也不做。

测试数据以方法名序列和参数序列给出，输出数组是每次调用的返回值，无返回值的调用对应 null。

示例 1

输入：操作 = ["MyHashMap","put","put","get","get","put","get","remove","get"]
参数 = [[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]
输出：[null,null,null,1,-1,null,1,null,-1]

解释：get(3) 找不到返回 -1；put(2,1) 把键 2 的值改为 1；删除键 2 后再查返回 -1。

数据范围

0 <= key, value <= 10^6
put、get、remove 合计最多调用 10^4 次。

解题思路：链地址法

链地址法：开 base 个桶（取质数 769），键 key 放进第 key % base 个桶，桶里存 [key, value] 对。put 先在桶里找同名键，找到就改值，找不到才追加；get 在桶里找到就返回值，否则 -1；remove 找到就删掉。

为什么正确

每个键在整个映射中至多出现一次，且只出现在第 key % base 个桶中，存着它最近一次 put 的值。

复杂度分析

设 n 为键的个数，每次操作平均 O(1 + n / base)；空间 O(base + n)。

易错点

put 已存在的键必须覆盖旧值，而不是再追加一对，否则 remove 后旧值还会被查到。值可以为 0，不能用 0 表示“不存在”。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class MyHashMap:
    def __init__(self, base: int = 769):
        self.base = base
        self.buckets = [[] for _ in range(base)]

    def put(self, key: int, value: int) -> None:
        b = self.buckets[key % self.base]
        for pair in b:
            if pair[0] == key:
                pair[1] = value
                return
        b.append([key, value])

    def get(self, key: int) -> int:
        b = self.buckets[key % self.base]
        for pair in b:
            if pair[0] == key:
                return pair[1]
        return -1

    def remove(self, key: int) -> None:
        b = self.buckets[key % self.base]
        for i, pair in enumerate(b):
            if pair[0] == key:
                b.pop(i)
                return

class MyHashMap {
    private int base;
    private List<List<int[]>> buckets;

    public MyHashMap() {
        base = 769;
        buckets = new ArrayList<>();
        for (int i = 0; i < base; i++) buckets.add(new ArrayList<>());
    }

    public void put(int key, int value) {
        List<int[]> b = buckets.get(key % base);
        for (int[] p : b) {
            if (p[0] == key) {
                p[1] = value;
                return;
            }
        }
        b.add(new int[]{key, value});
    }

    public int get(int key) {
        List<int[]> b = buckets.get(key % base);
        for (int[] p : b) {
            if (p[0] == key) {
                return p[1];
            }
        }
        return -1;
    }

    public void remove(int key) {
        List<int[]> b = buckets.get(key % base);
        for (int i = 0; i < b.size(); i++) {
            if (b.get(i)[0] == key) {
                b.remove(i);
                return;
            }
        }
    }
}

class MyHashMap {
public:
    int base;
    vector<vector<pair<int, int>>> buckets;

    MyHashMap() {
        base = 769;
        buckets.assign(base, {});
    }

    void put(int key, int value) {
        auto& b = buckets[key % base];
        for (auto& p : b) {
            if (p.first == key) {
                p.second = value;
                return;
            }
        }
        b.push_back({key, value});
    }

    int get(int key) {
        auto& b = buckets[key % base];
        for (auto& p : b) {
            if (p.first == key) {
                return p.second;
            }
        }
        return -1;
    }

    void remove(int key) {
        auto& b = buckets[key % base];
        for (int i = 0; i < (int)b.size(); i++) {
            if (b[i].first == key) {
                b.erase(b.begin() + i);
                return;
            }
        }
    }
};

type MyHashMap struct {
	base    int
	buckets [][][2]int
}

func Constructor() MyHashMap {
	base := 769
	return MyHashMap{base: base, buckets: make([][][2]int, base)}
}

func (this *MyHashMap) Put(key int, value int) {
	h := key % this.base
	for i := range this.buckets[h] {
		if this.buckets[h][i][0] == key {
			this.buckets[h][i][1] = value
			return
		}
	}
	this.buckets[h] = append(this.buckets[h], [2]int{key, value})
}

func (this *MyHashMap) Get(key int) int {
	b := this.buckets[key%this.base]
	for _, p := range b {
		if p[0] == key {
			return p[1]
		}
	}
	return -1
}

func (this *MyHashMap) Remove(key int) {
	h := key % this.base
	for i, p := range this.buckets[h] {
		if p[0] == key {
			this.buckets[h] = append(this.buckets[h][:i], this.buckets[h][i+1:]...)
			return
		}
	}
}

var MyHashMap = function() {
    this.base = 769;
    this.buckets = Array.from({ length: this.base }, () => []);
};

MyHashMap.prototype.put = function(key, value) {
    const b = this.buckets[key % this.base];
    for (const p of b) {
        if (p[0] === key) {
            p[1] = value;
            return;
        }
    }
    b.push([key, value]);
};

MyHashMap.prototype.get = function(key) {
    const b = this.buckets[key % this.base];
    for (const p of b) {
        if (p[0] === key) {
            return p[1];
        }
    }
    return -1;
};

MyHashMap.prototype.remove = function(key) {
    const b = this.buckets[key % this.base];
    for (let i = 0; i < b.length; i++) {
        if (b[i][0] === key) {
            b.splice(i, 1);
            return;
        }
    }
};

class MyHashMap {
    base: number;
    buckets: number[][][];

    constructor() {
        this.base = 769;
        this.buckets = Array.from({ length: this.base }, () => []);
    }

    put(key: number, value: number): void {
        const b = this.buckets[key % this.base];
        for (const p of b) {
            if (p[0] === key) {
                p[1] = value;
                return;
            }
        }
        b.push([key, value]);
    }

    get(key: number): number {
        const b = this.buckets[key % this.base];
        for (const p of b) {
            if (p[0] === key) {
                return p[1];
            }
        }
        return -1;
    }

    remove(key: number): void {
        const b = this.buckets[key % this.base];
        for (let i = 0; i < b.length; i++) {
            if (b[i][0] === key) {
                b.splice(i, 1);
                return;
            }
        }
    }
}

载入编辑器，自己跑一遍 →

其他解法

链地址法通过哈希函数把大值域压到少量桶中，需要处理冲突；直接寻址可以看作桶数等于值域的哈希表，没有冲突但占内存。

解法 2：直接寻址数组时间 O(1)，空间 O(U)

key 的范围是 0 到 10⁶，直接开一个长为 10⁶ + 1 的数组，用 key 作下标。初始全部填 −1 表示不存在。put 写入 value，get 直接读取，remove 写回 −1。

实现最简单，每次操作 O(1)。代价是内存取决于 key 的值域 U，且只适用于小范围的整数 key。

class MyHashMap:
    def __init__(self):
        self.data = [-1] * 1000001

    def put(self, key: int, value: int) -> None:
        self.data[key] = value

    def get(self, key: int) -> int:
        return self.data[key]

    def remove(self, key: int) -> None:
        self.data[key] = -1

class MyHashMap {
    private final int[] data = new int[1000001];

    public MyHashMap() {
        Arrays.fill(data, -1);
    }

    public void put(int key, int value) {
        data[key] = value;
    }

    public int get(int key) {
        return data[key];
    }

    public void remove(int key) {
        data[key] = -1;
    }
}

class MyHashMap {
    vector<int> data;

public:
    MyHashMap() : data(1000001, -1) {}

    void put(int key, int value) {
        data[key] = value;
    }

    int get(int key) {
        return data[key];
    }

    void remove(int key) {
        data[key] = -1;
    }
};

type MyHashMap struct {
	data []int
}

func Constructor() MyHashMap {
	data := make([]int, 1000001)
	for i := range data {
		data[i] = -1
	}
	return MyHashMap{data: data}
}

func (this *MyHashMap) Put(key int, value int) {
	this.data[key] = value
}

func (this *MyHashMap) Get(key int) int {
	return this.data[key]
}

func (this *MyHashMap) Remove(key int) {
	this.data[key] = -1
}

class MyHashMap {
    constructor() {
        this.data = new Int32Array(1000001).fill(-1);
    }

    put(key, value) {
        this.data[key] = value;
    }

    get(key) {
        return this.data[key];
    }

    remove(key) {
        this.data[key] = -1;
    }
}

class MyHashMap {
    data: Int32Array;

    constructor() {
        this.data = new Int32Array(1000001).fill(-1);
    }

    put(key: number, value: number): void {
        this.data[key] = value;
    }

    get(key: number): number {
        return this.data[key];
    }

    remove(key: number): void {
        this.data[key] = -1;
    }
}

设计专题的其他题目

查看设计全部题目 →