Tablas hash

Clases
class	Aleph::DynLhashTable< Key, Record, Cmp >
class	Aleph::DynHashTable< Key, Cmp, HashTable >
class	Aleph::Hash_Cache< Key, Data, Cmp >
class	Aleph::Hash_Cache< Key, Data, Cmp >::Cache_Entry
class	Aleph::GenLhashTable< Key, BucketType, Cmp >
class	Aleph::GenLhashTable< Key, BucketType, Cmp >::Iterator
class	Aleph::LhashBucket< Key >
class	Aleph::LhashBucketVtl< Key >
class	Aleph::LhashTable< Key, Cmp >
class	Aleph::LhashTableVtl< Key, Cmp >
class	Aleph::LinHashBucket< Key >
class	Aleph::LinHashBucketVtl< Key >
class	Aleph::GenLinearHashTable< Key, BucketType, Cmp >
struct	Aleph::LinearHashTable< Key, Cmp >
struct	Aleph::LinearHashTableVtl< Key, Cmp >
class	Aleph::ODhashTable< Key, Cmp >
class	Aleph::OLhashTable< Key, Cmp >

Funciones
size_t	Aleph::xor_hash (void *key, size_t len)
size_t	Aleph::rot_hash (void *key, size_t len)
size_t	Aleph::djb_hash (void *key, size_t len)
size_t	Aleph::sax_hash (void *key, size_t len)
size_t	Aleph::fnv_hash (void *key, size_t len)
size_t	Aleph::oat_hash (void *key, size_t len)
size_t	Aleph::jsw_hash (void *key, size_t len)
size_t	Aleph::elf_hash (void *key, size_t len)
size_t	Aleph::jen_hash (void *key, size_t length, unsigned initval=Default_Hash_Seed)
size_t	Aleph::SuperFastHash (void *key, size_t len)

Variables
const unsigned	Aleph::Default_Hash_Seed

Descripción detallada

Tablas hash

Aleph define la mayoría de tipos de tablas hash existentes para guardar claves en memoria principal.

Hay tres grupo de tablas hash:

1. Con resolución de colisiones por encadenamiento separado (enfoque tradicional)

   Ver también

   LhashTable LhashTableVtl

2. Con resolución de colisiones por encadenamiento separado y crecimiento dinámico y lineal

   Ver también

   GenLinearHashTable

3. Resolución de colisiones cerrada (open addressing)

   Ver también

   OLhashTable ODhashTable

   Todas las tablas con resolución de colisión por encadenamiento separado manejan "cubetas"; es decir, su objeto de operación es la cubeta contentiva de la clave junto con cualquier información asociada. Este enfoque, aunque muy versatil, es más engorroso que un simple contenedor. Sin embargo todas las clases que manejan cubetas tienen una derivación que maneja directamente un conjunto dinámico.

   Ver también

   DynLhashTable LinearHashTable LinearHashTableVtl

   Autor

   Leandro Rabindranath León (lrleon en ula punto ve)

Documentación de las funciones

size_t Aleph::djb_hash ( void *  key, size_t  len  )

inline

Modified Bernstein hash

"Dan Bernstein created this algorithm and posted it in a newsgroup. It is known by many as the Chris Torek hash because Chris went a long way toward popularizing it. Since then it has been used successfully by many, but despite that the algorithm itself is not very sound when it comes to avalanche and permutation of the internal state. It has proven very good for small character keys, where it can outperform algorithms that result in a more random distribution"

"Bernstein's hash should be used with caution. It performs very well in practice, for no apparently known reasons (much like how the constant 33 does better than more logical constants for no apparent reason), but in theory it is not up to snuff. Always test this function with sample data for every application to ensure that it does not encounter a degenerate case and cause excessive collisions."

"A minor update to Bernstein's hash replaces addition with XOR for the combining step. This change does not appear to be well known or often used, the original algorithm is still recommended by nearly everyone, but the new algorithm typically results in a better distribution:"

Autor

Julienne Walker

size_t Aleph::elf_hash ( void *  key, size_t  len  )

