Implement a hash table
10 min readJan 23, 2020
706. Design HashMap
A quick summary can be found from my article shared on LeetCode.
A naive way can get accepted. However, it is very memory consuming.
class MyHashMap:def __init__(self):
"""
Initialize your data structure here.
"""
self.a = [-1]*1000010def put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
self.a[key] = valuedef 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
"""
return self.a[key]def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""
self.a[key] = -1# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)
This is a better one:
https://leetcode.com/problems/design-hashmap/discuss/185347/Hash-with-Chaining-Python
# using just arrays, direct access table
# using linked list for chaining
class ListNode:
def __init__(self, key, val):
self.pair = (key, val)
self.next = None
class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.m = 1000;
self.h = [None]*self.m
def put(self, key, value):
"""
value will always be non-negative.
:type key: int
:type value: int
:rtype: void
"""
index = key % self.m
if self.h[index] == None:
self.h[index] = ListNode(key, value)
else:
cur = self.h[index]
while True:
if cur.pair[0] == key:
cur.pair = (key, value) #update
return
if cur.next == None: break
cur = cur.next
cur.next = ListNode(key, value)
def get(self, key):
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
:type key: int
:rtype: int
"""
index = key % self.m
cur = self.h[index]
while cur:
if cur.pair[0] == key:
return cur.pair[1]
else:
cur = cur.next
return -1
def remove(self, key):
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
:type key: int
:rtype: void
"""
index = key % self.m
cur = prev = self.h[index]
if not cur: return
if cur.pair[0] == key:
self.h[index] = cur.next
else:
cur = cur.next
while cur:
if cur.pair[0] == key:
prev.next = cur.next
break
else:
cur, prev = cur.next, prev.next
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)Here is my code based on this one
class LinkedList:
def __init__(self, key, value):
self.pair = (key, value)
self.next = Noneclass MyHashMap:def __init__(self):
"""
Initialize your data structure here.
"""
self.C = 1000
self.hashtable = [None]*self.Cdef put(self, key: int, value: int) -> None:
"""
value will always be non-negative.
"""
i = key%self.C
if self.hashtable[i] is None:
self.hashtable[i] = LinkedList(key, value)
else:
node = self.hashtable[i]
while True:
if node.pair[0] == key:
node.pair = (key, value)
return
if node.next is None:
node.next = LinkedList(key, value)
return
node = node.nextdef 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
"""
i = key%self.C
node = self.hashtable[i]
while node is not None:
key_, value= node.pair
if key==key_:return value
node = node.next
return -1def remove(self, key: int) -> None:
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
"""
i = key%self.C
node = self.hashtable[i]
if node is None:return
parent, node = node, node.next
key_, _ = parent.pair
if key_==key:
self.hashtable[i]=node
return
while node is not None:
key_, value = node.pair
if key_ == key:
parent.next = node.next
return
parent, node = node, node.next
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)
Java code is here
class MyHashMap {
class Node{
final int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
final int SIZE = 10001;
Node[] array;
public MyHashMap() {
array = new Node[SIZE];
}public void put(int key, int value) {
int index = hash(key);
Node head = array[index];
Node node = head;
while (node != null) {
if (node.key == key) {
node.value = value;
return;
}
node = node.next;
}
Node newNode = new Node(key, value);
newNode.next = head;
array[index] = newNode;
}public int get(int key) {
int index = hash(key);
Node node = array[index];
while (node != null) {
if (node.key == key) return node.value;
node = node.next;
}
return -1;
}public void remove(int key) {
int index = hash(key);
Node node = array[index];
while (node != null) {
if (node.key == key) {
node.value = -1;
return;
}
node = node.next;
}}private int hash(int key) {
return Integer.hashCode(key) % SIZE;
}
}
Hash in python
>>> hash(None)
115747397
>>> hash(0)
0
>>> hash(1)
1
>>> hash(2)
2
>>> hash(10000000000)
10000000000
>>> hash(10000000000000000000000000000000000000000000000000000000000)
1767470299500112132
>>> hash(10000000000000000000000000000000000000000000000000000000001)
1767470299500112133
>>> hash(10000000000000000000000000000000000000000000000000000000002)
1767470299500112134
>>> hash(10000000000000000000000000000000000000000000000000000000003)
1767470299500112135
>>> hash(10000000000000000000000000000000000000000000000000000000004)
1767470299500112136
>>> hash(10000000000000000000000000000000000000000000000000000000005)
1767470299500112137What is the capacity of the hashtable for python
If we use this O(n) algorithm to check, it will run forever.
>>> while True:
... i+=1
... if hash(i)!=i:
... print(i)
... breakWe can use binary O(log(n)) algorithm to check
>>> def good(m):
... hash(m)==m>>> def binary():
... l, r = 0, 10000000000000000000000000000000000000000000000000000000000
... while l<r:
... m = (l+r+1)//2
... if good(m):l=m
... else:r=m-1
... return l>>> binary()
2305843009213693950>>> hash(2305843009213693951)
0
>>> hash(2305843009213693952)
1
>>> hash(2305843009213693953)
2
C++ code (112 ms)
double linked list (O(k))
It is using a vector to save the results. And a double linked list is used to handle hash collision. The complexity is O(k) when get and put where k is the average size of list length.
class MyHashMap {
private:
vector<list<pair<int,int>>> hashmap_;
// using a prime number
int size_ = 9851;
public:
/** Initialize your data structure here. */
MyHashMap()
{
hashmap_.resize(size_);
}
/** value will always be non-negative. */
void put(int key, int value)
{
auto &list = hashmap_[key % size_];
for (auto & val : list)
{
if (val.first == key)
{
val.second = value;
return;
}
}
list.emplace_front(key, value);
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key)
{
const auto &list = hashmap_[key % size_];
if (list.empty()) return -1;
for (const auto & val : list)
if (val.first == key)
return val.second;
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key)
{
auto &list = hashmap_[key % size_];
list.remove_if([key](auto& n) { return n.first == key; });
}
};Lightweight forward list (O(k))
Or we can change it to a lightweight forward list.
class MyHashMap {
private:
//change from list to forward_list can speed up from 112 ms to 104 ms.
vector<forward_list<pair<int,int>>> hashmap_;
int size_ = 9851;
public:
/** Initialize your data structure here. */
MyHashMap()
{
hashmap_.resize(size_);
}
/** value will always be non-negative. */
void put(int key, int value)
{
auto &list = hashmap_[key % size_];
for (auto & val : list)
{
if (val.first == key)
{
val.second = value;
return;
}
}
list.emplace_front(key, value);
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key)
{
const auto &list = hashmap_[key % size_];
if (list.empty()) return -1;
for (const auto & val : list)
if (val.first == key)
return val.second;
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key)
{
auto &list = hashmap_[key % size_];
list.remove_if([key](auto& n) { return n.first == key; });
/*
for(auto it=list.begin();it!=list.end();++it){
if(it->first==key) { list.erase(it); return; }
}
*/
}
};Using a red-black tree (O(log K))
Using the red-black tree can further improve the complexity of the algorithm to O(log K).
class MyHashMap {
private:
//change from list to forward_list can speed up from 112 ms to 104 ms.
vector<map<int,int>> hashmap_;
int size_ = 9851;
public:
/** Initialize your data structure here. */
MyHashMap()
{
hashmap_.resize(size_);
}
/** value will always be non-negative. */
void put(int key, int value)
{
auto &m = hashmap_[key % size_];
m[key] = value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key)
{
auto &m = hashmap_[key % size_];
return m.count(key)?m[key]:-1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key)
{
auto &m = hashmap_[key % size_];
if (m.count(key)) m.erase(key);
}
};Other solutions
This one is kind of less efficient as we are using a vector instead of a list. Vector and list are almost the same, however, for erase, the vector is less efficient.
/*
Runtime: 128 ms, faster than 67.03% of C++ online submissions for Design HashMap.Memory Usage: 42.7 MB, less than 82.14% of C++ online submissions for Design HashMap.*/
class MyHashMap {
private:
vector<vector<pair<int, int>>> hashmap_;
int size_;
public:
/** Initialize your data structure here. */
MyHashMap(): size_{1000}{
hashmap_.resize(size_);
}
/** value will always be non-negative. */
void put(int key, int value) {
int idx = key%size_;
for(auto &p:hashmap_[idx]){if(p.first==key){p.second=value;return;}}
hashmap_[idx].emplace_back(key,value);
return;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
int idx = key%size_;
for(auto&p:hashmap_[idx])
if(p.first==key)
return p.second;
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
int idx = key%size_;
for(auto it=hashmap_[idx].begin();it!=hashmap_[idx].end();++it)
//Erase has more complexity compared with using list or forwardlist. vector erase: Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).
if(it->first==key){hashmap_[idx].erase(it);return;}
return;
}
};/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
We can change the code by changing the vector to list.
/*Runtime: 100 ms, faster than 99.53% of C++ online submissions for Design HashMap.Memory Usage: 43.4 MB, less than 75.00% of C++ online submissions for Design HashMap.
*/
class MyHashMap {
private:
vector<list<pair<int, int>>> hashmap_;
int size_;
public:
/** Initialize your data structure here. */
MyHashMap(): size_{1000}{
hashmap_.resize(size_);
}
/** value will always be non-negative. */
void put(int key, int value) {
int idx = key%size_;
for(auto &p:hashmap_[idx]){if(p.first==key){p.second=value;return;}}
hashmap_[idx].emplace_back(key,value);
return;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
int idx = key%size_;
for(auto&p:hashmap_[idx])
if(p.first==key)
return p.second;
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
int idx = key%size_;
for(auto it=hashmap_[idx].begin();it!=hashmap_[idx].end();++it)
//Erase has more complexity compared with using list or forwardlist. list can be faster.
if(it->first==key){hashmap_[idx].erase(it);return;}
return;
}
};/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
Complexity of these code:
put O(k)
get O(k)
remove O(k)
If we want to change it to O(1), is it possible?
Yes.
/*
Runtime: 140 ms, faster than 20.00% of C++ online submissions for Construct Target Array With Multiple Sums.Memory Usage: 29.6 MB, less than 100.00% of C++ online submissions for Construct Target Array With Multiple Sums.*/
class MyHashMap {
private:
vector<list<pair<int, int>>> hashmap_;
unordered_map<int,list<pair<int,int>>::iterator> m_;
int size_;
public:
/** Initialize your data structure here. */
MyHashMap(): size_{1000}{
hashmap_.resize(size_);
}
/** value will always be non-negative. */
void put(int key, int value) {
auto it = m_.find(key);
bool found = it!=m_.end();
int idx = key%size_;
if(found)m_[key]->second=value;
else{
hashmap_[idx].emplace_back(key,value);
m_[key] = --hashmap_[idx].end();
}
return;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
auto it = m_.find(key);
bool found = it!=m_.end();
if (found)return it->second->second;
else return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
auto it = m_.find(key);
bool found = it!=m_.end();
if (found){
int idx = key%size_;
hashmap_[idx].erase(it->second);
m_.erase(key);
}
return;
}
};/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
The solution above is O(1), however, it is meaningless as we are using a hash table to implement another hash table. It is not so smart cheating and it is essential to the following cheating code.
/*
Runtime: 116 ms, faster than 90.12% of C++ online submissions for Design HashMap.
Memory Usage: 42.6 MB, less than 82.14% of C++ online submissions for Design HashMap.
*/
class MyHashMap {
private:
unordered_map<int,int> m_;
public:
/** Initialize your data structure here. */
MyHashMap(){
}
/** value will always be non-negative. */
void put(int key, int value) {
m_[key] = value;
return;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
auto it = m_.find(key);
bool found = it!=m_.end();
if (found)return m_[key];
else return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
auto it = m_.find(key);
bool found = it!=m_.end();
if (found)m_.erase(key);
return;
}
};/**
* Your MyHashMap object will be instantiated and called as such:
* MyHashMap* obj = new MyHashMap();
* obj->put(key,value);
* int param_2 = obj->get(key);
* obj->remove(key);
*/
This article discussed several ways to implement the hash table. It shows several O(k) solution. Also, it shows why O(1) solution is not OK.
Thanks for reading.
