[한민호]HashedStringList 제대로 알고 사용하기

 

 엑셈에 입사하게 되면서 학창시절 어렵게 공부했던 List에 관심을 갖기 시작했다. 프로그래밍에 문외한이었던 나에게 자료구조 초반에 배웠던 List는 어렵고 과연 저것이 얼마나 많이 사용될까 싶었는데 현업에서는 매우 자주 사용되고 있었다. 또한 초보 프로그래머들에게는 라이브러리 클래스로 지원되는 List를 이용하면 공들여 List를 프로그래밍 하지 않고도 쉽게 사용할 수 있었다.

 델파이를 접하게 되면서 가장 처음 접하게 된 리스트가 StringList였다. 정말 유용하지만 List에 데이터가 많을 경우 첫 번째 인덱스부터 순차적으로 검색하기 때문에 검색속도가 매우 떨어지는 단점에도 불구하고 다른 방법이나 내부적 구조를 몰랐기에 그냥 사용할 때가 많았다.

어느 날 검색속도에 관심을 갖고 StringList의 대안을 찾던 중 HashedStringList라는 꽤 괜찮은 List을 알게 되었다. HashedStringList는 StringList를 그대로 상속받아 만들어져 StringList가 가진 기능들을 전부와 단지 IndexOf 메소드의 기능을 충실히 할 수 있도록 Name과 Value의 Hash키만을 가지고 있었다.

 Hash Table을 가지고 있는 것만으로도 검색속도는 매우 좋을 것이라 생각했고 이것이 어떠한 함정이 있을 것이라곤 깊게 생각하지 못했다.

 이 HashedStringList에 대해 자세히 알아보기 위해 예제를 만들어 확인해 보기로 했다. 예제는 1500만 건의 숫자 스트링을 10회 Insert 해본 통계와 10회의 Search 성능의 통계이다.

 

 
 예제를 보면 StringList와 HashedStringList의 Insert 속도는 거의 동일한 것을 확인 할 수 있고 검색 속도는 평균적으로 HashedStringList가 훨씬 앞서는 것을 확인할 수 있다. 예제상의 화면만으로 분석을 해보자면 Insert시 Hash Table을 생성하지 않는 다는 것을 추측해 볼 수 있다. Hash Key 를 생성하고 Hash List를 만든다면 1500만 건의 데이터를 삽입하는데 절대 동일한 성능이 나올 수가 없기 때문이다. 또한 Search 테스트를 보면 Hash List가 언제 생성되는지 추측해 볼 수 있다. Search 테스트를 보면 Hash List는 첫 번째 데이터를 조회할 때 생성된다고 볼 수 있다.

 1을 조회하는데 StringList는 0ms이 걸렸지만 HashedStringList는 7250ms(약 7초)나 걸렸기 때문이다. 오히려 Insert를 한 시간보다 더 오래 걸린 것을 확인할 수 있다. 이것은 Hash List에 Insert하기 전 Hash Key를 생성하는데 드는 시간이라 볼 수 있다.

 StringList는 1부터 1500만까지 0을 하나씩 늘려가며 조회해 볼 때마다 시간이 점점 늘어나는 것을 확인할 수 있는데 이것은 단순 for루프를 이용해서 조회가 되기 때문이다. 그러나 HashedStringList는 Hash List가 생성된 이후 Hash Key를 이용해서 단번에 찾아가기 때문에 검색 시 검색어의 Hash Key를 생성하는 시간을 제외하고는 더 이상 검색하는 속도에는 시간이 들지 않기 때문에 매우 효율적인 검색이 가능하다.

 이러한 결과에 대해 소스를 확인해보면서 좀더 설명해 보도록 하자.

 

-          THashedStringList 소스 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;

 

 소스에서 IndexOf와 IndexOfName만 오버라이드 했다는 것만 봐도 이 함수들에 대한 내용이   변경이 되었다는 사실을 알 수 있다. 또한 중점적으로 보아야 할 부분이 Value와 Name에 대해 Hash List가 있다는 것이다. 이것이 바로 검색 시 참조될 리스트 이다.

 이 두 개의 리스트로 인해 생기는 단점은 메모리 사용량이 데이터 개수가 늘어날 때마다 함께 증가 할 수 있다는 것이다(검색 기능을 이용하지 않는다면 증가하지 않을 수도 있다.). 때문에 데이터가 매우 많다면 윈도우에서 한 프로세스가 소유할 수 있는 메모리가 2GB로 제한되어 있기 때문에 Hash List가 생성될 시점에 Out of Memory와 같은 메시지가 출력될 수도 있다는 문제점이 있다.

 그렇다면 이 Hash List가 어느 시점에 생성이 되느냐가 중요할 수 있는데 보통 Hash Table은 데이터가 Bucket에 들어가면서 함께 업데이트가 된다. 하지만 앞서 테스트 예제와 같이 HashedStringList는 좀 달랐다. IndexOf나 IndexOfName을 통해 검색이 될 시점에 Hash List가 생성이 되도록 되어 있었다.

 그래서 Insert 통계를 보면 Hash Table을 생성하지 않기 때문에 일반 StringList와 HashedStringList가 거의 동일한 데이터 Insert 성능을 보여주었던 것이다.

 소스를 확인해보시면 더 이해가 빠르리라 생각된다.

 

-          IndexOf 함수 function THashedStringList.IndexOf(const S: string): Integer; begin   UpdateValueHash;   if not CaseSensitive then     Result :=  FValueHash.ValueOf(AnsiUpperCase(S))   else     Result :=  FValueHash.ValueOf(S); end;   -          UpdateValueHash 프로시저 procedure THashedStringList.UpdateValueHash; var   I: Integer; begin   if FValueHashValid then Exit;     if FValueHash = nil then     FValueHash := TStringHash.Create   else     FValueHash.Clear;   for I := 0 to Count - 1 do     if not CaseSensitive then       FValueHash.Add(AnsiUpperCase(Self[I]), I)     else       FValueHash.Add(Self[I], I);   FValueHashValid := True; end;

 

IndexOf 소스를 보면 UpdateValueHash 프로시저를 호출하게 되는데 이 UpdateValueHash를 확인해보면 ValueHash List를 생성하여 Hash Table을 만들고 있다. 이 과정 때문에 초기 검색 시 매우 많은 시간이 소요되며 많은 데이터가 존재할 경우 아예 검색이 안될 수도 있는 상황이 발생할 수 있다. 실제 1억 건 정도의 숫자 스트링 데이터를 Insert 시 Out of Memory 메시지가 출력이 되어 검색이 제대로 되지 않았다.

 그리고 최대 단점은 Hash List의 Bucket이 데이터 수만큼의 배열로 관리가 되고 있기 때문에 한 건의 데이터가 추가되거나 삭제되어 바뀌더라도 배열을 새로 생성해야 한다는 것이다. 때문에 HashedStringList의 데이터가 변경(Add, Delete, Update)되면 다시 검색속도가 느려지는 치명적인 단점을 가지고 있다.

 결론을 짓자면 HashedStringList를 사용은 변동이 없는 정적인 데이터들을 보관하고 그것들을 자주 조회하는 프로그래밍에 적합하다고 생각된다. 무조건 조회가 빠르다고 해서 사용했다간 오히려 StringList보다 더 많은 메모리를 사용하면서 성능의 이득조차 볼 수 없는 그런 상황이 되어버릴 수 있다. 하지만 적합한 환경에 사용한다면 엄청난 이득을 볼 수 있는 좋은 List란 생각이 든다.