

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object Hash
public class Hash
Fast, well distributed, crossplatform hash functions.
Development background: I was surprised to discovered that there isn't a good crossplatform hash function defined for strings. MD5, SHA, FVN, etc, all define hash functions over bytes, meaning that it's underspecified for strings.
So I set out to create a standard 32 bit string hash that would be well defined for implementation in all languages, have very high performance, and have very good hash properties such as distribution. After evaluating all the options, I settled on using Bob Jenkins' lookup3 as a base. It's a well studied and very fast hash function, and the hashword variant can work with 32 bits at a time (perfect for hashing unicode code points). It's also even faster on the latest JVMs which can translate pairs of shifts into native rotate instructions.
The only problem with using lookup3 hashword is that it includes a length in the initial value. This would suck some performance out since directly hashing a UTF8 or UTF16 string (Java) would require a prescan to get the actual number of unicode code points. The solution was to simply remove the length factor, which is equivalent to biasing initVal by (numCodePoints*4). This slightly modified lookup3 I define as lookup3ycs.
So the definition of the crossplatform string hash lookup3ycs is as follows:
The hash value of a character sequence (a string) is defined to be the hash of its unicode code points, according to lookup3 hashword, with the initval biased by (length*4).
So by definition
lookup3ycs(k,offset,length,initval) == lookup3(k,offset,length,initval(length*4)) AND lookup3ycs(k,offset,length,initval+(length*4)) == lookup3(k,offset,length,initval)
An obvious advantage of this relationship is that you can use lookup3 if you don't have an implementation of lookup3ycs.
Constructor Summary  

Hash()

Method Summary  

static int 
lookup3(int[] k,
int offset,
int length,
int initval)
A Java implementation of hashword from lookup3.c by Bob Jenkins (original source). 
static int 
lookup3ycs(java.lang.CharSequence s,
int start,
int end,
int initval)
The hash value of a character sequence is defined to be the hash of it's unicode code points, according to lookup3ycs(int[] k, int offset, int length, int initval) 
static int 
lookup3ycs(int[] k,
int offset,
int length,
int initval)
Identical to lookup3, except initval is biased by (length<<2). 
static long 
lookup3ycs64(java.lang.CharSequence s,
int start,
int end,
long initval)
This is the 64 bit version of lookup3ycs, corresponding to Bob Jenkin's lookup3 hashlittle2 with initval biased by (numCodePoints<<2). 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Constructor Detail 

public Hash()
Method Detail 

public static int lookup3(int[] k, int offset, int length, int initval)
k
 the key to hashoffset
 offset of the start of the keylength
 length of the keyinitval
 initial value to fold into the hash
public static int lookup3ycs(int[] k, int offset, int length, int initval)
lookup3ycs(k,offset,length,initval) == lookup3(k,offset,length,initval(length<<2))
and
lookup3ycs(k,offset,length,initval+(length<<2)) == lookup3(k,offset,length,initval)
public static int lookup3ycs(java.lang.CharSequence s, int start, int end, int initval)
The hash value of a character sequence is defined to be the hash of
it's unicode code points, according to lookup3ycs(int[] k, int offset, int length, int initval)
If you know the number of code points in the CharSequence
, you can
generate the same hash as the original lookup3
via lookup3ycs(s, start, end, initval+(numCodePoints<<2))
public static long lookup3ycs64(java.lang.CharSequence s, int start, int end, long initval)
This is the 64 bit version of lookup3ycs, corresponding to Bob Jenkin's lookup3 hashlittle2 with initval biased by (numCodePoints<<2). It is equivalent to lookup3ycs in that if the high bits of initval==0, then the low bits of the result will be the same as lookup3ycs.


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 