해시테이블 하나에 담긴 고민들

박재성 님의 Next-Step 스터디를 진행하면서 WAS를 구현하는 미션을 수행했다. 처음에는 HTTP Header를 HashMap 형태로 구현하다가 이런 고민이 생겼다.

결국 이 헤더를 순회해서 문자로 만든 다음에 쏴 줘야 하는데, HashMap은 요소들 간의 순서가 보장이 안 된다. 그렇다면 보낼 때마다 헤더 필드의 순서가 바뀌게 되는데…

 

물론 헤더 순서가 바뀌어도 작동은 잘 된다. 헤더 값만 결국에 들어있으면 되기 때문. 하지만 여기에도 일종의 컨벤션이 있을 것이다. 자료들을 찾아보면 대부분 Host → Accept → User-Agent 같은 순으로 일관된 공통분모가 있다. 물론 클라이언트와 서버의 명세에 따라 또 다른 헤더를 넣을 수도 있고, 요청마다 헤더에 담기는 정보들도 다르기 때문에 뭐라 정의할 수는 없지만, 적어도 헤더에 넣은 순서대로는 응답이 가야지! 하는 생각이었다.

LinkedHashMap은 입력 순서가 보장된다

그럴 때 쓰라고 자바에는 LinkedHashMap이라는 자료구조가 있다. 기본적으로 작동 방식은 HashMap과 같다. 각 노드마다 이전 노드(before)와 이후 노드(after)를 참조하는 변수가 추가되어서 일종의 연결 리스트처럼 작동하는 구조다.

 

얘는 인간적으로 그리기 너무 힘들다... 출처는 아래에!

 

조금 더 자세히 설명해 보면, 해시맵에서는 특정 key의 요소를 찾을 때 key값을 해싱한 값이 table 배열에서의 인덱스가 된다. 해당 인덱스에서 요청한 key값을 찾을 때까지 해당 인덱스의 노드와 그 next 변수를 통해 노드 체인을 탐색한다. 여기서 주의할 점은 next는 지금 설명한 것처럼 테이블(버킷) 내에서 해싱된 인덱스가 값이 같은 노드들 사이에서의 순서를 나타내기 위한 변수이고, LinkedHashMap에서 입력 순서를 보장하기 위한 다음 변수는 before/after다. 처음에 자료를 찾을 때 next와 after의 역할 차이를 잠깐 혼동했는데, 해시 충돌 시에 같은 인덱스 내에서 노드들을 연결하기 위한 next는 HashMap에도 동일하게 있는 변수다.

 

즉 before/after라는 두 개의 참조변수가 추가되면서, 해시맵에 값을 추가하거나 삭제할 때 연결리스트를 탐색하는 비용이 생기지만, 값을 찾을 때는 HashMap과 똑같이 해싱된 인덱스를 찾아가는 방식은 같기 때문에 별도의 추가적인 성능 저하는 발생하지 않는다. 사실 HashMap을 사용하는 주요 이유는 원하는 key의 값을 O(1)에 찾아내는 데에 있기 때문에 일반적으로 LinkedHashmap의 성능 자체는 일반적인 HashMap과 비슷하다고 보는 경우가 많다.

 

하지만 역시 LinkedHashMap이 가지는 단점은 메모리를 좀 더 먹는다는 점일 것이다. 매 노드마다 before/after 변수가 추가로 덧붙기 때문이다.

 

파이썬 Dictionary는 순서 유지가 디폴트인데?

그러다가 문득 알고리즘 풀이할 때 쓰는 파이썬 Dictionary 생각이 났다. 파이썬의 Dictionary는 HashMap에 대응하는 해시테이블 자료구조인데, 파이썬 3.7버전 이후로는 LinkedHashMap처럼 입력 순서가 유지된다. 그래서 궁금증이 들었다.

순서 보장이 안 되는 일반적인 해시테이블 구조보다 메모리를 더 먹는데도 기본 구현을 변경한 이유가 뭘까?

그래서 찾아보니, 놀랍게도 파이썬의 새로운 딕셔너리 구조는 이전 버전의 구현과 비교해서 메모리를 덜 먹는다는 것이다! 어떻게 가능했을까? 이 새로운 딕셔너리 구조를 처음 제안한 Raymond Hettinger가 초기에 생각한 디자인을 보면 그 차이를 이해할 수 있다.

 

