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.
Question
sparksy21
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