lineprobing

Line probing is a technique used in computer science, particularly in the context of hash tables. It is a collision resolution strategy. When a hash function maps two or more keys to the same index in the hash table, a collision occurs. Line probing, also known as linear probing, resolves this by sequentially searching for the next available slot in the table.

In linear probing, if the calculated hash index is already occupied, the algorithm examines the next index (index + 1). If that is also occupied, it checks index + 2, and so on, wrapping around to the beginning of the table if the end is reached. This process continues until an empty slot is found where the new key-value pair can be stored.

When searching for a key, the same probing sequence is followed. The algorithm starts at the initial hash index and checks if the key matches. If not, it probes linearly through subsequent slots until the key is found or an empty slot is encountered, indicating the key is not present.

A significant drawback of linear probing is primary clustering. This occurs when occupied slots form contiguous blocks, leading to longer search and insertion times as the probing sequence has to traverse these clusters. Secondary clustering can also occur, where keys that hash to the same initial index follow the same probing sequence. Despite these issues, linear probing is simple to implement and can be efficient for hash tables with low load factors (the ratio of occupied slots to total slots).