Tablas Hash
 

Hola a todos:

Soy nuevo en esto de pascal y delphi y tengo una duda como se puede hacer una tabla hash :D .

No he encontrado nada creo que es un paquete ne particular pero no lo se seguro.

Alguien sabe .

Gracias adelantas

Básicamente una tabla Hash es una lista de elementos, pero variando la forma en que se añaden y se buscan. Normalmente una lista es secuencial, o ordenada por un campo. La diferencia de una tabla hash, es que la posición de cada elemento te la devuelve una función que debes aplicar al propio elemento.

Imagina que vas añadir nombres a una lista: Pepe, Juan, Jose, Luis,...

Antes de añadir el nombre (Pepe) a la lista le aplicas una función F, y eso te devuelve un entero. Ese entero (por ejemplo 37) es la posición en la lista donde colocarás a Pepe. Cuando va a añadir a Juan le aplicas la función F y eso te devuelve otro entero (por ejemplos 17); Esa será la posición donde añades a Juan.

Al final una HashTable es una Array de posiciones y una función que aplicas a los elementos.

La gracia de las tablas Hash, es que cuando vas a buscar el elemento Pepe, le aplicas la función F y te devolverá de nuevo el 37, con lo que el acceso al elemento es inmediato. Pepe está en la posición 37 del array.

(1) Debes partir con un array de posiciones fijas; Por ejemplo 1.000, 10.000, 100 posiciones (debes hacer una estimación de cuantos elementos vas a añadir). Dependerá de los elementos que vayas a añadir.
(2) La función F es "la madre del cordero" como se suele decir; Debe ser una función que te devuelva como máximo el número 10.000 (el mismo número escogido para el array) que es el tope del array. Debe ser una función rápida, para que no pierdas mucho tiempo en cálculos, pero a la vez debe ser una función lo suficientemente compleja para que no devuelva colisiones (*NOTA*). Tener muchas colisiones es malo, porque baja el rendimiento de la lista.
(3) Cuando desees acceder a la lista para añadir, borrar, buscar o modificar un elemento, debes aplicarle la función y eso te dará la posición exacta donde se encuentra.

Espero haberte aclarado algo. Si tienes dudas pregunta. La implementación de una lista de hash no es sencilla, aunque lo primero que debes hacer es entender el concepto.


(*NOTA*) Se entiende por colisión, cuando la función F aplicada a dos elementos devuelve el mismo entero. En esa posición deberías almacenar dos elementos. Hay varias formas de solucionar esto, pero en todos los casos perderás tiempo, ya que no obtendrás un acceso directo al elemento. Por eso interesa una función de Hash que devuelva el mínimo numero de colisiones posibles.
Lo más importante es encontrar el equilibrio entre una función de hash sencilla (para que sea rápida), pero a la vez compleja (para que devuelva el mínimo número de colisiones).

tabla hash
 

Gracias por contestar , pero creo que mi pregunta no estuvo bien formulada ,

Tengo que hacer un compilador y necesito hacer una tabla hash donde la key sea un String y lo otro sea una lista de string.

Como creo que Delphi no tiene tabla hash propia me he bajado un paquete que se llama "hashtrie" , y mi pregunta es como hago para crear una de esta forma , ya que no he encontrado nada por ahí.

Gracias adelantadas :confused:

Bueno ya he resuelto el problema de las tablas una vez que metes el paquete en el proyecto , solo has de meter este dato para crear y para acceder y añadir es lo siguiente:

Código Delphi [-]
procedure TForm1.FormCreate(Sender: TObject);
var
  miLista:TStringList;
  listaAux :TStringList;

begin
  htable:=TStringHashTrie.Create;
  htable2:=TStringHashTrie.Create;
  miLista:=TStringList.Create;
  htable.Add('llave1',miLista);
  showMessage(booltoStr(htable.find('llave1',TObject(miLista))));
end;

Gracias a todos