[Delphi] THashStringList (대용량 문자열 저장/검색)

낚이면 안되는 게 THashedStringList 가 아니라는 것.

 

코드웨이에서 퍼온 것임.

아래는 그 게시물 내용.

 

사전검색과 같이 대량의 데이터를 빈번히 검색할 때에는 TStringList의 속도가 너무 느려 사용할 수 없죠.

THashedStringList가 Hash를 이용하기 때문에 월씬 속도가 빠르지만 두가지 단점이 있습니다.

먼저 hash크기가 255로 고정되어 있어서 데이터의 양이 많아질 수록 해쉬값 충돌로 인해 검색 속도가

느려진다는 점이고, 두번째는 삽입/삭제가 발생하면서 검색하면 최악의 성능을 보인다는 것입니다.

이는 값이 변경이 발생한 후 검색을 하면 해쉬를 다시 생성하기 때문에 시간이 많이 소요됩니다.

 

그래서 THashedStringList를 참고로 해서 위의 문제점을 수정한 클래스를 만들어 보았습니다.

 

약 290000건의 데이터를 가지고 테스트해 본결과

 

 

                                  삽입 후 검색             삽입/검색을 동시에

TStringList                   측정 포기                  측정 포기

THashedStringList         27초                        측정 포기 

THashStringList            2초                          2초

 

좀 더 빠른 검색을 원하시면 Jedi에 있는 TStringHaspMap를 이용해 보세요.

 

 

 

코드는 그리 길지 않으므로 본문에 바로 첨부함.

 

 

unit HashStringList;

 

interface

 

uses
  Classes, SysUtils, IniFiles;

 

type
  THashStringList = class(TStringList)
  private
    FValueHash: TStringHash;
    FHashSize: Integer;
    procedure AddHash(const S: string; Index: Integer);
    procedure DeleteHash(Index: Integer);
  protected
  public
    constructor Create(HashSize: Integer);
    destructor Destroy; override;
    function Add(const S: string): Integer; override;
    procedure Delete(Index: Integer); override;
    function IndexOf(const S: string): Integer; override;
    function Contains(const S: string): Boolean;
    procedure Remove(const S: string);
  end;

 

implementation

 

 

{ THashStringList }

function THashStringList.Add(const S: string): Integer;
begin
  Result:= inherited Add(S);
  AddHash(S, Result);
end;

 

procedure THashStringList.AddHash(const S: string; Index: Integer);
begin
  FValueHash.Add(S, Index);
end;

 

function THashStringList.Contains(const S: string): Boolean;
begin
  Result:= IndexOf(S) <> -1;
end;

 

constructor THashStringList.Create(HashSize: Integer);
begin
  // 대소문자를 구별한다.
  CaseSensitive:= True;
  FHashSize:= HashSize;
  FValueHash := TStringHash.Create(FHashSize);
end;

 

procedure THashStringList.Delete(Index: Integer);
begin
  DeleteHash(Index);
  inherited Delete(Index);
end;

 

procedure THashStringList.DeleteHash(Index: Integer);
begin
  Remove(Self[Index]);
end;

 

destructor THashStringList.Destroy;
begin
  FValueHash.Free;
  inherited Destroy;
end;

 

function THashStringList.IndexOf(const S: string): Integer;
begin
  Result := FValueHash.ValueOf(S);
end;

 

procedure THashStringList.Remove(const S: string);
begin
  FValueHash.Remove(S);
end;

 

end.