I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash?

One reason to rehash seems to be load factor or hash table size. When I want to lower the load factor and increase hash table size, then I need to rehash. Any other reasons, especially in real database development? Thanks!

  • 1
    $\begingroup$ Collision ratio. (Load factor/table size is just a means to keep it low.) $\endgroup$
    – greybeard
    Aug 9 '20 at 20:48
  • $\begingroup$ @greybeard True! Collision ratio can be high without load factor! Thanks :) $\endgroup$
    – Heuyie
    Aug 20 '20 at 21:04

One example is consistent hashing. The usual scenario used for motivation is assigning files to servers. To avoid having too many files associated with a single server, you map $n$ files to $m$ servers via some hash function $h:[n]\rightarrow[m]$. Suupose you add a new server or that an existing server crashes, then you would have to rehash all the files to maintain functionality (this entails actual copying of the contents). One solution that avoids this is mapping each file and sever to the unit circle, and associating each file with the first server met when moving anticlockwise. If $h:[n]\cup[m]\rightarrow \left\{(\cos t,sin t)| 0\le t\le 2\pi\}\right\}$ satisfies SUHA, i.e. $h(i)$ is uniformly distributed on the unit circle when $i$ is uniformly distributed over $[n]\cup [m]$, then the expected number of files moved after a crash is $\frac{n}{m}$.

  • $\begingroup$ Thanks for answering! This is like the case that I need to add a node in Cassandra cluster because now one node has too many entries, correct? $\endgroup$
    – Heuyie
    Aug 20 '20 at 21:07
  • $\begingroup$ I don't really know what's going on in Cassandra, but this is a common problem which is dealt with in one way or another in every distributed database. $\endgroup$
    – Ariel
    Aug 20 '20 at 21:10
  • $\begingroup$ OK! Thanks again :) $\endgroup$
    – Heuyie
    Aug 20 '20 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.