org.getopt.util.hash
Class FNV1

java.lang.Object
  org.getopt.util.hash.FNV1

Direct Known Subclasses:

FNV132, FNV164, FNV1a32, FNV1a64

public abstract class FNV1
extends java.lang.Object

A family of fast hash functions, originally created by Glenn Fowler, Phong Vo, and improved by Landon Curt Noll.

FNV1 hashes are designed to be fast while maintaining a low collision rate. The FNV1 speed allows one to quickly hash lots of data while maintaining a reasonable collision rate. The high dispersion of the FNV1 hashes makes them well suited for hashing nearly identical strings such as URLs, hostnames, filenames, text, IP addresses, etc.

FNV1a is a variant of FNV1, which is slightly better suited for hashing short values (< 4 octets).

This is a straightforward port of the public domain C version, written by Landon Curt Noll (one of the authors), available from his website.

The usage pattern is as follows: to compute the initial hash value you call one of the init(...) methods. After that you may update the hash zero or more times with additional values using the update(...) methods. When you are done, you can retrieve the final hash value with getHash().

Individual instances of FNV1 are reusable after you call one of the init(...) methods. However, these implementations are NOT synchronized, so proper care should be taken when using this hash in a multi-threaded environment.

Author:

Andrzej Bialecki <ab@getopt.org>

Field Summary

static long	FNV1_32_INIT Initial seed for 32-bit hashes.
static long	FNV1_64_INIT Initial seed for 64-bit hashes.
protected long	hash Current hash value.
protected long	INIT Current initial seed.

Constructor Summary

FNV1()

Method Summary

protected abstract long	fnv(byte[] buf, int offset, int len, long seed) Compute the hash value.
long	getHash() Retrieve the hash value
void	init(byte[] buf, int offset, int len) Initialize this hash instance.
void	init(java.lang.String s) Initialize this hash instance.
void	update(byte[] buf, int offset, int len) Update the hash value.
void	update(java.lang.String s) Update the hash value.

Methods inherited from class java.lang.Object

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

Field Detail

FNV1_32_INIT

public static final long FNV1_32_INIT

Initial seed for 32-bit hashes.

See Also:

Constant Field Values

FNV1_64_INIT

public static final long FNV1_64_INIT

Initial seed for 64-bit hashes.

See Also:

Constant Field Values

INIT

protected long INIT

Current initial seed.

hash

protected long hash

Current hash value.

Constructor Detail

FNV1

public FNV1()

Method Detail

init

public void init(java.lang.String s)

Initialize this hash instance. Any previous state is reset, and the new hash value is computed.

Parameters:

s - the method String.getBytes(java.lang.String) is called on this argument, with the UTF-8 encoding (or with the default encoding if that fails), and the hash is computed from the resulting byte array; cannot be null.

init

public void init(byte[] buf,
                 int offset,
                 int len)

Initialize this hash instance. Any previous state is reset, and the new hash value is computed.

Parameters:

buf - byte buffer from which to compute the hash

offset - starting position in the buffer

len - number of bytes after the starting position

update

public void update(java.lang.String s)

Update the hash value. Repeated calls to this method update the hash value accordingly, and they are equivalent to calling the init(...) method once with a concatenated value of all parameters.

Parameters:

s - see (@link #init(String)}

update

public void update(byte[] buf,
                   int offset,
                   int len)

Update the hash value. Repeated calls to this method update the hash value accordingly, and they are equivalent to calling the init(...) method once with a concatenated value of all parameters.

Parameters:

buf - byte buffer from which to compute the hash

offset - starting position in the buffer

len - number of bytes after the starting position

getHash

public long getHash()

Retrieve the hash value

Returns:

hash value

fnv

protected abstract long fnv(byte[] buf,
                            int offset,
                            int len,
                            long seed)

Compute the hash value.

Parameters:

buf - byte buffer from which to compute the hash

offset - starting position in the buffer

len - number of bytes after the starting position

seed - initial seed (or previous hash value)

Returns:

the next hash value