Is this the right way to implement a hashmap?

Is this the right way? Any comments on the hash functions? If asked a question like this in an interview, do I need to follow all OOP concepts(because I am using Java)? Like encapsulating the variables by writing getter and setter functions?

```
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class HashMapY {
private static int capacity = 100;
private Map[] arr;
private int size;

public HashMapY () {
arr = (Map[]) Array.newInstance(Map.class, capacity);
size = 0;
}

public V get(Object key) {
assert key!=null;
int i = -1;
if (key instanceof String || key instanceof Character){
i = hash(key.toString(), capacity) % capacity;
}
if (key instanceof Integer)
i = hash(Integer.parseInt(key.toString()))%capacity;
while (!key.equals(arr[i].k) && i > 31;
k ^= k pairs = new ArrayList();
assert key!=null;
int i = -1;
if (key instanceof String || key instanceof Character)
i = hash(key.toString(), capacity) % capacity;
if (key instanceof Integer)
i = hash(Integer.parseInt(key.toString()))%capacity;
while (!arr[i].k.equals(key) && capacity > i){
i = i + 1;
}
if (capacity >= i){
Object temp = arr[i].v;
while (arr[i]!= null && arr[i].k.equals(key)){

pairs.add(arr[i]);
arr[i] = null;
size--;
}
for (Map m : pairs){
this.put(m.k, m.v);
}
return (V) temp;
}
return null;
}

public int size() {
return size;
}

class Map {
K k;
V v;

public Map(K key, V val){
k = key;
v = val;
}
}

public boolean containsKey(K key) {
assert key!=null;

No, this is not the correct way to implement a hash map in Java, and especially not to implement the java.util.Map interface.

-
You aren't even explicitly implementing the Map interface.

-
What is (Map[]) Array.newInstance(Map.class, capacity) supposed to be? I'd think a simple new Map[capacity] would be sufficient.

-
You calculate your hashes yourself. However, every Object has a hashCode() method – use that instead.

-
Because you shouldn't calculate the hash code yourself, you shouldn't do any special handling of String and Character or Integer.

-
In your get method, what happens when the key is not one of your special classes? Not only will you be doing a linear search through your bins which breaks my expectations about the algorithmic complexity of a hash map, you'll also start at index -1, which will greet you with an ArrayIndexOutOfBoundsException.

-
Should you be implementing java.util.Map, the get method should throw an explicit NullPointerException rather than an optional assertion error as you do not want to allow null keys.

-
For some reason, the hash method is public. Furthermore, hash and doHash are not static although they don't access any object state.

-
Many criticisms about get also apply to put.

-
Your remove method sports this code: arr[i].k.equals(key). That risks a null pointer exception when arr[i] is null. Instead: arr[i] != null && key.equals(arr[i].k)

-
remove also has a loop that will only execute once or nonce:

while (arr[i]!= null && arr[i].k.equals(key)){
    pairs.add(arr[i]);
    arr[i] = null;
    size--;
}

Note that you never modify i.

-
In remove, it would be much simpler to look up the bin for that key, and then empty that bin rather. Consider putting your main get logic into a private int getBin(Object key), which you could use both in get:

int i = getBin(key);
... // assert i in range
if (arr[i] != null) {
    return arr[i].v;
}

and remove:

int i = getBin(key);
... // assert i in range
if (arr[i] != null) {
    V value = arr[i].v;
    arr[i] = null;
    size--;
    return value;
}

-
The Map class would usually be named Entry. Note that the java.util.Map interface contains a nested interface java.util.Map.Entry which you'd also have to implement for compatibility.

-
containsKey could be implemented using a getBin helper as

int i = getBin(key);
... // assert i in range
return arr[i] != null;

-
Your hash map can only contain 100 elements. If it grows larger, you should reallocate the storage array. You are furthermore resolving hash collisions via “open addressing” (using the next free bucket). Alternatively, you could use linked lists in each bucket, which also simplifies growing the hash table.

Then, there are many style problems in your code.

-
Consider changing a few whiles to easier to read for loops.

-
i = i + 1 could be abbreviated to i += 1, but is most often written i++.

-
Always use braces around the blocks of an if:

if (key instanceof Integer) {
    i = hash(Integer.parseInt(key.toString())) % capacity;
}

-
Many of your casts could be prevented with the use of generics. In remove, you have

Object temp = arr[i].v;
...
return (V) temp;

Instead:

V temp = arr[i].v;
...
return temp;

Regarding the question: “do I need to follow all OOP concepts(because I am using Java)?” – the answer is yes, but not because you are using Java. Instead, you'll want to write solid OOP code simply because your are writing object-oriented code, the language does not matter. Applying best practices is vastly preferable to producing shoddy, almost-working, bug-ridden code.

What now?

Your hash map implementation does not hold up to a code review. But that's not a problem.

• First, learn more about the topic: there is the Wikipedia article on hash tables, there is also the source code for java.util.HashMap (e.g. here). Compare what you've learned with your code, and try to understand your errors.

• Along the way, you'll probably also get better at actual Java programming.

• Then, try again. Start with a clean slate, and write another HashMap implementation. I'm sure you'll have improved by leaps and bounds. And please come back to have your new code reviewed :)

StackExchange Code Review Q#45770, answer score: 14