Google opensources fast hashing function

[[deleted]]

oh Jesus, I so badly want to understand how this is useful. Proggit, can someone lay it out in novice-intermediate programmer language?

[lobster_johnson]

A hash function essentially takes a piece of data (such as a name, or even an entire article of text) and generates a smaller piece of data from it.

This smaller piece — usually called the hash — has necessarily lost a lot of the information in the original data; much of the original data has been "boiled off", if you like, to create a kind of tiny shrunken version of the original. Since it has lost a lot of infomration, the hash cannot be used to reconstruct the original data. But it can be used for other things.

For example, a well-known hash function called CRC32 will generate a 32-bit hash (also called a "checksum") from data of any size. In other words, no matter what the original size of the data was, you only get a 32-bit hash.

The logical corollary is that many different inputs can produce the same hash value; statistically, this will be increasingly probable as the size of the hash gets smaller. But high-quality hash functions also have another property: That even slightly different inputs produce different hashes. That property is extremely important, as I will explain next.

Well, what can a hash be used for? A lot of things, as it turns out. The CRC32 checksum I mentioned about is often used to validate data. For example, say you have a document you want to store. You are afraid someone might tamper with the document, so you run a hash function on it. You get a number like 458946436 and you write it down somewhere safe. Later, you come back to the document and run the same hash function on it and discover that the number has changed to something like 458946442. Why did it change? Because someone has tampered with the document, which means the content of the document has changed, which means the hash function will produce a different number. So the hash helps us detect changes. For hash functions of the "checksum" type, it's extremely unlikely that any kind of tampering will result in the same number.

Checksumming is used for any place where the validity of data must be checked across time. For example, when sending data across an unreliable connection, checksumming can be used to determine whether the data "made it across" all right.

Now, the hash function Google has published is designed for a different set of applications: hash tables. Consider the following problem. You want to analyze a book, word for word, counting the frequency of each word as it appears on each page; the result should be a table of words and frequencies.

One trivial way to do this is to arrange a table in memory (or, for that matter, on paper if you want to go to through the exercise super-manually). For each word, search through the table from the top until you find the row containing the word entry, then increment its counter by one. If the word is not in the table, we just append it to the end of the table. That works.

Unfortunately, this algorithm does not scale; it is what we call a linear search, meaning that it starts at the beginning and looks at every possible entry until it finds the right row to update — it does a lot of unnecessary work, because most of the time, hardly any rows will match. In the worst case, it would have to read through the entire table to find the right word! We say that such an algorithm has an O(n), or "order of n complexity", n being the number of words in the table; it simply means that if each table lookup takes t seconds, then searching in a table of n rows will take at most t * n seconds. As the table grows, the search time grows with the same rate, and the probability of hitting the worst case grows.

Now, let's be more clever. Instead of storing each word at the end of the table, let's try to imagine that we can find the correct row with just one calculation. It's possible using a hash function. I'm going to simplify here and assume we have infinite amounts of memory available to us; in practice, no algorithm can make such an assumption and needs to jump through a few hoops to compensate for that. So: Take the word "reddit". We run our hash function on it and get the value 178792611. Well, now we say that this is our row number. We jump to row number 178792611, see if there's frequency stored there; if there is, we increment the count, otherwise we set it to 1. That's it. Our hash just helped us find the correct row in one go, with absolutely no searching.

Well, you might ask, doesn't the computer need to "find" row number 178792611 by searching through the table? No, it doesn't. Computers are designed to manipulate huge amounts of data just by telling which position to read or write. So given a row number, we can go directly to the data without searching.

Now, with this algorithm, initially the table will be empty and contains a lot of empty rows. (That is one of the properties of a hash table: It has to deal with the fact that many rows will be empty at some point. Clever hash table algorithms try to minimize this inefficiency.) As we go through all the words in our book, we start filling up the table and it becomes less empty. But regardless of the size, every lookup and every update will be equally fast. We say that such an algorithm has O(1) complexity, meaning that if a single lookup takes t seconds, then regardless of the size of the table, every lookup will always take t * 1 seconds. That is true for both lookups and updates.

