Google publishes FarmHash, a new family of hash functions for strings
Google has just announced FarmHash, a new family of hash functions for strings. FarmHash is a successor to CityHash, from which it inherits many tricks and techniques. FarmHash has multiple goals and claims to improve CityHash on several accounts.
According to Geoff Pike, software engineer at Google and co-author of the library together with Jyrki Alakuijala, although FarmHash development has been influenced by the types of CPUs that are common in Google’s datacenters, one of the library goals is being fast and easy for developers to use in phones, tablets, and PCs too. This has led to improving the existing 32 and 64 bit hash implementations.
Another improvement over CityHash is providing one interface on top of multiple platform-specific implementations, says Geoff. So, FarmHash also addresses the case where a developer simply wants a fast, robust hash function for hash tables, and it need not be the same on every platform.
Accounting for all this, FarmHash implementation reaches a count of about 1500 lines of code (excluding test-related code), versus approximately 600 lines of code in CityHash. A thorough analysis of CityHash can be found online.
Currently, FarmHash only includes hash functions for byte arrays, on 32, 64, and 128 bit platforms. Future development plans include support for integers, tuples, and other data.
CityHash's hashing algorithm was found to be vulnerable to attacks targeting weaknesses in the hash algorithms that permit multiple hash collisions to take place (hash flooding). This could quickly overload any application using such hash algorithm, although no CityHash exploits are known. The vulnerability also affected other major hash implementations based on MurmurHash. It is not clear at the moment whether FarmHash is immune to the same vulnerability.
Dmytro Svarytsevych Oct 30, 2014