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
-
1Why not try a Google search!Am_I_Helpful– Am_I_Helpful2014-09-13 19:52:50 +00:00Commented Sep 13, 2014 at 19:52
-
Did not get the satisfactory answeruser3856587– user38565872014-09-13 19:53:36 +00:00Commented Sep 13, 2014 at 19:53
-
Check out this answer: stackoverflow.com/questions/4100677/…nem035– nem0352014-09-13 19:55:47 +00:00Commented Sep 13, 2014 at 19:55
-
are you sure hash always has O(1)? what about collision?ajay.patel– ajay.patel2014-09-13 19:56:25 +00:00Commented Sep 13, 2014 at 19:56
-
ya @zerocool agree with you could provide me some link or informationuser3856587– user38565872014-09-13 19:59:48 +00:00Commented Sep 13, 2014 at 19:59
|
Show 1 more comment
1 Answer
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.
