Which data structure is typically used to implement hash table ?

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.