Problem Detail: 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.
Asked By : zallarak
Answered By : David Richerby
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 $8237643bmod 1034$, your response will be to reach for your calculator; if I ask you what is $8237643bmod 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.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/19020
