What is a hash table and how does it work?

A hash table is a data structure that maps keys to values using a hash function to compute an index into an array of buckets or slots. The hash function converts the key into an array index, providing average O(1) time complexity for insertion, deletion, and lookup. Hash tables handle collisions using techniques like chaining (linked lists at each bucket) or open addressing (probing for next available slot).