# When using a hash and a collision occurs and linear probing is used how is that item found again

How is the search for the item supposed to find the specific item if the data is all clumped together and all the search is given is the output of the hash function. I don't understand how it knows which of the pieces of data is the one that corresponds to the key if linear probing has been used so it could be any of a number of pieces of data? Thanks for any help

## 2 Answers

Any given equality function over the objects. You're asking if an object is in a hash table, and it is if there is an object that is "equal" to the given object.

And remember that object equality implies hash equality.

• Thanks, but say I want to get an object that corresponds to a key and when the key is passed into the hash function it gives an array location, from that how do I know which of the elements is the one i want if there is a number of elements that have all been shifted along due to linear probing? Thanks Apr 23, 2017 at 22:41
• @JackFerguson The entry in the table contains a copy of the key. Apr 24, 2017 at 0:13

In linear probing, The hash function only points to the bucket in the hash table that is the starting index for the search. So say item $x$ after hashing has a hash value of $h(x)$. This is just the starting index of the bucket. If the data at hash bucket $h(x)$ is not equal to the data, we incrementally search $h(x)+1, h(x)+2,....$ till either the data is found or an empty slot if found.

• But when you say till the data is found how do you know when the data has been found if all you know is the key that corresponds to that piece of data? Apr 23, 2017 at 22:44