BT
x Your opinion matters! Please fill in the InfoQ Survey about your reading habits!

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

by Sergio De Simone on Apr 04, 2014 |

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.

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

Educational Content

General Feedback
Bugs
Advertising
Editorial
InfoQ.com and all content copyright © 2006-2014 C4Media Inc. InfoQ.com hosted at Contegix, the best ISP we've ever worked with.
Privacy policy
BT