• 0

Hash table question


Question

Hi,

I'm going through some past CS exam papers at the moment, and I'm at a loss as to questions about hash tables. In particular, question 4 here. For part ©, part of the mark scheme for the Hash function says:

============================

Procedure Hash(var s : ARRAY of CHAR): Integer

VAR

i : INTEGER:

h : INTEGER;

BEGIN

h := 0;

i := 0;

while (i < K) AND (s =/= 0x) do // 0x is the null pointer

h := 27 * h + ORD(s) - ORD('a') + 1;

i := i + 1;

end;

while (i < K) do

h := 27 * h;

i := i + 1;

end;

return h;

end Hash;

=======================

I understand that multiplying the value of h by 27 is something to do with the fact that it's in base 27, but I don't understand how this achieves a monotonic hash function. I understand the logic of the two while loops - it's just what's being done to h that I don't really understand.

Thanks!

Link to comment
Share on other sites

1 answer to this question

Recommended Posts

  • 0

You are on the right track with the 27 being a base (0=null, 1-26=a-z, which is a total of 27). And if you rewrote the code so that the two loops were combined as one, it should be fairly obvious what the loops are trying to do (hint: it may help to think of the operation on h in the second loop as "h := 27 * h + 0"). And keep in mind what a monotone hash is--one that preserves the sort order. If you can identify what the loops are doing, then showing monotonicity should be trivial.

Link to comment
Share on other sites

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.