I am studying data structures and the book \"How to Think About Algorithms\" by

Question

I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that:

"Hopefully, all the elements that are in your set happen to be placed into different entries in the table. In this case one can

determine whether or not an element is contained in the set,
ask for an arbitrary element form the set,
determine the number of elements in the set,
iterate through all the elements,
and add and delete elements

in constant time i.e independently of the number of items in the set."

when speaking about hash tables. I don't understand how it is possible to iterate through all the elements in constant time. Shouldn't it be O(N) since we iterate through all of them?

Explanation / Answer

What you said is true. You can't iterate through all the elements in a hash table in constant time. It would take O(N). But the author is not actually talking about all the elements in the hash table, but to iterate though each single element (in which there is only one element, making it constant). It comes down to the assumption here:

"all the elements that are in your set happen to be placed into different entries in the table."

In this case for each element, there is a single node. If this was not true you need to form a link-list for the hash table table, that is when there is collision. Then for each element it's no longer a constant time. But whatever item in the hash table happens to have the longest list.

Again, the explanation isn't clear here. As it looks like the author is saying iterating through all the elements in a hash table, and not iterating through for each element.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.