inline

ELF hash

"The ELF hash function has been around for a while, and it is believed to be one of the better algorithms out there. In my experience, this is true, though ELF hash does not perform sufficiently better than most of the other algorithms presented in this tutorial to justify its slightly more complicated implementation. It should be on your list of first functions to test in a new lookup implementation"

Autor

Julienne Walker

size_t Aleph::fnv_hash ( void *  key, size_t  len  )

inline

Autor

Julienne Walker

size_t Aleph::jen_hash ( void *  key, size_t  length, unsigned  initval = Default_Hash_Seed  )

inline

Jenkins hash

"The dreaded Jenkins hash has been thoroughly tested and passes all kinds of tests for avalanche and permutations. As such it is considered to be one of the best and most thoroughly analyzed algorithms on the market presently. Unfortunately, it is also ridiculously complicated compared to the other hashes examined in this tutorial"

Autor

Julienne Walker

size_t Aleph::jsw_hash	(	void *	key,
		size_t	len
	)

JSW hash (Julienne Walker)

"This is a hash of my own devising that combines a rotating hash with a table of randomly generated numbers. The algorithm walks through each byte of the input, and uses it as an index into a table of random integers generated by a good random number generator. The internal state is rotated to mix it up a bit, then XORed with the random number from the table. The result is a uniform distribution if the random numbers are uniform. The size of the table should match the values in a byte. For example, if a byte is eight bits then the table would hold 256 random numbers"

Autor

Julienne Walker

size_t Aleph::oat_hash ( void *  key, size_t  len  )

inline

One-at-a-Time hash

"The FNV hash, short for Fowler/Noll/Vo in honor of the creators, is a very powerful algorithm that, not surprisingly, follows the same lines as Bernstein's modified hash with carefully chosen constants. This algorithm has been used in many applications with wonderful results, and for its simplicity, the FNV hash should be one of the first hashes tried in an application. It is also recommended that the FNV website be visited for useful descriptions of how to modify the algorithm for various uses."

Autor

Julienne Walker

size_t Aleph::rot_hash ( void *  key, size_t  len  )

inline

Rotating hash

"The rotating hash is identical to the XOR hash except instead of simply folding each byte of the input into the internal state, it also performs a fold of the internal state before combining it with the each byte of the input. This extra mixing step is enough to give the rotating hash a much better distribution. Much of the time, the rotating hash is sufficient, and can be considered the minimal acceptable algorithm. Notice that with each improvement, the internal state is being mixed up more and more. This is a key element in a good hash function"

Autor

Julienne Walker

size_t Aleph::sax_hash ( void *  key, size_t  len  )

inline

Shift-Add-XOR hash

"The shift-add-XOR hash was designed as a string hashing function, but because it is so effective, it works for any data as well with similar efficiency. The algorithm is surprisingly similar to the rotating hash except a different choice of constants for the rotation is used, and addition is a preferred operation for mixing. All in all, this is a surprisingly powerful and flexible hash. Like many effective hashes, it will fail tests for avalanche, but that does not seem to affect its performance in practice."

Autor

Julienne Walker

size_t Aleph::SuperFastHash	(	void *	key,
		size_t	len
	)

Paul Hsieh super fast hash function.

Autor

Paul Hsieh

size_t Aleph::xor_hash ( void *  key, size_t  len  )

inline

XOR hash

"The XOR hash is another algorithm commonly suggested by textbooks. Instead of adding together the bytes of an object as the additive hash does, the XOR hash repeatedly folds the bytes together to produce a seemingly random hash value"

Autor

Julienne Walker

Documentación de las variables

const unsigned Aleph::Default_Hash_Seed

Additive hash

"Probably the simplest algorithm for hashing a sequence of integral values (such as a string), is to add all of the characters together and then force the range into something suitable for lookup with the remainder of division. I will give an example of this algorithm only because books commonly suggest it in their rush to get past the topic of hash functions on their way to collision resolution methods. This algorithm is very bad"

Autor

Julienne Walker