Formatted question description: https://leetcode.ca/all/706.html

# 706. Design HashMap

Easy

## Description

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

• put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
• get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
• remove(key): Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1);            // returns 1
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1
hashMap.remove(2);          // remove the mapping for 2


Note:

• All values will be in the range of [0, 1000000].
• The number of operations will be in the range of [1, 10000].
• Please do not use the built-in HashMap library.

## Solution

Since all keys and values are in the range of [0, 1000000], create an array with length 1000001, which has int type. Initially, all the elements in the array are -1.

For the put function, set the value at index key in the array to be value.

For the remove function, set the value at index key in the array to be -1.

For the get function, simply return the element at index key.

Some of the questions which can be asked to the interviewer before implementing the solution:

• For simplicity, are the keys integers only?
• For collision resolution, can we use chaining?
• Can we assume inputs are valid or do we have to validate them?
• Can we assume this fits memory?
• class MyHashMap {

int[] hash;

/** Initialize your data structure here. */
public MyHashMap() {
hash = new int[1000001];
Arrays.fill(hash, -1);
}

/** value will always be non-negative. */
public void put(int key, int value) {
hash[key] = value;
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
return hash[key];
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
hash[key] = -1;
}
}

/**
* 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);
*/

• // OJ: https://leetcode.com/problems/design-hashmap/
// Time: O(1)
// Space: O(1)
class MyHashMap {
const static int N = 1000001;
int m[N];
public:
MyHashMap() {
for (int i = 0; i < N; ++i) m[i] = -1;
}
void put(int key, int value) {
m[key] = value;
}
int get(int key) {
return m[key];
}
void remove(int key) {
m[key] = -1;
}
};

• class MyHashMap:

def __init__(self):
"""
"""
self.buckets = 1000
self.itemsPerBuckect = 1001
self.hashmap = [[] for _ in range(self.buckets)]

def hash(self, key):
return key % self.buckets

def pos(self, key):
return key // self.buckets

def put(self, key, value):
"""
value will always be positive.
:type key: int
:type value: int
:rtype: void
"""
hashkey = self.hash(key)
if not self.hashmap[hashkey]:
self.hashmap[hashkey] = [None] * self.itemsPerBuckect
self.hashmap[hashkey][self.pos(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
"""
hashkey = self.hash(key)
if (not self.hashmap[hashkey]) or self.hashmap[hashkey][self.pos(key)] == None:
return -1
else:
return self.hashmap[hashkey][self.pos(key)]

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
"""
hashkey = self.hash(key)
if self.hashmap[hashkey]:
self.hashmap[hashkey][self.pos(key)] = None

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)


Or, use bucket strategy.

• public class Design_HashMap {
class MyHashMap {
private int capacity;

/**
* Initialize your data structure here.
*/
public MyHashMap() {
this.capacity = 10000;
for (int i = 0; i < capacity; i++) {
}
}

/**
* value will always be non-negative.
*/
public void put(int key, int value) {
int bucketIdx = hashCode(key);
}

/**
* Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
*/
public int get(int key) {
int bucketIdx = hashCode(key);
return buckets[bucketIdx].get(key);
}

/**
* Removes the mapping of the specified value key if this map contains a mapping for the key
*/
public void remove(int key) {
int bucketIdx = hashCode(key);
buckets[bucketIdx].remove(key);
}

private int hashCode(int key) {
return Integer.hashCode(key) % capacity;
}
}

class ListNode {
ListNode next, prev;
int key;
int val;

public ListNode(int key, int val) {
next = prev = null;
this.key = key;
this.val = val;
}
}

ListNode dummyTail;

dummyTail = new ListNode(-1, -1);
}

public void insertToHead(int key, int val) {
ListNode existNode = search(key);
if (existNode != null) {
existNode.val = val;
} else {
ListNode newNode = new ListNode(key, val);
newNode.next = nextNode;
nextNode.prev = newNode;
}
}

private ListNode search(int key) {
while (p != dummyTail) {
if (p.key == key) {
return p;
}

p = p.next;
}

return null;
}

public int get(int key) {
ListNode node = search(key);

return node == null ? -1 : node.val;
}

public void remove(int key) {
ListNode currNode = search(key);
if (currNode != null) {
ListNode prevNode = currNode.prev;
ListNode nextNode = currNode.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
}
}

/**
* 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);
*/
}

• // OJ: https://leetcode.com/problems/design-hashmap/
// Time: O(1)
// Space: O(1)
class MyHashMap {
const static int N = 1000001;
int m[N];
public:
MyHashMap() {
for (int i = 0; i < N; ++i) m[i] = -1;
}
void put(int key, int value) {
m[key] = value;
}
int get(int key) {
return m[key];
}
void remove(int key) {
m[key] = -1;
}
};

• class MyHashMap:

def __init__(self):
"""
"""
self.buckets = 1000
self.itemsPerBuckect = 1001
self.hashmap = [[] for _ in range(self.buckets)]

def hash(self, key):
return key % self.buckets

def pos(self, key):
return key // self.buckets

