Linear Probing in Open Addressing
I have an array with size m = 11
and my hash function is Division method : h(k) = k mod m
I have an integer k = 10
and 10 mod 11 is -1
so where should I put this key in the array? I should put this key in the slot which its index is 10?
please help me thanks
EDITED : for getting my answer well for example I have integers like k = 10,22,31,4,15,28,17,88,59
the array would be like this?thanks
10 9 8 7 6 5 4 3 2 1 0 index
10 31 59 17 28 4 15 88 22 keys
As it's usually done, 10 mod 11 is 10, so yes, you'd normally use index 10.
Edit: To generalize: at least as it's normally defined, given two positive inputs, a modulo will always produce a positive result. As such, your questions about what to do with negative results don't really make sense with respect to the normal definition.
If you really do have the possibility of getting a negative result, my immediate reaction would be to switch to some language that will produce a reasonable result. If you can't do that, then you'd probably want to move the value into the correct range by adding m
to the negative number until you get a number in the range [0..m) so it fits the normal definition of mod
, then use that as your index.
精彩评论