Take the 2-minute tour ×

Which hashing algorithm is best for uniqueness and speed? Example (good) uses include hash dictionaries.

I know there are things like SHA-256 and such, but these algorithms are designed to be secure, which usually means they are slower than algorithms that are less unique. I want a hash algorithm designed to be fast, yet remain fairly unique to avoid collisions.

share|improve this question
For what purpose, security or other? –  Orbling Feb 19 '11 at 0:05
@Orbling, for implementation of a hash dictionary. So collisions should be kept to a minimal, but it has no security purpose at all. –  Earlz Feb 19 '11 at 0:06
Note that you will need to expect at least some collisions in your hash table, otherwise the table will need to be enormous to be able to handle even a relatively small number of keys... –  Dean Harding Feb 19 '11 at 1:14
You're wrong; crypto algorithms are designed to be as fast as possible while still remaining secure. –  zvrba Aug 4 '11 at 10:46
Great post! Could you also check's Yann Collet's xxHash (creator or LZ4), which is twice as fast as Murmur? Homepage: code.google.com/p/xxhash More info: fastcompression.blogspot.fr/2012/04/… –  user55191 May 29 '12 at 12:35
show 16 more comments

8 Answers

up vote 970 down vote accepted

I tested some different algorithms, measuring speed and number of collisions.

I used three different key sets:

For each corpus, the number of collisions and the average time spent hashing was recorded.

I tested:


Each result contains the average hash time, and the number of collisions

Hash           Lowercase      Random UUID  Numbers 
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis*
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis***
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis***
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
SuperFastHash     164 ns      344 ns         118 ns
                   85 collis    4 collis   18742 collis
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis
LoseLose          338 ns        -             -
               215178 collis


Collisions actually happen?

Yes. I started writing my test program to see if hash collisions actually happen - and are not just a theoretical construct. They do indeed happen:

FNV-1 collisions

  • creamwove collides with quists

FNV-1a collisions

  • costarring collides with liquid
  • declinate collides with macallums
  • altarage collides with zinke
  • altarages collides with zinkes

Murmur2 collisions

  • cataract collides with periti
  • roquette collides with skivie
  • shawl collides with stormbound
  • dowlases collides with tramontane
  • cricketings collides with twanger
  • longans collides with whigs

DJB2 collision

  • hetairas collides with mentioner
  • heliotropes collides with neurospora
  • depravement collides with serafins
  • stylist collides with subgenera
  • joyful collides with synaphea
  • redescribed collides with urites
  • dram collides with vivency

DJB2a collions

  • haggadot collides with loathsomenesses
  • adorablenesses collides with rentability
  • playwright collides with snush
  • playwrighting collides with snushing
  • treponematoses collides with waterbeds

CRC32 collisions

  • codding collides with gnu
  • exhibiters collides with schlager

SuperFastHash collisions

  • dahabiah collides with drapability
  • encharm collides with enclave
  • grahams collides with gramary
  • ...snip 79 collisions...
  • night collides with vigil
  • nights collides with vigils
  • finks collides with vinic


The other subjective measure is how randomly distributed the hashes are. Mapping the resulting HashTables shows how evenly the data is distributed. All the hash functions show good distribution when mapping the table linearly:

enter image description here

Or as a Hilbert Map (XKCD is always relevant):

enter image description here

Except when hashing number strings ("1", "2", ..., "216553") (e.g. zip codes), where patterns begin to emerge in most of the hashing algorithms:


enter image description here


enter image description here


enter image description here

All except FNV-1a, which still look plenty random to me:

enter image description here

In fact, Murmur2 seems to have even better randomness with Numbers than FNV-1a:

enter image description here

When i look at the FNV-1a "number" map, i think i see subtle vertical patterns. With Murmur i see no patterns at all. What do you think?

The extra * in the above table denotes how bad the randomness is. With FNV-1a being the best, and DJB2x being the worst:

        FNV-1: *
         DJB2: **
        DJB2a: **
         SDBM: ***

I originally wrote this program to decide if I even had to worry about collisions: I do.

And then it turned into making sure that the hash functions were sufficiently random.

FNV-1a algorithm

The FNV1 hash comes in variants that return 32, 64, 128, 256, 512 and 1024 bit hashes.

The FNV-1a algorithm is:

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

Where the constants FNV_offset_basis and FNV_prime depend on the return hash size you want:

Hash Size    Prime                       Offset
32-bit       16777619                    2166136261
64-bit       1099511628211               14695981039346656037
128-bit      309485009821345068724781371 144066263297769815596495629667062367629
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

See the main FNV page for details.

As a practical matter:

  • 32-bit UInt32,
  • 64-bit UInt64, and
  • 128-bit Guid can be useful

