Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I don't understand what is meant by:
"m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k." (pg. 231 of CLRS)
Terms defined:
m: size of hash table
h(k): hash function = k mod m
k: key
I don't understand what the p lowest-order bits of k means. Any clarification would be very helpful.
Refresh your knowledge of binary! The $p$ lowest-order bits of $k$ are the last $p$ bits when $k$ is written out in binary (i.e., the $p$ rightmost bits). For example, if $p=3$ and $k=17$ then $k$ is $10001$ in binary and the three lowest-order bits are $001$.
The point is that, in general, computing $k \bmod m$ is a relatively expensive operation. However, if $m=2^p$ is a power of two, the remainder operation is to just look at the $p$ lowest-order bits. That can be done in a single instruction, by taking the bitwise AND with $2^p-1$.
If it's easier, consider the decimal case. If I ask you what is $8237643\bmod 1034$, your response will be to reach for your calculator; if I ask you what is $8237643\bmod 1000$, you'll tell me that it's $643$ with barely a thought. This is because $1000=10^3$ is a power of ten, whereas $1034$ is not. (There's no immediate equivalent of the bitwise AND trick for decimal.)
I think you've got your answer of what does the p lowest-order bits of k means from this answer but answer to the question why m should not be a power of 2 lies behind the concept of
Choosing a good hash function is of the utmost importance. An uniform hash function is one that equally distributes data items over the whole hash table data structure. If the hash function is poorly chosen data items may tend to clump in one area of the hash table and many collisions will ensue. A non-uniform dispersal pattern and a high collision rate cause an overall data structure performance degradation.
When using division method if you are sure that the keys that are going to be used for a particular database have "All the low-order p bit patterns are equally likely" then choosing m equal to a power of 2 is not bad; in fact, it is same as choosing some other value of m which is not a power of 2.
But there maybe cases when keys are distributed in such a way that a large number of different keys have same low-order p bit patterns, then choosing m equal to a power of 2 will fail to provide uniform distribution.
The idea is that, hash function chosen should not be biased to some specific pattern(s) so that it can ensure equal distribution of data items over the whole hash table (without the knowledge of if keys are biased to a specific pattern) fairly in all the possible cases.
"When using the division method, we usually avoid certain values of m (table size). For example, m should not be a power of 2, since if m = 2^p , then h(k) is just the p lowest-order bits of k. Unless it is known that all low-order p bit patterns are equally likely, it is better to make the hash function depend on all the bits of the key."
--CLRS
For detailed explanation of hashing using division method check this answer.
