Aleph::GenLinearHashTable< Key, BucketType, Cmp > Class Template Reference

#include <tpl_linHash.H>

Inheritance diagram for Aleph::GenLinearHashTable< Key, BucketType, Cmp >:

Public Types
using	Hash_Fct = std::function< size_t(const Key &)>
using	Hash_Fct_Ptr = size_t(*)(const Key &)
using	Bucket = BucketType< Key >
	El tipo de cubeta.
using	Key_Type = Key
using	Item_Type = Key

Public Member Functions
void	set_hash_fct (Hash_Fct fct) noexcept
	Set the internal hash function.
void	set_hash_fct (Hash_Fct_Ptr fct) noexcept
Hash_Fct	get_hash_fct () const noexcept
Cmp &	get_compare () noexcept
const Cmp &	get_compare () const noexcept
float	current_alpha () const noexcept
	return the current table load
	GenLinearHashTable (size_t len=Primes::DefaultPrime, Hash_Fct_Ptr hash_fct=Aleph::dft_hash_fct< Key >, Cmp cmp=Cmp(), float lower_alpha=hash_default_lower_alpha, float upper_alpha=hash_default_upper_alpha, bool remove_all_buckets=true, bool with_resize=true)
void	swap (GenLinearHashTable &other) noexcept
void	empty () noexcept
Bucket *	search (const Key &key) const noexcept
const size_t &	size () const noexcept
	Retorna la cantidad de elementos que tiene la tabla.
bool	is_empty () const noexcept
	return true is table is empty
const size_t &	capacity () const noexcept
	Retorna el tamaño de la tabla.
const size_t &	busy_slots () const noexcept
	Retorna la cantidad de entradas vacía que tiene la tabla.
const size_t &	expansions () const noexcept
Bucket *	insert (Bucket *bucket)
Bucket *	search_or_insert (Bucket *bucket)
size_t	resize (size_t) noexcept
	Provided for generic programming compatibility.
Bucket *	remove (Bucket *bucket) noexcept
void	print ()
Stats	stats () const
void	print_stats (const Stats &stats) const
void	set_upper_alpha (const float &__upper_alpha)
void	set_lower_alpha (const float &__lower_alpha)
float	get_lower_alpha () const noexcept
float	get_upper_alpha () const noexcept

Protected Member Functions
	GenLinearHashTable (size_t __len, Hash_Fct __hash_fct, Cmp __cmp, float __lower_alpha, float __upper_alpha, bool __remove_all_buckets, bool)

Protected Attributes
Hash_Fct	hash_fct
Cmp	cmp
float	upper_alpha
float	lower_alpha
size_t	len

Friends
class	HashStats< GenLinearHashTable< Key, BucketType, Cmp > >

Detailed Description

template<typename Key, template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>
class Aleph::GenLinearHashTable< Key, BucketType, Cmp >

Tabla hash lineal genérica.

Básicamente, una tabla hash lineal es una tabla hash con resolución de colisiones por encadenamiento separado pero con la diferencia de que el tamaño de la tabla aumenta dinámicamente para asegurar que el factor de carga, típicamente llamado , esté delimitado entre dos valores inferior y superior, respectivamente.

Internamente, la tabla utiliza un arreglo dinámico del tipo DynArray. Esto conlleva ahorros de memoria por entradas de la tabla que no hayan sido escritas.

Este tipo es genérico y no está destinado a usarse. En su lugar, utilícese LinearHashTable o LinearHashTableVtl según se desee utilizar cubetas sin o con destructor virtual.

Parameters

Key	el tipo de clave por el cual se indiza la tabla.
BucketType	el tipo de cubeta entre LinHashBucket o LinHashBucketVtl.
Cmp	clase de comparación entre las claves.

See also

DynArray LinearHashTable LinearHashTableVtl

Member Typedef Documentation

Hash_Fct

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

using Aleph::GenLinearHashTable< Key, BucketType, Cmp >::Hash_Fct = std::function<size_t(const Key &)>

El tipo de función hash. Debe retornar valores positivos seudo aleatorios, entre cero y el número más grande posible.

Constructor & Destructor Documentation

GenLinearHashTable()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Aleph::GenLinearHashTable< Key, BucketType, Cmp >::GenLinearHashTable ( size_t  len = Primes::DefaultPrime, Hash_Fct_Ptr  hash_fct = Aleph::dft_hash_fct<Key>, Cmp  cmp = Cmp(), float  lower_alpha = hash_default_lower_alpha, float  upper_alpha = hash_default_upper_alpha, bool  remove_all_buckets = true, bool  with_resize = true  )

inline

Instancia una tabla hash lineal genérica.

Instancia una tabla hash lineal genérica de tamaño __len.

Parameters

[in]	__hash_fct	función hash.
[in]	__len	tamaño inicial y mínimo de la tabla.
[in]	__upper_alpha	umbral superior en que la tabla debe expandirse.
[in]	__lower_alpha	umbral inferior en que la tabla debe contraerse.
[in]	__remove_all_buckets	si es true, entonces se liberan las cuvetas de la tabla. De lo contrario, éstas permanecen intactas. Por omisión el valor es true.

Exceptions

length_error	si __ es igual a superior que la máxima dimensión permitida para un arreglo dinámico.
domain_error	si __upper_alpha es menor o igual a __lower_alpha.
bad_alloc	si no hay suficiente memoria
overflow_error	si ocurre un desborde desde DynArray (causado por sus cálculos internos).

Here is the call graph for this function:

Member Function Documentation

empty()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

void Aleph::GenLinearHashTable< Key, BucketType, Cmp >::empty ( )

inlinenoexcept

Vacía toda la tabla. Todas las cubetas son liberadas y el tamaño es ajustado al inicial.

expansions()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

const size_t& Aleph::GenLinearHashTable< Key, BucketType, Cmp >::expansions ( ) const

inlinenoexcept

Retorna el nivel de expansiones que se han realizado sobre la tabla.

insert()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket* Aleph::GenLinearHashTable< Key, BucketType, Cmp >::insert ( Bucket *  bucket )

inline

Insert bucket in the table. Return bucket if bucket->get_key() is not in the table, nullptr otherwise

Here is the call graph for this function:

remove()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket* Aleph::GenLinearHashTable< Key, BucketType, Cmp >::remove ( Bucket *  bucket )

inlinenoexcept

Elimina la cubeta bucket. Atención: no se verifica si la cubeta pertenece a la tabla.

Here is the call graph for this function:

search()

template<typename Key , template< class > class BucketType, class Cmp = Aleph::equal_to<Key>>

Bucket* Aleph::GenLinearHashTable< Key, BucketType, Cmp >::search ( const Key &  key ) const

inlinenoexcept

Busca la clave key en la tabla hash lineal. Retorna un puntero a la cubeta que contiene key si ésta se encuentra en la tabla; nullptr de lo contrario.

Here is the call graph for this function:

---

The documentation for this class was generated from the following file:

• tpl_linHash.H