超大数组
本题 key的取值范围在0-10^6之间，所以我们可以使用一个大小为10^6+1的超大数组来解这道题。这样能直接解决key的冲突问题。
- 为了保证哈希表的O(1)时间复杂度，
remove函数不会真的从数组中移除元素，而是将对应的值设置为-1。 - 该方法缺点也很明显，占用了很大的空间资源。如果key的取值范围很大的话，不建议使用这种方法
class MyHashMap(object):
def __init__(self):
self.map = [-1] * 1000001
def put(self, key, value):
self.map[key] = value
def get(self, key):
return self.map[key]
def remove(self, key):
self.map[key] = -1
拉链法
为了优化上面方案空间大小的问题，同时还需要确保时间复杂度必须为O(1)并且需要尽量避免key冲突的问题，在此延伸出了拉链法的解决方案。
拉链法其实就是数组与链表的结合，也就是说数组中的每一个元素都是链表，如果遇到哈希冲突直接将value添加到链表中即可。这样既达到了O(1)的时间复杂度又完美解决的哈希冲突的问题。
class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.maps = [[-1] * 1000 for x in range(1001)]
def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
row, col = key // 1000, key % 1000
self.maps[row][col] = value
def get(self, key: int) -> int:
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
"""
row, col = key // 1000, key % 1000
return self.maps[row][col]
def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""
row, col = key // 1000, key % 1000
self.maps[row][col] = -1
复杂度分析
- 时间复杂度 O（1）
- 空间复杂度 （数据范围）