Linear Probing

Both bucketing and chaining essentially makes use of a second dimension to handle collisions. This is not the case for linear probing. Linear Probing uses just a regular one dimensional array.

Insertion

The insertion algorithm is as follows:

• use hash function to find index for a record

• If that spot is already in use, we use next available spot in a "higher" index.

• Treat the hash table as if it is round, if you hit the end of the hash table, go back to the front

Each contiguous group of records (groups of record in adjacent indices without any empty spots) in the table is called a cluster.

Searching

The search algorithm is as follows:

• use hash function to find index of where an item should be.

• If it isn't there search records that records after that hash location (remember to treat table as cicular) until either it found, or until an empty record is found. If there is an empty spot in the table before record is found, it means that the the record is not there.

• NOTE: it is important not to search the whole array till you get back to the starting index. As soon as you see an empty spot, your search needs to stop. If you don't, your search will be incredibly slow

Removal

The removal algorithm is a bit trickier because after an object is removed, records in same cluster with a higher index than the removed object has to be adjusted. Otherwise the empty spot left by the removal will cause valid searches to fail.

The algorithm is as follows:

• find record and remove it making the spot empty

• For all records that follow it in the cluster, do the following:

  • determine the hash index of the record

  • determine if empty spot is between current location of record and the hash index.

  • move record to empty spot if it is, the record's location is now the empty spot.