On Fri, Apr 13, 2012 at 02:36, 胡瀚森 <softrank.net@xxxxxxxxx> wrote: > Hi everyone. > > I'm still reading CRUSH source code. > > When reading src/crush/hash.c, I've got some questions about the hash function. > > 1. There are several magic numbers there, like 1315423911, 231232, > 1232. Are they arbitrary or do they really mean something in theory? > > 2. crush_hashmix macro is a part of Jenkins hash function. In the > series of crush_hash_rjenkins1_* functions, why input parameters are > mixed this way instead of something else? Are they arbitrary or do > they really mean something in theory? Typically, hash functions have primes and similar magic numbers, and carefully-chosen mixing functions, to strike a balance between result uniformity, collision avoidance, and performance. CRUSH uses what is known as a Jenkins hash, which is one of the de facto standard "fast hashes". See more: http://en.wikipedia.org/wiki/Jenkins_hash_function http://burtleburtle.net/bob/hash/evahash.html > 3. I read the phrase "funneling hash", but I don't quite understand > what does it mean. Funneling is an undesirable property in a hash function, where when input changes in only a few bit locations, the output also changes in only a few bit locations. More desirable is that even a single bit change in the input causes a "big disturbance" in the output. -- To unsubscribe from this list: send the line "unsubscribe ceph-devel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
