Implement Hash String ID Index #1

문자열은 게임 개발에서 아직까지 많이 사용되고 있는 데이터 형식입니다. 여기서 데이터 형식이라고 한것은 문자열이 근본적으로 정수형이나 실수형처럼 내재된 데이터 타입이 아니기 때문입니다. 따라서 문자열 데이터 형식을 실제로 구현 및 처리할 때에는 많은 문제들이 발생합니다.

문자열에 대한 근본적인 문제로는 저장과 관리의 문제입니다. C++에서 문자열들은 근본적인 데이터형이 아닙니다. 따라서 문자열은 문자의 배열로 구현되고, 이에 대한 변수 길이는 하드코딩으로 제한되거나, 동적으로 할당합니다. 따라서 이를 처리하기에 편리한 여러 문자열 클래스들이 존재합니다. STL의 string 클래스가 좋은 예제입니다. 

두번째 문제로는 다중언어의 지원입니다. 이를 지원하기 위한 유니코드의 사용과 멀티바이트의 사용은 기본적인 규칙을 초기에 잡아주지 않으면 많은 문제가 발생하며, 특히 한자권 지역의 언어 지원은 많은 문제를 발생시킬 수 있습니다.

최종적으로 이 글에서 처리하고자 하는 속도의 문제입니다. 문자열들을 아직까지 내부적인 리소스 파일 이름, 오브젝트 아이디와 같은 곳에서 사용하는 프로젝트가 많이 존재합니다. 예를 들면 레벨 오브젝트에 "Player-Camera", "Mountain-Rock-01" 등등이 있습니다. 좋은 명명 규칙을 가진 문자열은 프로그래머나, 디자이너들이 오브젝트나 리소스들을 식별하기에 매우 편리합니다. 하지만 이렇게 문자열들만을 사용하여 처리하는 것은 게임 속도의 저하를 유발할 가능성이 매우 높습니다. 정수형들이나 실수형들을 비교하거나 복사하는 것은 단순히 머신 언어 명령들을 통해 이루어지기 때문에 매우 빠릅니다. 하지만 strcmp()와 같은 함수를 사용한 문자열들의 비교는  문자 배열들을 검색하는 O(n)의 비용이 필요합니다. 문자열의 복사는 메모리 동적 할당 비용을 포함한 O(n) 메모리 복사가 필요합니다. 문자열만을 사용하는 프로젝트들에서 strcmp()와 strcpy()가 가장 시간을 소비하는 함수로 측정될 가능성이 매우 높습니다.

이에 따라 문자열을 해쉬화 하여 정수형으로 대응하여 사용한다면 매우 많은 속도 이득을 볼 수 있습니다. 해쉬 함수는 부분적인-단일 정수에 문자열을 대응합니다. 문자열 해쉬 코드의 비교는 정수비교와 같은 것이어서 매우 빠르게 이루어질 수 있습니다. 해쉬 테이블 형식으로 문자열들을 저장해 놓는다면 해쉬 코드로부터 문자열을 얻어 올 수 있어 디버깅을 할 때나 디자이너에게 표시해 줄 때도 기존의 문자열로 표시해 줄 수 있습니다.

하지만 많은 사람들이 해시 시스템에서 충돌이 발생할 가능성이 있어 해쉬화된 문자열을 기피한다고 이야기들을 합니다. (즉, 두가지 다른 문자열들이 동일한 해쉬 코드를 생성하는 것입니다). 하지만 알맞은 해쉬 함수를 사용한다면,. 32-비트 해쉬 코드는 40억 이상의 값들을 사용할 수 있습니다. 그래서, 만일 해쉬 함수가 매우 넓은 범위로 문자열들을 잘 배치한다면, 충돌이 발생하지 않습니다. 해외의 스튜디오에서는 단순히 CRC-32 알고리즘을 사용하였을 때 2년동안 충돌이 한번도 발생하지 않았다는 참고 문서가 존재합니다.

다음 글에서는 해쉬화된 문자열의 구현에 대한 단계들을 차례로 설명해 보도록 하겠습니다.

- by 김영민

- 참고 문서: Game Engine Architecture: 5. Engine Support System