1 #ifndef _hash_h 2 #define _hash_h 3 4 /* 5 ------------------------------------------------------------------------------- 6 lookup3.c, by Bob Jenkins, May 2006, Public Domain. 7 8 These are functions for producing 32-bit hashes for hash table lookup. 9 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 10 are externally useful functions. Routines to test the hash are included 11 if SELF_TEST is defined. You can use this free for any purpose. It's in 12 the public domain. It has no warranty. 13 14 You probably want to use hashlittle(). hashlittle() and hashbig() 15 hash byte arrays. hashlittle() is is faster than hashbig() on 16 little-endian machines. Intel and AMD are little-endian machines. 17 On second thought, you probably want hashlittle2(), which is identical to 18 hashlittle() except it returns two 32-bit hashes for the price of one. 19 You could implement hashbig2() if you wanted but I haven't bothered here. 20 21 If you want to find a hash of, say, exactly 7 integers, do 22 a = i1; b = i2; c = i3; 23 mix(a,b,c); 24 a += i4; b += i5; c += i6; 25 mix(a,b,c); 26 a += i7; 27 final(a,b,c); 28 then use c as the hash value. If you have a variable length array of 29 4-byte integers to hash, use hashword(). If you have a byte array (like 30 a character string), use hashlittle(). If you have several byte arrays, or 31 a mix of things, see the comments above hashlittle(). 32 33 Why is this so big? I read 12 bytes at a time into 3 4-byte integers, 34 then mix those integers. This is fast (you can do a lot more thorough 35 mixing with 12*3 instructions on 3 integers than you can with 3 instructions 36 on 1 byte), but shoehorning those bytes into integers efficiently is messy. 37 ------------------------------------------------------------------------------- 38 */ 39 40 #include <stdint.h> /* defines uint32_t etc */ 41 #include <sys/types.h> 42 43 /* 44 -------------------------------------------------------------------- 45 This works on all machines. To be useful, it requires 46 -- that the key be an array of uint32_t's, and 47 -- that the length be the number of uint32_t's in the key 48 49 The function hashword() is identical to hashlittle() on little-endian 50 machines, and identical to hashbig() on big-endian machines, 51 except that the length has to be measured in uint32_ts rather than in 52 bytes. hashlittle() is more complicated than hashword() only because 53 hashlittle() has to dance around fitting the key bytes into registers. 54 -------------------------------------------------------------------- 55 */ 56 uint32_t hashword( 57 const uint32_t *k, /* the key, an array of uint32_t values */ 58 size_t length, /* the length of the key, in uint32_ts */ 59 uint32_t initval); /* the previous hash, or an arbitrary value */ 60 61 /* 62 -------------------------------------------------------------------- 63 hashword2() -- same as hashword(), but take two seeds and return two 64 32-bit values. pc and pb must both be nonnull, and *pc and *pb must 65 both be initialized with seeds. If you pass in (*pb)==0, the output 66 (*pc) will be the same as the return value from hashword(). 67 -------------------------------------------------------------------- 68 */ 69 void hashword2 ( 70 const uint32_t *k, /* the key, an array of uint32_t values */ 71 size_t length, /* the length of the key, in uint32_ts */ 72 uint32_t *pc, /* IN: seed OUT: primary hash value */ 73 uint32_t *pb); /* IN: more seed OUT: secondary hash value */ 74 75 /* 76 ------------------------------------------------------------------------------- 77 hashlittle() -- hash a variable-length key into a 32-bit value 78 k : the key (the unaligned variable-length array of bytes) 79 length : the length of the key, counting by bytes 80 initval : can be any 4-byte value 81 Returns a 32-bit value. Every bit of the key affects every bit of 82 the return value. Two keys differing by one or two bits will have 83 totally different hash values. 84 85 The best hash table sizes are powers of 2. There is no need to do 86 mod a prime (mod is sooo slow!). If you need less than 32 bits, 87 use a bitmask. For example, if you need only 10 bits, do 88 h = (h & hashmask(10)); 89 In which case, the hash table should have hashsize(10) elements. 90 91 If you are hashing n strings (uint8_t **)k, do it like this: 92 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); 93 94 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this 95 code any way you wish, private, educational, or commercial. It's free. 96 97 Use for hash table lookup, or anything where one collision in 2^^32 is 98 acceptable. Do NOT use for cryptographic purposes. 99 ------------------------------------------------------------------------------- 100 */ 101 102 uint32_t hashlittle( const void *key, size_t length, uint32_t initval); 103 104 /* 105 * hashlittle2: return 2 32-bit hash values 106 * 107 * This is identical to hashlittle(), except it returns two 32-bit hash 108 * values instead of just one. This is good enough for hash table 109 * lookup with 2^^64 buckets, or if you want a second hash if you're not 110 * happy with the first, or if you want a probably-unique 64-bit ID for 111 * the key. *pc is better mixed than *pb, so use *pc first. If you want 112 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)". 113 */ 114 void hashlittle2( 115 const void *key, /* the key to hash */ 116 size_t length, /* length of the key */ 117 uint32_t *pc, /* IN: primary initval, OUT: primary hash */ 118 uint32_t *pb); /* IN: secondary initval, OUT: secondary hash */ 119 120 /* 121 * hashbig(): 122 * This is the same as hashword() on big-endian machines. It is different 123 * from hashlittle() on all machines. hashbig() takes advantage of 124 * big-endian byte ordering. 125 */ 126 uint32_t hashbig( const void *key, size_t length, uint32_t initval); 127 128 129 #endif 130