tags:

views:

17

answers:

1

Hi 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
A: 

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.

Jerry Coffin
so for example if I have k = 4 then 11 mode 4 = -6 so I should put the key in the slot which has the index = 5?
also I edited my example is this correct? I also use your edition in my answer:)
@matin1234: It doesn't look quite right to me. 4 mod 11 should be 4, so that would end up at index 4. Then 15 mod 11 is also 4, so (using linear probing) that would end up at index 5.
Jerry Coffin