def put(self, key, value):
"""
value will always be positive.
:type key: int
:type value: int
:rtype: void
"""
hashkey = self.hash(key)
if not self.hashmap[hashkey]:
self.hashmap[hashkey] = [None] * self.itemsPerBuckect
self.hashmap[hashkey][self.pos(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
"""
hashkey = self.hash(key)
if (not self.hashmap[hashkey]) or self.hashmap[hashkey][self.pos(key)] == None:
return -1
else:
return self.hashmap[hashkey][self.pos(key)]

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
"""
hashkey = self.hash(key)
if self.hashmap[hashkey]:
self.hashmap[hashkey][self.pos(key)] = None

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)


List<int[]>

• class MyHashMap {
//Load factor = 10000/size = 0.75
List<int[]>[] lists; //using List<List<int[]>> lists is fine as well.
int size = 13000;

//O(size)
/** Initialize your data structure here. */
public MyHashMap() {
lists = new ArrayList[size];
for(int i=0; i<lists.length; i++)
lists[i] = new ArrayList<>(); //don't use linkedlist in my version which makes put() O(L^2)
}

public int getHashcode(int key)
{
return key%size;
}

//O(L)
/** value will always be non-negative. */
public void put(int key, int value) {
int index = getHashcode(key);
for(int i=0; i<lists[index].size(); i++)
{
if(lists[index].get(i)[0]==key)
{
lists[index].get(i)[1]=value;
return;
}
}
}

//O(L)
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
int index = getHashcode(key);
for(int i=0; i<lists[index].size(); i++)
{
if(lists[index].get(i)[0]==key)
return lists[index].get(i)[1];
}
return -1;
}

//O(L)
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
int index = getHashcode(key);
for(int i=0; i<lists[index].size(); i++)
{
if(lists[index].get(i)[0]==key)
lists[index].remove(i);
}
return;
}
}


• // OJ: https://leetcode.com/problems/design-hashmap/
// Time: O(1)
// Space: O(1)
class MyHashMap {
const static int N = 1000001;
int m[N];
public:
MyHashMap() {
for (int i = 0; i < N; ++i) m[i] = -1;
}
void put(int key, int value) {
m[key] = value;
}
int get(int key) {
return m[key];
}
void remove(int key) {
m[key] = -1;
}
};

• class MyHashMap:

def __init__(self):
"""
"""
self.buckets = 1000
self.itemsPerBuckect = 1001
self.hashmap = [[] for _ in range(self.buckets)]

def hash(self, key):
return key % self.buckets

def pos(self, key):
return key // self.buckets

def put(self, key, value):
"""
value will always be positive.
:type key: int
:type value: int
:rtype: void
"""
hashkey = self.hash(key)
if not self.hashmap[hashkey]:
self.hashmap[hashkey] = [None] * self.itemsPerBuckect
self.hashmap[hashkey][self.pos(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
"""
hashkey = self.hash(key)
if (not self.hashmap[hashkey]) or self.hashmap[hashkey][self.pos(key)] == None:
return -1
else:
return self.hashmap[hashkey][self.pos(key)]

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
"""
hashkey = self.hash(key)
if self.hashmap[hashkey]:
self.hashmap[hashkey][self.pos(key)] = None

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)


List<List<Integer>> not passing OJ large dataset, possibly some collisions

test case:

["MyHashMap","put","get","put","get"]
[[],[1000000,1],[1000000],[0,2],[0]]


if matrix 1000*1000, then 0 and 1000000 will colide, so make it 1001

• class MyHashMap {

int bucketSize = 1000;
int eachBucketLength = 1001;
List<List<Integer>> data;

/** Initialize your data structure here. */
public MyHashMap() {
data = new ArrayList<>();
}

/** value will always be non-negative. */
public void put(int key, int value) {
if (data.get(hash(key)).isEmpty()) {
}

data.get(hash(key)).set(position(key), value);
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
if (!data.get(hash(key)).isEmpty()) {
return data.get(hash(key)).get(position(key));
}

return -1;
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
if (!data.get(hash(key)).isEmpty()) {
data.get(hash(key)).set(position(key), -1);
}
}

private int hash(int key) {
return key % bucketSize;
}

private int position(int key) {
return key / eachBucketLength;
}
}

/**
* 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);
*/


• // OJ: https://leetcode.com/problems/design-hashmap/
// Time: O(1)
// Space: O(1)
class MyHashMap {
const static int N = 1000001;
int m[N];
public:
MyHashMap() {
for (int i = 0; i < N; ++i) m[i] = -1;
}
void put(int key, int value) {
m[key] = value;
}
int get(int key) {
return m[key];
}
void remove(int key) {
m[key] = -1;
}
};

• class MyHashMap:

def __init__(self):
"""
"""
self.buckets = 1000
self.itemsPerBuckect = 1001
self.hashmap = [[] for _ in range(self.buckets)]

def hash(self, key):
return key % self.buckets

def pos(self, key):
return key // self.buckets

def put(self, key, value):
"""
value will always be positive.
:type key: int
:type value: int
:rtype: void
"""
hashkey = self.hash(key)
if not self.hashmap[hashkey]:
self.hashmap[hashkey] = [None] * self.itemsPerBuckect
self.hashmap[hashkey][self.pos(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
"""
hashkey = self.hash(key)
if (not self.hashmap[hashkey]) or self.hashmap[hashkey][self.pos(key)] == None:
return -1
else:
return self.hashmap[hashkey][self.pos(key)]

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
"""
hashkey = self.hash(key)
if self.hashmap[hashkey]:
self.hashmap[hashkey][self.pos(key)] = None

# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)