Hashtable

Roy · #1 28-07-2003

Hola a todos:

¿ Existe en Delphi alguna clase que implemente lo que en Java se conoce como Hashtable ? Deseo guardar objetos (o números) de acuerdo a alguna clave....

Gracias.

Roy

delphi.com.ar · #2 28-07-2003

Te recomiendo este link http://www.undu.com/articles/020604.html

Saludos!

Roy · #3 28-07-2003

... simple y claro. Muchas gracias.

Roy

__marcsc · #4 29-07-2003

Hola,

Aunque la clase parece un poco menos potente que la que te propone delphi.com.ar, Delphi (al menos la versión 6 Enterprise) trae una clase llamada THashedStringList en la unit IniFiles. Quizás te sirva y de este modo evitas depender de una unidad externa.

Saludos.

marto · #5 30-07-2003

Hola,

¿Y por qué no qudarse con nuestra querida TStrings? Cualquier clase que hereda de ella tiene una propiedad Objects en la que se pueden guardar TObject's vinculados a cada cadena. La ventaja es que, por ejemplo, la podemos asignar a la propiedad Items de un combo y hacer que el usuario elija uno de nuestros objetos.
Yo siempre que he neceistado listas de objetos he trabajado o con TObjectList o con TStrings (TStringList habitualmente) en función de si necesitaba una String representativa de cada objeto o no.

Roy · #6 30-07-2003

Hola:

Me gustan vuestras respuestas y siempre es bueno tener más de una alternativa para hacer las cosas... Como usuario nuevo de Delphi que soy, no tengo mucha base para dar una opinión del tema (por eso pregunté !!), pero me parece que cualquier clase que utilice Hashing para las búsquedas, hará que estas sean más eficientes. Quisá se pueda lograr almacenar y recuperar lo mismo con TString, pero cuando son muchos ítems, la diferencia debe estar en la velocidad de búsqueda.... (creo haber leído algo de eso por ahí.....)

Roy

__marcsc · #7 30-07-2003

Hola Marto,

solo un comentario, THashedStringList es un descendiente de TStrings, con lo que en teoria tamibén puede asignarse su valor a los items de un Combo.

Saludos.

marto · #8 30-07-2003

Pues tiees razón Marc, THashedStringList hereda de TStringList y de hecho solo sobreescribe el destructor (que nos es igual)) y los mètodos IndexOf e IndexOfName, es decir los mètodos de búsqueda sobre la lista.
En conclusión, yo me quedaría con esta clase para el proposito que se plantea en el hilo.

delphi.com.ar · #9 30-07-2003

Muchachos, no quiero parece repetitivo, pero en el link que le he recomendado habla también del uso de TStrings

Cita:

Although TStrings provides similar functionality through its Values[] property, this is not a good choice. TStrings doesn't use hashing, so finding an item is an O(n) (slow for lots of data) operation, whereas with a hash it is normally O(1) (same speed regardless of the number of items).

Saludos!

__marcsc · #10 30-07-2003

Hola de nuevo

La verdad es que no acabo de entender el propósito de tu mensaje...

Por lo que yo entendí lo que venía a decir Marto es que es interesante tener un descente de TStrings dado que de este modo tenemos compatibilidad con otros objetos/componentes.

Por cierto, que leyendo el enlace que proponías no he visto la jerarquía de esa clase, y tampoco bajé el código, por lo que no veo si esa clase es descendiente de TStrings.

En todo caso, dado que THashedStringList redefine o introduce los métodos IndexOf y IndexOfName es de esperar que estas dos operaciones sean (o tengan tendencia a ser) también de orden O(1) en lugar de O(n) como el IndexOf de TStrings. No lo puedo confirmar porqué no he mirado el código y la verdad es que ahora no tengo muchas ganas, pero vamos, esta es la idea del hashing, no? jejeje

De todos modos como ya dije a mi me parece más completa la clase de tu enlace dado que permite indexar directamente, sin necesidad de utilizar métodos, lo que pasa que THashedStringList está disponible sin necesidad de bibliotecas externas y además seguro que es descendiente de TStrings.

Saludos compañero

delphi.com.ar · #11 30-07-2003

