1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – james king Apr 23 '17 at 22:41
  • $\begingroup$ @JackFerguson The entry in the table contains a copy of the key. $\endgroup$ – Gilles Apr 24 '17 at 0:13
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – james king Apr 23 '17 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.