4

To solve Dynamic programming problem I used two approaches to store table entries, one using multi dimension array ex:tb[m][n][p][q] and other using hashmap and using indexes of 1st approach to make string to be used as key as in "m,n,p,q". But on one input first approach completes in 2 minutes while other takes more than 3 minutes. If access time of both hashmap and array is asymptotically equal than why so big difference in performance ?

rainyday
  • 353
  • 3
  • 17
  • 1
    We need to have some code to analyze its performance. – EsotericVoid Jul 23 '17 at 14:58
  • 1
    Can anyone tell the reason for downvotes ? – rainyday Jul 23 '17 at 17:20
  • 3
    Although I do not know the exact reasons, it may be because your original questions didn't follow these [guidelines](https://stackoverflow.com/help/how-to-ask). As a general rule of thumb, questions should be written in the same manner as if you asked it to a busy workmate. Introduce the problem, provide context, explain what you have already tried and try and make it reproducible. The problem should be as specific as possible and the answer applicable to as large an audience as possible. The lack of code initially may be the best guess. – Sumi Straessle Jul 23 '17 at 17:53
  • Possible duplicate of [Hashmap vs Array performance](https://stackoverflow.com/questions/6462055/hashmap-vs-array-performance) – EsotericVoid Jul 23 '17 at 17:53
  • @SumiStraessle Couldn't have said it better myself. –  Jul 24 '17 at 00:27
  • Updated my answer to make it short – rainyday Jul 28 '17 at 18:40

1 Answers1

8

Like mentioned here:

HashMap uses an array underneath so it can never be faster than using an array correctly.

You are right, array's and HashMap's access time is in O(1) but this just says it is independent on input size or the current size of your collection. But it doesn't say anything about the actual work which has to be done for each action.

To access an entry of an array you have to calculate the memory address of your entry. This is easy as array's memory address + (index * size of entity).

To access an entry of a HashMap, you first have to hash the given key (which needs many cpu cycles), then access the entry of the HashMap's array using the hash which holds a list (depends on implementation details of the HashMap), and last you have to linear search the list for the correct entry (those lists are very short most of the time, so it is treated as O(1)).

So you see it is more like O(10) for arrays and O(5000) hash maps. Or more precise T(Array access) for arrays and T(hashing) + T(Array access) + T(linear search) for HashMaps with T(X) as actual time of action x.

Obenland
  • 856
  • 16
  • 28