Club Delphi  
    FTP   CCD     Buscar   Trucos   Trabajo   Foros

Retroceder   Foros Club Delphi > Otros entornos y lenguajes > Lazarus, FreePascal, Kylix, etc.
Registrarse FAQ Miembros Calendario Guía de estilo Buscar Temas de Hoy Marcar Foros Como Leídos

Respuesta
 
Herramientas Buscar en Tema Desplegado
  #1  
Antiguo 14-02-2008
godel godel is offline
Registrado
 
Registrado: feb 2008
Posts: 5
Poder: 0
godel Va por buen camino
Tablas Hash

Hola a todos:

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

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

Alguien sabe .

Gracias adelantas
Responder Con Cita
  #2  
Antiguo 15-02-2008
Avatar de Neftali [Germán.Estévez]
Neftali [Germán.Estévez] Neftali [Germán.Estévez] is offline
[becario]
 
Registrado: jul 2004
Ubicación: Barcelona - España
Posts: 18.233
Poder: 10
Neftali [Germán.Estévez] Es un diamante en brutoNeftali [Germán.Estévez] Es un diamante en brutoNeftali [Germán.Estévez] Es un diamante en bruto
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).
__________________
Germán Estévez => Web/Blog
Guía de estilo, Guía alternativa
Utiliza TAG's en tus mensajes.
Contactar con el Clubdelphi

P.D: Más tiempo dedicado a la pregunta=Mejores respuestas.

Última edición por Neftali [Germán.Estévez] fecha: 15-02-2008 a las 11:12:37.
Responder Con Cita
  #3  
Antiguo 17-02-2008
godel godel is offline
Registrado
 
Registrado: feb 2008
Posts: 5
Poder: 0
godel Va por buen camino
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
Responder Con Cita
  #4  
Antiguo 19-02-2008
godel godel is offline
Registrado
 
Registrado: feb 2008
Posts: 5
Poder: 0
godel Va por buen camino
Smile

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
Responder Con Cita
Respuesta


Herramientas Buscar en Tema
Buscar en Tema:

Búsqueda Avanzada
Desplegado

Normas de Publicación
no Puedes crear nuevos temas
no Puedes responder a temas
no Puedes adjuntar archivos
no Puedes editar tus mensajes

El código vB está habilitado
Las caritas están habilitado
Código [IMG] está habilitado
Código HTML está deshabilitado
Saltar a Foro

Temas Similares
Tema Autor Foro Respuestas Último mensaje
codigo hash maco2007 Varios 4 20-10-2007 18:01:04
tablas en sql server demasiadas tablas yeison Cristman SQL 8 10-08-2006 17:26:36
Hash RaulChemical Varios 1 07-09-2004 21:10:11
Ver tablas Onti Oracle 4 25-09-2003 17:26:24
¿Hash or not Hash? hgiacobone Varios 5 17-07-2003 20:43:26


La franja horaria es GMT +2. Ahora son las 22:52:37.


Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi
Copyright 1996-2007 Club Delphi