All my results are with the 32-bit variant.

FNV-1 better than FNV-1a?

No. FNV-1a is all around better. There was more collision with FNV-1a when using the english word corpus:

Hash    Word Collisions
FNV-1   1
FNV-1a  4

Now compare lowercase and uppercase:

Hash    lowercase word Collisions  UPPERCASE word collisions
FNV-1   1                          9
FNV-1a  4                          11

In this case FNV-1a isn't "400%" worse than FN-1, only 20% worse.

I think the more important takeaway is that there's two classes of algorithms when it comes to collisions:

  • collisions rare: FNV-1, FNV-1a, DJB2, DJB2a, SDBM
  • collisions common: SuperFastHash, Loselose

And then there's the how evenly distributed the hashes are:

  • outstanding distribution: Murmur2, FNV-1a, SuperFastHas
  • excellent distribution: FNV-1
  • good distribution: SDBM, DJB2, DJB2a
  • horrible distribution: Loselose


Murmur? Sure, why not


@whatshisname wondered how a CRC32 would perform, added numbers to the table.

CRC32 is pretty good. Few collisions, but slower, and the overhead of a 1k lookup table.

snip all erroneous stuff about CRC distribution - my bad

Up until today I was going to use FNV-1a as my de facto hash-table hashing algorithm. But now I'm switching to Murmur2:

  • Faster
  • Better randomnessification of all classes of input

And I really, really hope there's something wrong with the SuperFastHash algorithm i found; it's too bad to be as popular as it is.

Update: From the MurmurHash3 homepage on Google:

(1) - SuperFastHash has very poor collision properties, which have been documented elsewhere.

So I guess it's not just me.

Update: I realized why Murmur is faster than the others. MurmurHash2 operates on 4 bytes at a time. Most algorithms are byte by byte:

for each octet in Key

This means that as keys get longer Murmur gets its chance to shine.


GUIDs are designed to be unique, not random

A timely post by Raymond Chen reiterates the fact that "random" guids are not meant to be used for their randomness. They, or a subset of them, are unsuitable as a hash key:

Even the Version 4 GUID algorithm is not guaranteed to be unpredictable, because the algorithm does not specify the quality of the random number generator. The Wikipedia article for GUID contains primary research which suggests that future and previous GUIDs can be predicted based on knowledge of the random number generator state, since the generator is not cryptographically strong.

Randomess is not the same as collision avoidance; which is why it would be a mistake to try to invent your own "hashing" algorithm by taking some subset of a "random" guid:

int HashKeyFromGuid(Guid type4uuid)
   //A "4" is put somewhere in the guid. 
   //i can't remember exactly where, but it doesn't matter for 
   //the illustrative purposes of this pseudocode
   int guidVersion = ((type4uuid.D3 & 0x0f00) >> 8);
   Assert(guidVersion == 4);

   return (int)GetFirstFourBytesOfGuid(type4uuid);

Note: Again, i put "random guid" in quotes because it's the "random" variant of guids. A more accurate description would be Type 4 uuid. But nobody knows what type 4, or types 1, 3 and 5 are. So it's just easier to call them "random" guids.

share|improve this answer
some of the collisions make awesome band names. Particularly 'Adorable Rentability' –  mcfinnigan Apr 23 '12 at 14:35
Also, I'd love to hear how you generated these results (source code and/or tools) –  Earlz Apr 23 '12 at 17:40
@Earlz Development tool is Delphi. i assume you mean the images though. For "linear" map i created a square bitmap of size nxn, (where n = Ceil(sqrt(hashTable.Capacity))). Rather than simply black for list entry is occupied and white for list entry is empty, i used an HSLtoRGB function, where the hue ranged from 0 (red) to 300 (magenta). White is still an "empty list cell". For the Hilbert map i had to hunt wikipedia for the algorithm that turns an index into an (x,y) coordinate. –  Ian Boyd Apr 23 '12 at 18:15
I've removed a number of comments that were along the lines of "+1 great answer!" - Please don't post comments that don't ask for clarifications or add information to the answer, if you feel it's a great answer, upvote it ;) –  Yannis Rizos Apr 28 '12 at 20:34
A new hash by the name of 'xxHash', by Yann Collet, was doing the rounds recently. I'm always suspicious of a new hash. It would be interesting to see it in your comparison, (if you aren't tired of people suggesting random hashes they've heard of to be added...) –  th_in_gs May 29 '12 at 11:51
show 51 more comments

Here is a list of hash functions, but the short version is:

If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. It has excellent distribution and speed on many different sets of keys and table sizes

unsigned long
hash(unsigned char *str)
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
share|improve this answer
add comment

