Source: http://thecoldsun.com/es/content/tipos-de-datos-tabla-hash
Timestamp: 2017-04-26 03:58:34+00:00

Document:
Delphi. Tipos de datos. Tabla Hash
Uso de memoria en Delphi (6,414) Tipos de datos. Tabla Hash (3,448) Introducción a .NET (2,647) Multihilo. Espacios de memoria, código reentrante y código threadsafe. (2,632) Programación multihilo en Delphi. TThread y sincronización básica (2,595) Medir el tiempo de ejecución de un fragmento de código (2,141) Obtener el tiempo de CPU de procesos y tareas (2,041) El mundo del runtime en delphi. (1,965) Delegados en Delphi. Pasando metodos y funciones como parametros. (1,788) Clases abstractas e interfaces (1,728) Sistema de plugins con C#. Parte I. Conceptos (1,618) Atributos en .NET. Leyendo los atributos con Reflection (1,608) Sistema de plugins con C#. Parte II. El código explicado (1,558) Sistema de Plugins con C# y .NET (1,549) Patrones de diseño. Facade Pattern (1,432) Patrones de diseño. Abstract Factory Pattern (1,392) Aplicaciones Multihilo en Delphi: Metodos de sincronización de Delphi (1,373) Test Driven Development (Desarrollo dirigido por las pruebas) (1,268) Aplicaciones Multihilo en Delphi. Primitivas de sincronización de Windows (1,254) Aplicaciones Multihilo en Delphi. Los problemas del multihilo (1,219) C# 3.0. Nuevas características II (1,212) Managed DirectX. Introducción y Tutorial I. (1,192) Patrones de diseño. Template Method (1,178) Distancia geodésica entre dos puntos (1,153) Singletons en Delphi (1,114) 1
Multihilo. Espacios de memoria, código reentrante y código threadsafe. (39,633) Tutorial de SQL. SELECT Parte II (28,573) Singletons en Delphi (17,678) Programación multihilo en Delphi. TThread y sincronización básica (16,453) Medir el tiempo de ejecución de un fragmento de código (16,044) Uso de memoria en Delphi (15,211) Patrones de diseño. Facade Pattern (14,591) Obtener el tiempo de CPU de procesos y tareas (14,306) Tipos de datos. Tabla Hash (14,157) Sistema de plugins con C#. Parte II. El código explicado (14,117) Delegados en Delphi. Pasando metodos y funciones como parametros. (13,657) Sistema de plugins con C#. Parte I. Conceptos (13,330) Patrones de diseño. Abstract Factory Pattern (12,567) Clases abstractas e interfaces (12,335) El mundo del runtime en delphi. (12,001) Check in early, check in offen (11,300) Atributos en .NET. Leyendo los atributos con Reflection (11,045) Patrones de diseño. Adapter Pattern (10,768) Aplicaciones Multihilo en Delphi. Primitivas de sincronización de Windows (10,481) Manejando el cambio desde el punto de vista de management. (10,285) Patrones de diseño. Template Method (10,147) C# 3.0. Nuevas características II (9,760) Managed DirectX. Introducción y Tutorial I. (9,532) Distancia geodésica entre dos puntos (9,397) Sistema de Plugins con C# y .NET (9,241) 1
Tipos de datos. Tabla Hash Table of Contents [hide]
Otras funciones de hash
Resolución con listas enlazadas
Una tabla hash completa
La función hash es la llave principal de una tabla hash, es la función que se encarga de asignar un identificador <em>único</em> a cada uno de los elementos que insertamos en la tabla. Se encarga de trazar un mapeo entre el identeficador del dato y su posición en la tabla.
Obviamente, puesto que el espacio posible de identificadores es potencialmente infinito y el espacio de memoria (el numero de posiciones del array) es, por definición, finito, existe la problemática de que varios elementos pueden 'colisionar' en una misma posición.
El funcionamiento normal de una tabla hash es:
Primero se calcula el hash (la posición del array en la que está guardado el elemento) del id proporcionado aplicando la función de hash
Una vez obtenida la posición del array se comprueba si hay una colisión (si ya hay un elemento en esa posición del array) y si la hay se resuelve.
Finalmente se escribe o se lee el valor en la tabla hash
El problema de asignar un numero a un identificador tiene varias soluciones, unas más rápidas que otras. El objetivo fundamental de una buena fución de hash es la aleatoriedad, es decir, que dados dos identificadores parecidos (cuyo cambio consista por ejemplo en el valor de un byte) obtengamos dos valores hash muy distanciados entre si. En gran parte de los casos, parte de la aleatoriedad puede conseguirse eligiendo los numeros a usar cuidadosamente (como por ejemplo en la función de Hash de Bernstain que es tan simple como h = 33 * h + p[i]; (siendo p la cadena que tiene la clave) y sin embargo produce unos buenos resultados de dispersión).
La forma más simple para obtener el hash de una determinada longitud dado un determinado tamaño consiste sencillamente en obtener un valor numérico del id (si el identificador no es numérico) y despues calcular el resto de la división por el tamaño de la tabla.
function SimpleHash(id : string; tableSize : integer) : integer;
// Obtener el valor numérico
result := result + Ord(id[i]);
// Ajustar al tamaño de la tabla
result := result mod tableSize;
El principal problema de esta función de hashing es que es poco aleatoria. Si tomamos el hash de 'aaa' y el hash de 'aba' observaremos que son relativamente cercanos (de hecho son correlativos) lo cual es una cualidad 'mala' en una función de hash ya que, por ejemplo si estamos insertando datos en la tabla den función de ids binarios no encontramos con una alto grado de colisiones ('0001', '0010', '0100' y '1000' por ejemplo tienen el mismo hash).
La función de hash ELF recibe su nombre de su utilización en los archivos objeto de Unix (Excetutable and Linking Format).
Básicamente la función es igual que la anterior pero añadiendo una cierta aleatoriedad en cada iteración del bucle.
function ElfHash(id : string; tableSize : integer) : integer;
h,x : longint;
h := (h shl 4) + Ord(id[i]);
x := h and $F0000000;
if x <;>; 0 then
h = h xor (x shr 24) xor x;
result := h mod tableSize;
Hay numerosas funciones de hash, yo fundamentalmente he usado la función ELF por ser una función que distribuye muy bien el espacio de claves en el espacio de memoria, con buenos resultados.
En cualquier caso es recomendable, si se observa que por las características del problema que estamos tratando nuestra función de hash produce un alto indice de colisiones es posible que necesitemos cambiarla. En la página The Art of Hashing hay una buena cantidad de funciones de hash (en ingles).
Como ya hemos dicho, por muy maravillosa que sea nuestra función de hash, puesto que el espacio de claves es potencialmente mucho mayor (como norma general) al espacio de hashing en algún momento nos encontraremos con que dos claves distintas producen el mismo hash. Esto significará que, en un determinado momento, al ir a introducir la información en nuestra tabla puede que ya haya un dato en esa posición o que al ir a recuperarla el dato de la posición que devuelve la tabla hash no tenga la clave correpondiente al elemento que deseamos recuperara. Al igual que existen varios metodos para hayar el hash dada una clave existen también distintos metodos para realizar la resolución de colisiones.
El metodo de resolución linear se basa en que, si una posición está ocupada, seguimos buscando una posición libre en base a algún desplazamiento (constante o dado por una función). A este tipo de resolución de colisiones se la considera englobada en el esquema abierto de direcciones (open addressing schemes).
La implementación más sencilla de este metodo es, al encontrar una posición ocupada, continuar recorriendo las posiciones siguientes hasta encontrar un hueco vacio.
procedure Write(id : string; data : Pointer);
pos, aux : integer;
// Obtener el hash
pos := hash(id);
// Guardar el hash original
aux := pos;
// Buscar un espacio libre por resolución linea ( pos++)
while Assigned(FData[pos]) do
if pos >; Lenght(FData) then
if pos = aux then
raise Exception.Create('Tabla hash llena');
CreateHashItem(FData[pos],id, data);
A la hora de realizar una busqueda el asunto es similar, miramos el primer hash y si no encontramos el elemento que buscamos en la posición avanzamos a la siguiente hasta encontrar el elemento en cuestión o un elemento vacio (fallo en la busqueda).
Cuando borramos un elemento de la lista sin embargo hay que tener cierto cuidado. No podemos sencillamente vaciar la posición que ocupaba el elemento sin más, imaginemos este caso:
23 'aba'
24 'aab'
25 'baa'
En el que todos los elementos hacen hash al 23, si eliminamos el elemento 'aab' y simplemente lo vaciamos
De forma que cuando realizamos una busqueda de 'baa' calculamos su hash, miramos el elemento 23 (fallo), pasamos al elemento 24 que está vacio y paramos la busqueda, sin haber encontrado el elemento que buscabamos y que realmente estaba ahí, asi que no podemos sencillamente 'vaciarlo' sino que deberemos introducir algún valor 'especial' que nos permita saber que ante una busqueda no debemos dejar de buscar.
La resolución lineal de colisiones tiene varias ventajas:
El uso de la tabla es constante, es decir, no se usa más memoria de la que inicialmente se asignó como tamaño inicial de la tabla (al contrario de lo que pasa con el metodo de lista enlazada)
El mecanismo es relativamente rápido si esperamos tan solo dos o como mucho tres colisiones
aunque tiene en mi opinión más desventajas que ventajas
El hecho de insertar elementos en posiciones que 'no son suyas' da lugar a que puedan producirse colisiones que no debería producirse.
Por ejemplo, si insertamos 'abb' y 'bba' que supongamos que corresponden al mismo hash (23) tendremos algo como esto más o menos
23 'abb'
24 'bba'
y después de ello insertamos el elemento 'bbb' que supongamos que corresponde al hash 24 obtendremos una colisión pese a que ningún otro elemento había obtenido el hash 24.
24 'baa'
25 'bbb'
Puesto que el espacio es límitado al encontrar una colisión podemos encontrarnos ante el caso de que la tabla se llene (lo cual no es necesariamente malo pero quizá no es lo que estamos buscando)
Cuando borramos un objeto de la tabla hay que marcar el hueco con un identificador de forma que cuando estemos haciendo una busqueda podamos reconocerlo y seguir buscando.
El algoritmo de hashing doble es otro algoritmo de esquema de direcciones abierto que resuelve el problema de colisiones aplicando un segundo hash en caso de colisión. El esquema es relativamente simple:
procedure Write(key : string; data : Pointer);
hash1, hash2, i : integer;
colision : boolean;
hash1 := FuncionHash1(key,tableSize);
// Aplicar los hashes hasta encontrar una posición libre
hash := (hash1 + hash2 * i) mod tableSize;
colision := Assigned(FData[hash]);
until not colision;
// Crear el item
CreateHashItem(FData[hash],key,data);
En el sistema de resolución linea si varias claves hacen hash a un mismo valor seguirán la misma ruta de resolución de colisión (sumando uno). El principio del doble hashing se basa en que es muy poco probable que dos hash distintos sobre distintas claves den el mismo valor para ambas de forma que cuando se produce una colisión en la primera función de hash es altamente probable que no se produzca colisión - con el mismo elemento - al aplicar la segunda función.
Nota: El ejemplo anterior no está teniendo en cuenta el caso de que la tabla este muy (o totalmente) llena lo cual sería malo (si estuviera llena en concreto lo anterior daría un bucle infinito)
Otro metodo para resolver colisiones consiste en establecer, en cada posición en la que se da una colisión, una lista enlazada con todos los elementos. De esta forma cuando realizamos una inserción, en caso de colisión tan solo debemos insertar al final de la lista correspondiente a la posición y cuando estamos realizando una búsqueda, accedemos a la posición y recorremos la lista.
La ventaja de esta solución es que es muy sencilla de implementar, permite que la tabla crezca de forma dinámica hasta la profunidad deseada (siempre podemos controlar la longitud de cada lista) y si estimamos 2 o 3 colisiones como mucho se comporta adecuadamente en las busquedas. Además no estaremos metiendo elementos en posiciones que no les corresponden, es decir, no estaremos produciendo 'falsas' colisiones.
hash := HashFunc(key,tableSize);
if not Assigned(FData[hash]) then
FData[hash] := TList.Create;
TList(FData[hash]).Add(THashItem.Create(key,data));
function Read(key : string) : Pointer;
hash, i : integer;
list := TList;
item : THashItem;
hash := HashFunc(key, tableSize);
lista := TList(FData[hash]);
item := THashItem(lista[i]);
if item.key = key then
type THashItem = class
constructor Create(Id : string; Data : Pointer);
property Data : Pointer read FPointer write FPointer;
type THashTable = class
FTableSize : integer;
FData : Array of TList;
function HashFunction(AId : string) : integer; virtual;
constructor Create(tableSize : integer);
{ Escribe un dato en la tabla dado su id }
procedure Write(AId : string; Data : Pointer);
{ Lee un dato de la tabla dado su id }
function Read(AId : string) : Pointer;
{ Borra un elemento de la tabla dado su id }
procedure Delete(AId : string);
{ Limpia la tabla de elementos }
constructor THashItem.Create(Id : string; Data : Pointer);
FId : Id;
FData : Data;
constructor THashTable.Create(tableSize : integer);
FTableSize := tableSize; SetLength(FData,tableSize);
function HashFunction(id : string) : integer;
{ ELF HASH }
procedure THashTable.Write(AId : string; Data : Pointer);
list := TList(FData[hash]);
if item.Id = AId then
// Si ya existia un item con ese ID sustituir
// Si no existía ya un item con ese ID, crearlo
list.Add(THashItem.Create(AId,Data));
function THashTable.Read(AId : string) : Pointer;
item := THashItem;
procedure THashTable.Delete(AId : string);
Enviado por Jorge el Mar, 12/09/2008 - 23:14. Idiomas

References: Resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución