A hash table is generally referred to as a data structure that has \"close to\"

Question

A hash table is generally referred to as a data structure that has "close to" O(1) time complexity for addition, lookup and removal. Part of this statement is ambiguous because "close to" is not well defined. Also, part of the statement is, in a sense, wrong, due to the fact that some information is left out. Select ALL true statements that help clarify the story on hash set operations.

The data values being added, removed or search for have to be hashed before the lookup occurs, so even if the lookup is O(1) the cost of getting the object hash code may be higher

A hash table may have to resize for an Add/Insert operation

A hash table may have multiple entries in a linked-list at a single index that corresponds to several different object hash codes. The cost of traversing through this list could be > O(1).

"Close to" may refer to the fact that the vast majority of insertions tend to be O(1) and only on rare occasions (if we have a good hashing function) will an insertion cost us O(n)

The data values being added, removed or search for have to be hashed before the lookup occurs, so even if the lookup is O(1) the cost of getting the object hash code may be higher

A hash table may have to resize for an Add/Insert operation

A hash table may have multiple entries in a linked-list at a single index that corresponds to several different object hash codes. The cost of traversing through this list could be > O(1).

"Close to" may refer to the fact that the vast majority of insertions tend to be O(1) and only on rare occasions (if we have a good hashing function) will an insertion cost us O(n)

Explanation / Answer

(i)TRUE
First statement is correct. Some times it will be more than O(1) since when we insert multiple
entries on same index.

(ii) TRUE
If table was full then it will increase table size.

(iii) TRUE
As discussed in first statement or option, some times it can be.

(iv) FALSE
At any cost it will be O(1),, some rare cases it may be > O(1) but not O(n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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