CODEWITHSUNDEEP
java
user3856587
user3856587

Reputation: 33

Time complexity of hash table and arraylist

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

Upvotes: 0

Views: 607

Answers (1)

Marko Topolnik
Marko Topolnik

Reputation: 200138

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.

Upvotes: 3

Related Questions