시작하며
Key value 구조의 장점은 명확하다. 개발적으로는 데이터 집합 내의 요소들을 key 로 구분하여 알아보기 쉽게 해주며, 자료구조적으로는 O(1)에 가까운 접근 시간을 가진다. 즉 알아보기도 쉽고 사용하기도 쉬우면서 심지어 매우 빠르다. 이렇게 만능인 자료구조이지만 그 댓가로 메모리 사용량이 높다.
자바의 HashTable, HashMap, C#의 Dictionary, 자바스크립트의 Object 등등 거의 대부분의 언어들은 어떤 식으로든 Key value 자료구조를 제공하고 있으며 사용하기도 매우 쉽다. 이번 포스팅에서는 이 Key value 자료구조의 작동 원리를 간단하게나마 이야기 해보도록 한다.
메모리는 1차원 배열
key value에 대해 이야기 하기 전에 우선 메모리, 변수, 배열에 대해 간단하게 짚고 넘어가보자.
메모리의 구조에 대해 생각해보자. 여기서 말하는 메모리 구조란 힙 영역이니 커널 영역이니 같은 몇 번씩 추상화된 구조가 아니라 조금 더 직접적인 형태에 대해 이야기한다.
복잡할 건 없다. 메모리는 1차원 위상공간을 가진 저장공간일 뿐이다. 컴퓨터에 램이 몇개가 꽃혀있든, CPU의 캐쉬가 몇개가 있든 그것들은 모두 합쳐져 OS레벨에서 1차원 메모리 공간으로 취급된다.
메모리 공간은 1바이트 단위로 주소를 가지며 이 주소는 정수값이다. 만약 메모리 공간이 총 1000바이트라고 하면 이 메모리 공간의 주소 범위는 0~999가 된다.
즉 메모리는 1차원 배열이라고 생각할 수 있다. 배열의 특정 요소를 접근할 때는 오직 그 요소의 인덱스만으로 접근할 수 있는 것 처럼 메모리의 특정 공간으로 접근하는 것은 오직 해당 메모리 주소만으로 접근할 수 있다.
변수
프로그램에서 가지는 모든 데이터 메모리에 저장된다. 변수도 데이터니까 당연히 메모리 어딘가에 저장되어 있다. int 형 변수 a 가 있다고 가정해보자. 여기서 int 는 4바이트라고 가정한다.
int a = 77;
변수 a에 들어있는 값 77을 메모리 어딘가에는 저장되어 있을 것이다. 대충 1000바이트의 메모리 공간이 있다고 가정하고 a의 주소가 300번지로 배정되었다고 가정해보자.
위 그림에서는 300번지에 a의 값이 들어가있다. 우리는 a의 값을 읽고 쓰는데 그 어떠한 중간과정도 필요하지 않다. 위에 선언되어 있는 a에 88을 덮어 씌우면 메모리 공간은 아래와 같이 될 것이다.
a = 88;
메모리 300번지의 값이 88로 바뀌었다. 너무나 당연한 결과지만 이것이 가능한 것은 a 라는 변수명으로 300번지에 직접 접근이 가능하기 때문이다. 즉, 변수명 a는 주소 300번지를 매핑하고 있다고 볼 수 있다.
(300번지) = 88;
변수명에는 특정 메모리 공간의 시작 주소가 매핑된다. 위의 변수 a는 300번지가 매핑되어 있고, int형으로 선언되어 있기 때문에 300번지부터 4바이트만큼의 공간, 즉 300, 301, 302, 303 번지의 데이터를 가져오거나 해당 번지들에 데이터를 쓸 수 있는 것이다.
배열
배열도 동일하다. 변수명에 해당 변수의 메모리 시작 주소가 매핑 되는것처럼 배열도 배열 변수명에 해당 배열의 시작 주소가 매핑된다. 일반 변수와 다른 점은 연속적인 메모리 공간이 예약 된다는 것이다.
int b[10] = {0,};
배열 변수명 b에 50번지가 배정되었다고 가정하면 b배열로 예약되는 공간은 50 ~ 89 번지까지가 된다.
배열의 각 요소는 (시작 주소 + (데이터형 사이즈 * 배열인덱스)) 의 식으로 바로 메모리 주소를 얻어내어 접근할 수 있다.
b의 인덱스 3 요소에 접근하고자 한다면 (50 + (4 * 3)) = 62 라는 간단한 식으로 접근 메모리 주소를 즉시 획득할 수 있는 것이다.
Key value
위에서 굳이 변수와 배열, 그리고 메모리에 대해 이야기를 한 것은 하나의 사실을 이야기 하고 싶었기 때문이다. 일반적인 개발 상황에서, 개발자가 메모리에 직접 접근할 수 있는 수단은 변수와 배열 뿐이다.
일반 변수는 단일 값이기 때문에, 데이터의 집합을 한 번에 메모리로 접근할 수 있는 수단은 사실상 배열이 유일하다. 그러나 Key value 구조도 집합 내 요소들을 key로 한 번에 접근 가능한데 이것은 결국 Key value 구조가 사실상 배열이기 때문에 가능한 일이다.
key를 인덱스로 변환
실제로는 배열인만큼 key 를 배열 인덱스로 변환시켜야만 한다. 이 과정은 흔히 해시 함수로 수행하게 되는데, 이 해시 함수의 성능은 해당 key value 구조의 성능을 결정짓는 아주 중요한 요소로 작용한다. 아래는 극단적으로 간단한 해시 함수의 예다.
int hashKey(string key, int arraySize){
return key[0] % arraySize;
}
key를 해시하여 인덱스를 얻게되니 당연히 중복 인덱스가 생성되는 문제가 발생한다. 그렇기 때문에 key value 구조의 내부 배열은 각각의 요소를 리스트 형태로 관리하게 된다. 이 리스트를 단순한 링크드 리스트로 구현할지, 이진 트리로 구현할지 등등의 구체적인 구현은 구현목적에 따라 달라지게 된다.
배열 크기의 문제
key value 의 실제 정체는 결국 배열이니 만큼 배열 크기의 문제에서 자유로울 수 없다. 근본적으로 배열은 고정된 크기를 갖으며 크기를 변경할 수 없는 자료구조다.
//KeyValueStore 를 생성할 때 실제로 내부적으로는 고정된 크기의 배열이 생성된다.
KeyValueStore<int> a = new KeyValueStore();
그렇기 때문에 key가 계속 추가가 되어 결국 내부의 배열 크기를 초과하게 될 때, 새롭게 내부 배열을 재생성 해주어야 한다. 이 때 재생성 하는 배열의 크기를 이전 배열의 크기 보다 얼마나 크게 생성할지는 구현 목적에 따라 달라진다.
만약 이전 배열의 크기보다 조금만 크게 재성생 한다면 key가 계속 추가될 경우 재생성을 자주 해주어야만 하기 때문에 key 추가 성능이 떨어지게 된다.
반대로 재생성 크기를 크게 늘릴 경우 key 추가에 의한 성능 손실은 줄일 수 있으나 key가 더 이상 추가가 되지 않을 경우, 사용되지 않은 배열 공간은 그대로 낭비되게 된다. 물론 이 문제는 최초 생성시에도 동일하게 적용된다. 이것은 key value 구조가 메모리를 댓가로 성능을 얻을 수 있는 근본적인 이유이기도 하다.
key를 삭제할 때에도 위 문제는 그대로 적용되는데 추가로 인한 문제보다 삭제로 인한 문제가 더 많다. 특히 검색 성능의 최적화를 위해 배열 요소가 트리 구조등으로 구현되어 있다면 삭제 시 성능에서 손해를 꽤 많이 보기 때문에 반드시 필요한 경우가 아니면 키 삭제 시 메모리를 반환하지 않는 경우가 많다.
마치며
메모리 사용량에 약점이 있는 key value 구조이지만 요즘처럼 메모리가 풍족한 시대엔 이마저도 약점이라 치부하기도 어려운 것 같다. 위에서 이것저것 쓰잘데기 없이 설명하였지만 설명한 모든 것을 신경쓰지 않아도 key value 는 쉽게 사용할 수 있다. 이 쉬움이야 말로 가장 큰 장점이 아닐까 싶다.