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 tableh(k): hash function = k mod mk: keyI don't understand what the p lowest-order bits of k means. Any clarification would be very helpful.
Why should one not use a 2^p size hash table when using the division method as a hash function?
hash tables
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.)