Linear probing hash is a software to visualize the creation and manipulation of a hash table with linear-probing collision treatment for a better understanding.
Collision handling in a hash table using linear probing is a technique used to deal with situations where two or more calculated hash keys result in the same table index, i.e. a collision occurs.
A hash table is a data structure that allows the storage and fast retrieval of elements associated with unique keys. It uses a hash function to convert the keys into table indexes where the elements are stored. However, when two different keys produce the same index, a collision occurs.
Linear probing is one of the common approaches to resolve collisions in a hash table. In this technique, when a collision occurs, the element with the duplicate hash key is simply placed in the next available position in the table. The idea is to do a sequential search through subsequent indexes until an empty position is found where the element can be stored.
For example, suppose the hash function produced the same index for two different keys:
- Key A -> Hash (index) = 5
- Key B -> Hash (index) = 5 (collision)
If there is a collision, the hash table is updated as follows using linear probing:
- Index 5: Key A (first key calculated).
- Index 6: Key B (second calculated key, placed at the next available index after 5)
It is worth noting that when searching for an available position, it is necessary to take into account that the hash table can be circular, i.e. the search can continue from the beginning of the table if it has reached the end.
To use the program, simply install and run the LinearProbingHash1.0.exe file generated in the latest release.
When the program starts, it will open the screen below in which the user must enter the size of the hash table, this size being a prime number greater than 2. If the user does not enter anything, the software will use the size 23 by default:
After that, the main screen below will appear showing the table and the operations that can be performed.
| Name | Functionallity |
|---|---|
| Insert | Inserts one key and element given by the user on input |
| Search | Searches for an element according to the key given by the user |
| Delete | Deletes an element instantly according to the key given by the user |
| Set element available | Turns an element according to the key given by the user into available to be deleted later |
| Delete elements available | Deletes all elements set as available |
Note that deletion from a hash table using linear probing can be done in two different ways, namely immediate deletion and deletion with slot marking as available.
- In
immediate deletion, when an element is removed, the corresponding slot is emptied immediately, making it available for reuse. However, this approach can result in primary clustering and table fragmentation, impacting performance. - On the other hand, deletion with slot marking as
availableavoids immediate physical removal of the element. When an element is deleted, the slot is marked asavailable, indicating that it is free to be reused. This approach avoids primary clustering, but can take up table space with slots marked asavailable.
The choice of approach depends on the specific needs of the system, considering factors such as performance, fragmentation and table space occupation.