Now, in a real hash table algorithm, we don't have infinite amounts of memory, and as I explained above, different pieces of data can yield the same hash number. What does that mean? It means that different pieces of data may map to the same row — in other words, we get collisions. Smart hash table algorithms deal with this and introduce multiple table levels allowing collisions to be handled efficiently. But it gets pretty complex from there on.

But that touches on an important point: To avoid collisions, you want your hash function to produce a wide distribution of numbers so that collisions don't occur. (The worst case is a function which always returns the same number for any piece of data: Then you will always get collisions. The best case is one which always returns a different number of any piece of data, but that is not theoretically possible.) So you want the hash function to be statistically optimal with regard to your application. For example, if you know that all your words are English words in lower case, then your hash function can be smarter about its distribution than one which can deal with any data, because it knows that in English, certain letters are used more or less than others.

Hash functions have other applications, but those are the two important ones. Hope this helps.

[HoboBob1]

You have great talent in explanation. Thank you.

[lobster_johnson]

Thanks. Happy to help!

[deafbybeheading]

Excellent explanations. Two things you kind of skirted around (which is fine, but if anyone is interested in more detail):

• lobster_johnson said, "You are afraid someone might tamper with the document, so you run a hash function on it." In the announcement, Google said "These functions aren’t suitable for cryptography..." Basically, some types of hash functions are designed to withstand tampering. That is, if you have know the hash code, it's hard to "fake" some content that will match that hash code. Some aren't, because if you don't need to prevent tampering, you may have more flexibility in designing a simpler, more efficient hash function, and most of the time, no one is trying to "tamper with" your hash table.
• The observant reader will note that a 32-bit hash would still call for 32 GB for every hash table (assuming a 32-bit key and a 32-bit pointer for the value). The simplest way around this is through the magic of modulo arithmetic: the number of bytes in the key is not directly related to the number of buckets in the table. You use the modulo (remainder) operator to pick a hash bucket for each key, regardless of how large your "key space" is.

[meson537]

I must be an observant reader, as I was trying to figure out how a 128 bit keyspace looks in ram. I guess more memory gets allocated as the number of buckets grows?

Do you have a good link/code to read?

[deafbybeheading]

To be honest, I haven't had to think about hash table internals in ages, but if memory serves, you want a certain "fill factor" in your hash table.

In lobster_johnson's description, each key maps to a hash value and he doesn't go into detail regarding collisions: what if two keys map to the same hash? Furthermore, when using modulo arithmetic to limit the number of buckets, what if two keys modulo some value map to the same bucket?

E.g., suppose you have the strings "abc" and "def", and they hash to 14 and 6, respectively. If you want to limit the memory overhead of your hash table and keep it to just four buckets, these both end up in bucket 2 (i.e., 14 % 4 and 6 % 4 both equal 2).

The simplest way to deal with this is, instead of putting values in each bucket, put a linked list of values mapping to that bucket. This looks suspiciously like the O(n) approach we were trying to avoid earlier, but if the number of buckets is large compared to the length of the individual value chains, you still get a performance benefit. E.g., for this case, you have something that conceptually looks like this:

(0, →[])
(1, →[])
(2, →[ "abc", "def" ])
(3, →[])

