How Hash Tables Store Data and Resolve Collisions

A hash table is essentially an array that stores key‑value pairs called entries.

Each key (for example, a student ID) is processed by a hash function to produce an index, which determines the position of the entry in the array.

Hash collisions occur when two different keys (e.g., two students' IDs) produce the same hash value, causing both entries to map to the same array slot.

The two main collision‑resolution methods are open addressing and chaining.

Open addressing places a colliding entry in the next available slot: if slot 1 is occupied, it tries slot 2, then slot 3, and so on until an empty position is found.

Chaining stores multiple entries in the same bucket by linking them with a next pointer, forming a linked list; each entry points to the next colliding entry, and further collisions extend the list.

In summary, both open addressing and chaining aim to locate an alternative location for entries that would otherwise conflict in the hash table.

Source: blog.csdn.net/zsyoung/article/details/114505480