원래의 딕셔너리 구조는 위에서 살펴본 자바의 HashMap이 그렇듯 배열 안에 실제 key, value가 들어있는 구조였다. 이 key, value가 들어있는 배열을 entries라고 보면, entries[해싱된 인덱스]에 key, value가 들어있을 것이고, 해시 테이블 특성상 entries 배열에는 비어있는 인덱스가 많은 구조일 수밖에 없다.

 

 

배열 한 칸에 해시값(long 변수, 64비트 기준 8Byte), key 포인터(8Byte), value 포인터(8Byte)가 들어가기 때문에 총 24Byte의 데이터 공간이 필요한데, 비어있는 인덱스가 있을 때마다 24Byte의 공간이 낭비되는 셈이다. 파이썬은 위에서 예시로 든 자바처럼 해시 충돌이 일어났을 경우에 연결 리스트로 잇는 개별 체이닝 방식이 아니라 인접한 빈 공간을 찾아 노드를 넣어 놓는 오픈 어드레싱 방식을 사용하기 때문에, 충돌이 많을 경우엔 조금 더 빈 공간이 적을 수 있겠지만 상대적으로 큰 공간을 낭비해야 함은 분명하다.

 

그런데 새로운 구현에서는 신기한 방법을 쓴다. 새로운 구현에서는 위의 entries에 해당하는 배열을 해시 테이블로 사용하지 않는다. entries는 그냥 배열로 순서대로 값들을 넣어 두고, 해당 entries의 변수들이 entries에서 인덱스 몇 번에 있는지를 나타내는 해시 테이블인 indcies를 따로 두는 것이다.

 

그리고 이 indicies에 저장되는 건 그냥 정수값이다. 그리고 이 정수의 크기는 entries의 변수 개수에 따라 달라진다. entries의 원소가 256개 이하라면 이 배열은 byte로 만들어지고, 2^16개 이하라면 2바이트 정수, 2^32개 이하라면 4바이트 정수…로 가변적으로 변하는 식이다. 뭐가 됐든 정수값 하나이니 24Byte보다는 작을 것이다.

 

 

즉, 실제 데이터 entry들은 entries에 순서대로 저장되고, 실제로는 중간에서 indicies가 실질적인 해시 테이블 역할을 하게 되는 것이다. 이렇게 자료구조를 이원화하면서 해시값으로 데이터를 찾는 기존의 탐색도 낭비되는 공간을 줄이면서 구현 가능하고, 순서대로 전체 entry가 필요할 때는 entries를 쓰는 방식을 사용하게 되는 것이다.

 

자료들을 찾으면서 entries도 전체 배열 크기 대비 일정 개수 이상의 데이터가 차면 더 메모리를 많이 할당해서 새로운 리스트로 옮겨갈 텐데, 그렇다면 entries에도 메모리가 꽤 쓰이지 않을까? 하는 의문도 들었는데, 공간이 부족할 때 새로 늘리는 것은 기존의 entries 배열 하나일 때도 마찬가지였을 것이기 때문에 어찌되었든 새로운 방식이 더 메모리 공간을 효율적으로 사용할 것이라 추측해 볼 수 있다.

 

언어는 계속 진화하고, 정답은 없다!

처음 ‘파이썬은 어떨까?’하고 찾아볼 때는, 당연히 파이썬도 비슷한 구조를 통해서 순서가 유지되는 해시테이블을 만들었을 거라고 생각했다. 그런데 일단 두 언어에서 비슷한 기능을 하는 자료구조의 내부 구현이 전혀 다르다는 점이 흥미로웠다. 역시 내부구조를 까 보다 보면 생각하지도 못한 개발자들의 발상들을 엿볼 수 있다는 점이 즐겁다.

무엇보다도 파이썬을 주력으로 사용하고 있지는 않지만, 언어도 끊임없이 개선을 거듭하고, 그 과정에서 여러 개발자들의 피땀눈물이 있구나… 하는 사실을 느꼈다. 매일같이 쓰는 해시테이블 자료구조 하나에도 이렇게 많은 고민이 들어가 있다!

 

 

 

참고자료

• 자바 LinkedHashMap 이미지 출처
• Are dictionaries ordered in Python 3.6+?
• More compact dictionaries with faster iteration
• Faster, more memory efficient and more ordered dictionaries on PyPy