Hashtable

[__marcsc]

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

  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:

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:

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!