BT

Your opinion matters! Please fill in the InfoQ Survey!

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

| by Sergio De Simone Follow 6 Followers on Apr 04, 2014. Estimated reading time: 1 minute |

A note to our readers: As per your request we have developed a set of features that allow you to reduce the noise, while not losing sight of anything that is important. Get email and web notifications by choosing the topics you are interested in.

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

Adoption Stage
Style

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.

Tell us what you think

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

Email me replies to any of my messages in this thread

SipHash by Bartosz Nowaczyk

It's worth noting that there exists a hashing algorithm created specifically to be used in hash tables AND to prevent hash flooding attacks: en.wikipedia.org/wiki/SipHash. 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

Email me replies to any of my messages in this thread

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

Email me replies to any of my messages in this thread

1 Discuss

Login to InfoQ to interact with what matters most to you.


Recover your password...

Follow

Follow your favorite topics and editors

Quick overview of most important highlights in the industry and on the site.

Like

More signal, less noise

Build your own feed by choosing topics you want to read about and editors you want to hear from.

Notifications

Stay up-to-date

Set up your notifications and don't miss out on content that matters to you

BT