Which data structure is typically used to implement hash table ?
2023
Which data structure is typically used to implement hash table ?
Answer: B. Array — Answer: Array Why: A hash table is typically implemented as an array of buckets. A hash function maps each key to an index in that array, allowing…
- A.
Linked list
- B.
Array
- C.
Binary Tree
- D.
Stack
Attempted by 973 students.
Show answer & explanation
Correct answer: B
Answer: Array
Why: A hash table is typically implemented as an array of buckets. A hash function maps each key to an index in that array, allowing average-case constant time (O(1)) for lookup, insertion, and deletion.
Collision handling: When multiple keys map to the same array index, collisions are handled using strategies such as chaining (each bucket stores a list of entries) or open addressing (probing to find another slot).
Buckets can use different internal structures: commonly a linked list for chaining, and some implementations switch to a balanced tree for very large buckets to guarantee better worst-case performance.
Why the other structures are not the typical choice:
Linked list: Useful as the per-bucket structure for chaining, but not the overall container that maps keys to positions.
Binary tree: Provides ordered operations and O(log n) performance, and may be used inside buckets in some implementations, but is not the typical primary structure for a hash table.
Stack: Has LIFO semantics and does not support indexing by a hash; it is not suitable for implementing hash table operations.