# Design a HashMap

• I got this question in an interview. Can anyone help me with the best approach to solve this question?

• Look up separate chaining and linear probing. The latter is more efficient.

• Sharing my Java solution using array with linked list. I tested a few cases and it works OK. Any suggestions/comments are welcome.

``````class MyHashMap {
private static final int SIZE = 32;

class Entry {
String key;
String value;
Entry next;
Entry(String key, String value) {
this.key = key;
this.value = value;
next = null;
}
}

private Entry[] table;

public MyHashMap() {
table = new Entry[SIZE];
}

public void put(String key, String value) {
Entry entry = new Entry(key, value);
int code = key.hashCode() % SIZE;
if (table[code] == null) {
table[code] = entry;
} else {
}
}

public String get(String key) {
int code = key.hashCode() % SIZE;
}
return null;
}

public void remove(String key) {
int code = key.hashCode() % SIZE;
Entry dummy = new Entry("0", "0");
Entry prev = dummy;
}
table[code] = dummy.next;
}

public boolean containsKey(String key) {
int code = key.hashCode() % SIZE;
}
return false;
}

return;
}
}
prev.next = node;
}
}
``````

• @ccyjoshua nicely done!

• @ccyjoshua it seems your solution has a fixed bucket size. The efficiency will drop quickly when the size is increasing. So it's better to adjust (increasing or decreasing) the bucket size on the fly based on a load factor. For example, the LF = 0.75, if the size of the HashMap > 0.75 * size of Bucket, we should double the size of the bucket. Then cut the bucket by half when size of the HashMap < 0.75 * half size of Bucket.

• @MuscleNerd theorically your suggestion is right.I wonder the real purpose behind this interview question.Is it just test interviewer's familiarity for HashMap implement?Or maybe require another way to design HashMap?

• @ccyjoshua
I thought get() in a hashmap must be O(1), but yours is O(n).

• Did you get the offer? I am thinking about accepting Goldman over Microsoft.

• This post is deleted!

• red black tree, my friends.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.