CODEWITHSUNDEEP
javaarraysperformancehashmaptime-complexity
Koopa
Koopa

Reputation: 31

HashMap vs Array search Time-Complexity

So, I have a HashMap map containing ~120.000 entries. Every time a new entry comes, I check if the entry already exists in the HashMap (if(!map.containsKey(hashcode))) and if it doesn't I create a new object and put it in the HashMap.

Now my question is: Would it be better to create a boolean array NxN (with N = 6.000) and check every time if the array element in [n1][n2] is false (not in hashmap yet) or true (the pair is in HashMap), instead of using the .containsKey()?

Upvotes: 3

Views: 3190

Answers (3)

Ivan
Ivan

Reputation: 8758

Map has computeIfAbsent() method which does exactly what you need:

  • If the specified key is not already associated with a value (or is mapped
  • to {@code null}), attempts to compute its value using the given mapping
  • function and enters it into this map unless {@code null}. *

  • If the function returns {@code null} no mapping is recorded. If

  • the function itself throws an (unchecked) exception, the
  • exception is rethrown, and no mapping is recorded. The most
  • common usage is to construct a new object serving as an initial
  • mapped value or memoized result

Regarding option with array, if your hashing algorithm for keys is good then your map will execute lookups by key in approximately O(1) which is as good as lookup in array by index. But your additional array will use additional memory and is not needed in this case.

Upvotes: 2

Sid
Sid

Reputation: 4995

Nope, containsKey is a perfectly fine way. HashMaps have a usual lookups of O(1), so it should not be an issue, unless the objects being stored have a poorly implemented hash algorithm. Only question could be, why do you have so many entries in a HashMap?

Upvotes: 0

Chandrakant Audhutwar
Chandrakant Audhutwar

Reputation: 345

See, HashMap is having Time Complexity of O(1), so getting checked by containsKey is best solution in your case.

Upvotes: 0

Related Questions