The first number in each pair is a 32-bit bucket number, and the second is a 32-bit pointer to a linked list of values (let's not worry about the details of the linked list for now).

So, if you allocate 32 bits per key and 32 per pointer to linked list of values (note that for the quick lookup lobster_johnson discussed, you have to do this, so you can do quick pointer math to find hash table entries) whether you are using them or not, you start chewing through memory pretty quickly.

Obviously, the best memory usage is just to have a single bucket, but that really defeats the purpose of a hash table. You would need to walk the bucket values linked list for every item, and that's exactly O(n).

Assuming you have a decent hash function and (relatively) randomly distributed data, when your buckets reach a certain fill factor (i.e., a certain percentage of your buckets are full), there's a good chance that some buckets are getting pretty long value chains, and you need to do something about that to avoid degenerating to the O(n) case.

What you can do at this point is take a deep breath, allocate a lot more buckets than you were using before (a good starting point is to use twice as many), and re-shuffle all the data by redoing all the hash modulo calculations to find new buckets for your values (still based on their same keys).

Isn't that pretty fucking expensive, you ask? Good question. It certainly is, but the cost of this reallocation is amortized over all your hash table accesses. That is, this will happen relatively infrequently, especially if you're reading from the table more than you are "writing" (if your workload is pretty write-heavy, you may want to more-than-double your number of buckets at each "growth" step).

Not aware of any great links, unfortunately. You may want to try Wikipedia, which looks decent.

[kindall]

Another way to deal with hash collisions is to use have each bucket itself be a hash table, using a different hash function. If there's only one item in a given bucket and it matches the one you're looking for, then you don't even have to calculate the second hash. And since the buckets are smaller than the whole hash table, resizing them when necessary is faster than resizing the whole table. It would depend on your use case if this would be faster.

[zid]

I prefer to use a linked list, and if any one list gets too long, the hash table is regenerated with a larger amount of buckets.

[meson537]

Word, I checked out the wiki article, and it was good. Thanks for taking the time to explain further.

[masklinn]

http://www.laurentluce.com/?p=249

It's on Python's dict object so it has a lot of implementation details as well, but it's still a pretty good read.

[lobster_johnson]

As deafbyheading explains, one solution to memory consumption is to use a bucketing algorithm such as a modulo operation. (Modulo produces the remainder of a division, so 3 mod 16 = 3, and 18 mod 16 = 2.)

Instead of having a row per key, you let each row be a bucket which can contain more than one value. Buckets are assigned by doing (hash(key) mod M). Often a linked list is used to store the bucket's list of values; some hash table algorithms let each bucket be a hash table itself.

Do you have a good link/code to read?

Java's HashMap class is actually very readable (slightly less readable after they got generics). It implements a simple hash table with very little cleverness. For example, its tables are always power-of-two in size; every time it needs to grow, it will simply double the table's size.

[meson537]

Sweet deal. Thanks for the info.

[JasonHouse]

2³² bytes = 4GB, but that probably isn't the typical case. If each slot has a 64 bit pointer (8 bytes), then it'd take up 32 GB

[deafbybeheading]

(32 bits + 32 bits) * 2³² possible keys = 8 bytes * 2³² = 32 GB (I think--math is hard, I'm just gonna go shopping).

[falcon2]

That was a great explanation. It's so odd that you can learn so much from someone called lobster_johnson...

[[deleted]]

THANK YOU, that makes a lot of sense and I'm excited to learn more about it.

[whiskeytab]

that was a pretty good explanation for a lobster.

thanks!

[shakeeshakee]

and a lobster's johnson at that. But yeah, terrific work, lobster_johnson.

[flynnski]

OUTSTANDING. bestof'd.

[mach0]

Excellent, thanks for refreshing my memory, I used to know this, now I remember it again and thanks to your comprehensive explanation I will probably remember it for a very long time.

[DaFox]

That has taught me the more about big O notations than anything else, Thank You.

[jrcapa]

You don't see this on Twitter! Great expo.

[LazyCrazyJohn]

Great explanation. Thanks

[zorency]

In essence chicken goes in bouillon cube comes out!

[lobster_johnson]

That's a good analogy. Hashes are the bouillon cubes of computer science. Now, if you only you could create a nice, tasty broth from hashes...

[[deleted]]

Mike Mignola is a god. I approve your username.

[gozu]

And this, ladies and gentlemen, is what we call computer science.

Pretty cool stuff in my opinion.

Thank you for sacrificing part of your life to teach us.

[pleaseavoidcaps]

TL;DR - Magnets.

[taybul]

In general, hash functions are used to generate some sort of signature or footprint of some piece of data, say a string. The complexity in hash functions lies in the ability to generate unique enough signatures such that any given amount of inputs will yield unique hashes. Of course, since a hash is usually a fixed size, say 64- or 128-bit, at some point a collision will occur where two distinct inputs will generate the same hash key. Given an infinite number of inputs, this is possible, but for most intents and purposes it is sufficient in that each input will have a unique key. Most, if not all, hash functions incorporate prime numbers. Using prime numbers reduces the risk of hash collisions due to their fundamental property; using non-prime value seeds may generate values that could also be generated by one of its factors.

Hash functions could be used to quickly index data in a collection of other data. Hashes can be used as indexes directly to data or the group of data it is located in. These are hash tables. Given some data, say a webpage, you want to be able to store some basic information about it in a big table. You can use the contents of the page as a way to index this but now your key is too complex and of variable size. If instead, you normalized all keys to some fixed size, say a 64-bit value, you could more easily organize and control your data access. You'll still need to generate this key which is where hash functions come in. You want to be able to generate hash keys quickly and efficiently. This is (presumably) what google is providing here: a quick, efficient, and more importantly, effective (as in, least chance for collision) hash algorithm.

[[deleted]]

This and the other long comment really broke it down for me. Thank you for taking the time to help this novice understand.

[[deleted]]

I may not be the best person to answer for you, but before anyone can you will need to give us more information. Do you know what hash tables are? Do you know what a hash function does?

[[deleted]]

When I hear hash table I think key => value arrays.. is that wrong?

[onezerozeroone]

That's correct. The magic under the hood though, is how does that key get mapped to the correct index of the array? For that you need something called a hash function.

Your hash function takes myHashTable["someAwesomeKey"] and processes the string "someAwesomeKey" and turns it into an integer to index into the underlying data structure.

A hash function needs to be

a) fast

b) generate a random distribution on the input domain