El propósito es simple, pero no me daban ganas de hacer una explicación larga. El tema es que si THashedStringList desciende de TStrings entonces THashedStringList no es netamente una HashTable como bien dice el texto que he copiado en inglés, los TStrings no utilizan hashing. Ahora si la finalidad es utilizar una lista "cosas" a la que pueda acceder por un Key, sin importarnos la metodología y/o velocidad, pues recomiendo usar TStrings, porque obviamente son mucho mas "naturales" para Delphi.
Aclaro que no he visto la clase THashedStringList, solo me guió por los comentarios expuestos en este hilo.

Simplemente en el mensaje quería remarcar lo que decía el link!

Saludos!

Roy · #12 30-07-2003

Hola denuevo:

Cita:

Posteado originalmente por delphi.com.ar
......Ahora si la finalidad es utilizar una lista "cosas" a la que pueda acceder por un Key, sin importarnos la metodología y/o velocidad, pues recomiendo usar TStrings......
Saludos!

Esta es exáctamente mi finalidad... por lo que entiendo, según el consejo de delphi.com.ar puedo usar TStrings, pero alguien me puede ayudar a hacerlo ? Cómo utilizo una Key para acceder a un ítem ?

Puedo crear un TStringList, pero cada ítem es encontrado por un índice.... y yo necesito poder encontrar un ítem utilizando una clave....

Muchas gracias por todos sus aportes y comentarios.

Roy

__marcsc · #13 30-07-2003

Cita:

Posteado originalmente por delphi.com.ar
El tema es que si THashedStringList desciende de TStrings entonces THashedStringList no es netamente una HashTable

Hola, yo tenía la esperanza de que internamente THashedStringList cambiaba la representación interna de la clase TStrings.

Lo que no te perdono es que por culpa de tu mensaje me has obligado a mirar el código fuente cuando yo realmente no tenía ganas. Esta me la apunto

Ahora en serio, esta es la declaración de la clase

Código:

  THashedStringList = class(TStringList)
  private
    FValueHash: TStringHash;
    FNameHash: TStringHash;
    FValueHashValid: Boolean;
    FNameHashValid: Boolean;
    procedure UpdateValueHash;
    procedure UpdateNameHash;
  protected
    procedure Changed; override;
  public
    destructor Destroy; override;
    function IndexOf(const S: string): Integer; override;
    function IndexOfName(const Name: string): Integer; override;
  end;

Se intuye que lo que hace esta clase realmente es delegar las búsquedas a un objeto cuya clase es TStringHash. La implementación de IndexOf así lo confirma:

Código:

function THashedStringList.IndexOf(const S: string): Integer;
begin
  UpdateValueHash;
  if not CaseSensitive then
    Result :=  FValueHash.ValueOf(AnsiUpperCase(S))
  else
    Result :=  FValueHash.ValueOf(S);
end;

Lo que hace la función UpdateValueHash es insertar el valor en la estructura de datos de TStringHash, es decir, podríamos decir que THashedStringList tiene un comportamiento Just In Time, no utiliza la estructura de datos para hash hasta que se necesita hacer una búsqueda.

Ahora la cuestión es qué hace realmente la clase TStringHash. Realmente lo único que hace es la típica estructura de Hash, es decir una tabla estática de N posiciones. La ubicación de cada elemento se decide aplicandole una función de Hash. Las colisiones se gestionan del siguiente modo. Cada item de la tabla es un apuntador a una variable de tipo PPHashItem:

Código:

PPHashItem = ^PHashItem;
  PHashItem = ^THashItem;
  THashItem = record
    Next: PHashItem;
    Key: string;
    Value: Integer;
  end;

Es decir, cada nodo tiene un apuntador al siguiente. De este modo, si la función Hash es lo suficientemente buena para evitar colisiones (cosa que desconozco

) las búsquedas serán O(1) (dado que la inserción será O(1) y la búsqueda O(1).

Como vemos es una solución un poco híbrida y chapuzilla pero que yo considero totalmente válida en lo que respecta a la eficiencia.

Saludos!

delphi.com.ar · #14 30-07-2003

Cita:

Posteado originalmente por marcsc
cada nodo tiene un apuntador al siguiente

100% Hash!!

Saludos!