Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ


Choose your language

InfoQ Homepage News Google publishes FarmHash, a new family of hash functions for strings

Google publishes FarmHash, a new family of hash functions for strings

This item in japanese

Lire ce contenu en français


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.

Rate this Article


Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Community comments

  • SipHash

    by Bartosz Nowaczyk,

    Your message is awaiting moderation. Thank you for participating in the discussion.

    It's worth noting that there exists a hashing algorithm created specifically to be used in hash tables AND to prevent hash flooding attacks: It's already used in some well-known and widely-used projects (more in the wikipedia article).

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p