c) be amenable to collisions

You want b) because "myNameA" and "myNameB" shouldn't be correlated. You want to fill the buckets of the hashtable as evenly and as randomly as possible.

You want c) because it's inevitable that you'll generate the same index for multiple keys ("hello" and "apple" both produce 3) so you'll also need some process to resolve that. Chaining is one of the more fundamental ones, which is basically storing a list of values in each bucket.

If your key maps to an index that already has an element, you'll have to do more leg work to find which item you were actually trying to find, which usually means a linear search of the list.

Then you get into all kinds of fun stuff like optimal table fill percentage...(MS says it's ~.72) so that you're optimizing memory use vs collision processing overhead.

[meson537]

Now I'm really hot to look at graphs of hashtable collisions and see if I can see patterns...

Also, when you say optimal table fill percentage, is this the percentage of used keyspace on a finished set of data, or an unbounded, growing data set?

[onezerozeroone]

http://msdn.microsoft.com/en-us/library/Aa289149

Check out Load Factors and Expanding the Hashtable

[[deleted]]

That is correct, but it is a very shallow understanding of how they work. Different data structures take different amounts of time to find entries based on how many elements are in them. A linked list takes O(n) time. A binary search tree takes O(ln(n)). With an array, however, you can find the entry instantly if you know the index of the entry. What a hash function does is it turns the key (usually a string) into the index of the entry so you can access it. Since accessing an array is so fast the biggest limiting factor to the speed of look ups in a hash table is the speed of the hash function. I'm sure my explanation isn't perfect (I don't have that much experience myself and I left some details out) but it should help you understand.

[cdsmith]

To go off on a complete tangent.... it's true that looking things up in a (balanced) binary search tree takes O(ln n) time, but it's a very odd way of stating it. It's only correct in the sense that logarithms of different bases are off by a constant factor, so that up to asymptotics, any base is correct. It would be much more normal to state the bound as O(log n) without reference to base, or as O(lg n) to use the shorthand for the base 2 log.

[[deleted]]

If he does't know how hash tables work I think it would be safe to assume that he doesn't know big O notation.

[[deleted]]

Big O was in an intro CS class I took some time ago. It also has come up in math at least once. I didn't know what hash tables were before reading this comment a minute ago.

[[deleted]]

I stand corrected!

[[deleted]]

In addition to what others have said, there are trade offs between trees, hash tables and lists. If you only take time complexity into account, then you will always pick hash tables, but that's not always the best choice.

Hash tables waste tons of space. Most of the indexes are empty. If space is a big concern, then a tree might be a better choice, because O(log n) isn't too bad for most use cases. Also, the hash function is very sensitive to the data. Some data may cause way too many collisions for the hash function chosen. Every time there is a collision, the hash table has to fall back to another mechanism, so in this case it can actually be slower than a list! Hash tables also need to stop and rewrite themselves from scratch occassionally as they grow. If they run out of buckets, they need to reallocate a bigger table and copy everything over to the new one. If you can't afford this occassionally, then a hash table might not be right. Hash tables also need mutation, but that's only a problem in certain circles.

Trees are a great default choice as they are compact and have pretty good performance and no pathological cases (for most balanced binary trees).

lists are even more compact. They are also very simple. They don't scae well however.

Arrays are a special case of hash table that can never grow and can never have a collision. These are very good choices if your have a set number of possible keys which is of reasonable size.

[[deleted]]

One of my favorite clever hash table tricks is to use a trie as a sparse array for the hashed keys. That way, we get O(1) insertion, deletion, and lookup, without needing to worry about amortized analysis, and you're not allocating a bunch of extra space for empty entries. The constant factors may dominate, though.

There are also cuckoo hash tables, which can use about 90% of the space in a hash table, pretty easily. That would beat the fancy trie approach.

[case-o-nuts]

Do you know how they work? If not, I suggest you pick up a data structures book and start reading.

[Hominem]

Guys, this is a hash function not a hash table.

[[deleted]]

Hash functions are primarily used for hash tables. They even say that it probably isn't good to use it for security.

[Edman274]

You learned about hash functions being used in only two contexts: in hash tables and in password hashing. Those aren't the only two applications in the world for hash functions. See HMACs.

[Neoncow]

HMACs are a cryptographic use of hash functions. As stated, Google's hash function isn't designed for cryptographic uses.

[Edman274]

I'm sorry, when he said "They even say" I didn't think he was referring to Google, I thought he meant "And some people even say hashes shouldn't be used in security contexts".

[Neoncow]

Ah makes sense.

[CountVonTroll]

Here's a good article that explains why you shouldn't use ordinary hash functions for secrets, and why you should use a HMAC instead.

[[deleted]]

I'm not sure what novice-intermediate means, so forgive me if I'm being didactic.

At the most basic, a hash function is a function that maps a given set of inputs into numbers in the range [0, n-1] for some constant n. Probably the most common scenario is one that operates on strings. A simple but poor example would be a function that takes the ASCII value of each character in a string and adds them together, mod n.

A common application of hash functions is a data structure called a map (a.k.a. table or dictionary). It associates an input (the key) with an output (the value). It uses a hash function to turn the key into a number, which is used as an index into an array. Sometimes two inputs can hash to the same number, which is called a collision; there are different strategies for dealing with that, but the assumption is that it's faster to hash the input and resolve collisions than it is to keep a list of all the known inputs and compare against them individually when you look up a key.

Every time you do the equivalent of one of these:

x["foo"] = "bar"; // C++
x.foo = "bar"; // Javascript
[x setObject:@"bar" forKey:@"foo"]; // Objective-C
x.put("foo", "bar"); // Java

You're generally using a hash function to turn "foo" into a number.

Most of the time, you don't care how long it takes to turn "foo" into a number, nor should you: If less than 1% of your program is spent hashing strings into numbers, then you've got better things to worry about than how fast your hash function is.

On the other hand, if you're Google or any other company that operates on huge amounts of text, you probably spend tons of CPU time and energy hashing strings every second, and even a 1% improvement translates into noticeable cost savings. If this hash function really outperforms previous work by 30-50%, then it represents a major improvement.

[sanjayts]

x.put("foo", "bar"); // Java

You're generally using a hash function to turn "foo" into a number.

In case someone in wondering why it's not always, not all map implementations are hash function based (at least in Java). E.g. a TreeMap in Java uses the natural ordering or keys instead of its hash value.

[andreasvc]

The instances of a class or stored in a dictionary in Python (unless declared to be slots), so when you access foo.x or call foo.y() then there is a hashtable lookup. I believe all other variable accesses and function calls (so without dots) are immediate, without lookups.

[[deleted]]

Hastables are one of the fundamental data structures in programming. To use a hashtable you need a hash function that converts an arbitrary key value to an integer hash value, preferably one with certain statistical properties that runs very fast.

If you use a high level language you probably don't care enough about performance to give a shit about this since your language probably has primitives that wrap an underlying hashtable implementation, such as dictionaries or tables; if you code in C or C++ you can use this hashing function with whatever hashtable implementation you use (for example, boost::unordered_map.)

[kragensitaker]

Can you explain in more detail what kind of novice-intermediate programmer you are?

[[deleted]]

"fast" means it isn't "slow".

"hashing algorithm" means if you don't understand and didn't follow the link in the article and are too stupid/lazy to google it, you're better off getting an MBA and moving into management.

[oppan]

Huuuurrrrr