If you are wanting to create a hash map from an unchanging dictionary, you might want to consider perfect hashing https://en.wikipedia.org/wiki/Perfect_hash_function - during the construction of the hash function and hash table, you can guarantee, for a given dataset, that there will be no collisions.

share|improve this answer
+1 I wasn't aware of such an algorithm –  Earlz May 25 '12 at 5:00
Here's more about (minimal) Perfect Hashing burtleburtle.net/bob/hash/perfect.html including performance data, although it doesn't use the most current processor etc. –  Feral Oink May 29 '12 at 12:24
It's pretty obvious, but worth pointing out that in order to guarantee no collisions, the keys would have to be the same size as the values, unless there are constraints on the values the algorithm can capitalize on. –  chaiguy Apr 4 '13 at 20:34
add comment

CityHash by Google is the algorithm you are looking for. It is not good for cryptography but is good for generating unique hashes.

Read the blog for more details and the code is available here.

CityHash is written in C++. There also is a plain C port.

About 32-bit support:

All the CityHash functions are tuned for 64-bit processors. That said, they will run (except for the new ones that use SSE4.2) in 32-bit code. They won't be very fast though. You may want to use Murmur or something else in 32-bit code.

share|improve this answer
Is CityHash pronounced similar to "City Sushi?" –  Eric Mar 20 '13 at 21:20
Have a look at SipHash too, it is meant to replace MurmurHash/CityHash/etc. : 131002.net/siphash –  Török Edwin Oct 15 '13 at 8:47
add comment

The SHA algorithms (including SHA-256) are designed to be fast.

In fact, their speed can be a problem sometimes. In particular, a common technique for storing a password-derived token is to run a standard fast hash algorithm 10,000 times (storing the hash of the hash of the hash of the hash of the ... password).

#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'

def run_random_digest(digest, count)
  v = SecureRandom.random_bytes(digest.block_length)
  count.times { v = digest.digest(v) }

Benchmark.bmbm do |x|
  x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }


   1.480000   0.000000   1.480000 (  1.391229)

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)
share|improve this answer
It's relatively fast, sure, for a cryptographic hashing algorithm. But the OP just wants to store values in a hashtable, and I don't think a cryptographic hash function is really appropriate for that. –  Dean Harding Feb 19 '11 at 1:10
The question brought up (tangentially, it now appears) the subject of the cryptographic hash functions. That's the bit I am responding to. –  yfeldblum Feb 22 '11 at 13:14
Just to put people off the idea of "In particular, a common technique for storing a password-derived token is to run a standard fast hash algorithm 10,000 times" -- while common, that's just plain stupid. There are algorithms designed for these scenarios, e.g., bcrypt. Use the right tools. –  TC1 Oct 14 '13 at 13:19
Cryptographic hashes are designed to have a high throughput, but that often means they have high setup, teardown, .rodata and/or state costs. When you want an algorithm for a hashtable, you usually have very short keys, and lots of them, but do not need the additional guarantees of a cryptographic has. I use a tweaked Jenkins’ one-at-a-time myself. –  mirabilos Dec 6 '13 at 13:57
add comment

It depends on data You are hashing. Some hashing works better specific data like text. Some hashing algorithms were specificaly designed to be good at specific data.

Paul Hsieh once made fast hash. He lists source code and explanations. But it was already beaten. :)

share|improve this answer
add comment

Java uses this simple multiply-and-add algorithm:

The hash code for a String object is computed as

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the i​-th character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

There are probably much better ones out there but this is fairly widespread and seems to be a good trade-off between speed and uniqueness.

share|improve this answer
I wouldn't use the exact same one used here, as it's still relatively easy to produce collisions with this. It's definitely not terrible, but there are much better ones out there. And if there's no significant reason to be compatible with Java, it should not be chosen. –  Joachim Sauer Apr 23 '12 at 12:51
add comment

First of all, why do you need to implement your own hashing? For most tasks you should get good results with data structures from a standard library, assuming there's an implementation available (unless you're just doing this for your own education).

As far as actual hashing algorithms go, my personal favorite is FNV. 1

Here's an example implementation of the 32-bit version in C:

unsigned long int FNV_hash(void* dataToHash, unsigned long int length)
  unsigned char* p = (unsigned char *) dataToHash;
  unsigned long int h = 2166136261UL;
  unsigned long int i;

    h = (h * 16777619) ^ p[i] ;

  return h;
share|improve this answer
The FNV-1a variant is slightly better with randomness. Swap the order of the * and ^: h = (h * 16777619) ^ p[i] ==> h = (h ^ p[i]) * 16777619 –  Ian Boyd Apr 23 '12 at 15:04
add comment

protected by ChrisF May 29 '12 at 12:38

