Why is the time complexity of haskey is O(1). For finding a key it has to iterate all the element on the list so why it is O(1)
What is the time complexity of contains method of arraylist
Asked
Active
Viewed 581 times
0
user3856587
- 33
- 7
-
1Why not try a Google search! – Am_I_Helpful Sep 13 '14 at 19:52
-
Did not get the satisfactory answer – user3856587 Sep 13 '14 at 19:53
-
Check out this answer: http://stackoverflow.com/questions/4100677/is-there-a-comprehensive-big-o-listing-of-java-data-structures/25338144#25338144 – nem035 Sep 13 '14 at 19:55
-
are you sure hash always has O(1)? what about collision? – ajay.patel Sep 13 '14 at 19:56
-
ya @zerocool agree with you could provide me some link or information – user3856587 Sep 13 '14 at 19:59
-
okie..what exactly you don't understand? where are you stuck? can you probably update the question with your understanding and with what you dont understand. It will make things easier. – ajay.patel Sep 13 '14 at 20:05
1 Answers
3
A hashtable is not a list. It is a data structure specifically designed for O(1) lookup in the common case (the worst-case lookup is indeed O(n)). It achieves this by the notion of a hash, which is a number derived from the key's contents, used to directly calculate the index of the key in an array.
ArrayList is just an array underneath, so contains is what you would expect it to be for a linear-search structure.
Marko Topolnik
- 195,646
- 29
- 319
- 436