[C#] 해시테이블

c#에서 해시테이블은 키-값 쌍을 저장하는 데이터 구조로 키를 사용하여 값을 검색하고 저장할 수 있는 컬렉션이다.

해시테이블은 특정 키에 대한 값을 빠르게 찾을 수 있는 해시 함수를 사용하여 내부적으로 데이터를 저장하는 방식을 사용하는데 이는 키 값을 해시 함수로 해싱하여 해시테이블의 특정 위치로 직접 액세스하도록 만든 방식이다.

 

여기서 해시는 임의의 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑하는 것을 말한다. 예를 들어 임의의 숫자에  % 10의 연산을 통해 나오는 숫자는 한 자리만을 나타내게 되므로 일종의 해시라고 볼 수 있다.

 

이 해시테이블은 몇가지 특징을 갖고 있는데 앞서 말했듯, 키와 값 쌍을 저장하고 키는 고유해야하기 때문에 중복된 키를 허용하지 않으며, 탐색, 삽입, 삭제에 있어서 O(1), 즉 상수시간 시간복잡도를 가지고 있다.

 

언뜻 보면 삽입,삭제에서 O(n)만큼의 시간복잡도를 가지는 List보다 여러면에서 빠르게 보이는 해시테이블이 결점 없이 좋아보인다. 하지만 이는 최선의 경우에 해당될 때이며 해시 테이블의 내부에 데이터가 쌓여감에 따라 해시 충돌이 발생하여 O(n)까지도 발생할 수 있게 된다.

 

 

해시 충돌이 발생하는 근본적인 이유는 키 값을 아무리 복잡하고 다양한 해시 함수의 처리 과정을 지나더라도 처리 이후에 나오게 된 해시는 그 값만이 가질 수 있는 고유한 값을 가지는 것이 아니기 때문이다. 즉 해시 충돌이란 해시함수가 서로 다른 입력 값에 대해 동일한 해시테이블 주소를 반환하는 것을 뜻한다. 

 

모든 입력 값에 대해 고유한 해시 값을 만드는 것은 불가능하며 충돌은 피할 수 없지만 이러한 해시 충돌을 해결하기 위한 방법은 두 가지가 존재한다.

 

첫번째는 체이닝이다. 체이닝은 충돌이 발생했을 때 각 해시 저장 위치에 링크드 리스트와 같은 구조로 데이터를 연결하여 저장하는 방법이다. 각 해시 저장 위치는 슬롯으로 사용되고 충돌이 발생한 경우 해당 슬롯에 링크드 리스트를 구성하여 데이터를 저장한다.

단어 뜻 그대로 충돌이 발생한 위치에 체인을 걸어서 중복된 자료들을 다른 곳으로 옮기는 대신 링크드 리스트를 추가로 연결하여 저장하는 방법인데 검색을 할 때는 해당 키의 해시 값을 계산하여 그 위치에 있는 연결 리스트를 탐색하여 필요한 데이터를 찾는 방식을 사용한다.

 

 

 

이러한 방식은 링크드 리스트를 사용할 때와 마찬가지로 메모리 구조를 추가적으로 사용하여 포인터 또는 연결 리스트 구조를 위한 오버헤드가 발생할 수 있으며 해당 연결 리스트가 길어질 경우 성능 저하가 될 수 있다는 단점을 가진다.

 

 

 

두번째 방법은 개방 주소법이다. 개방 주소법은 충돌이 발생할 경우 다른 빈 공간을 찾아 데이터를 저장하는 방식으로 해시 충돌시 선형 탐색, 제곱 탐색, 이중 해시 등의 다양한 방법을 통해 다른 빈 공간을 선정하게 된다.

이러한 방식은 주소가 겹쳐서 충돌이 발생하는 문제를 다른 빈 공간을 찾아 할당하는 방식으로 해결하기 때문에 메모리를 효율적으로 사용할 수 있으며 추가적인 연결리스트를 사용하지 않아도 된다는 장점이 있다.

또한 체이닝과 비교했을 때 캐시 효율성, 즉 캐시 적중률이 높다는 장점도 있는데 이는 연결 리스트를 사용하는 체이닝의 특성에 기반한다. 연결 리스트는 특성상 메모리 상에 흩어져서 구현되어 있기 때문에 캐시 메모리에서 캐시 라인의 성능을 떨어뜨릴 수 있다.

 

캐시 라인 : 캐시에서 데이터를 가져오는 최소 단위로 일반적으로 인접한 메모리 주소를 함께 가져오는데 연결 리스트의 경우 저장된 메모리끼리 붙어있지 않고 떨어져 있을 확률이 높으므로 캐시 라인에 필요한 데이터가 함께 로드되지 않을 수 있다.

 

 

 

이러한 개방 주소법도 단점이 존재하는데 우선 해시 테이블이 가지고 있는 자료가 많아질 수록 성능저하가 기하급수적으로 심해진다는 것이다.

 

70퍼 즈음까진 성능저하가 심하지 않다

 

개방 주소법은 충돌이 발생할 경우 해당 위치가 아닌 다른 빈 공간을 찾아 데이터를 삽입하는 방식인데 근처에 빈 공간이 없어질 경우 삽입을 위해 더 멀리까지 탐색해야 하는 상황이 발생하면, 해당 위치에 데이터가 뭉치는 클러스터링 문제가 일어나게 된다. 이렇게 공간 사용률이 높을 때 성능저하가 발생하게 되므로 사용률이 높을 때는 해시테이블의 크기를 늘리고 테이블 내의 데이터를 모두 다시 해싱하는 재해싱의 과정이 필요하다.

 

 

 

 

<Hashtable과 Dictionary>

 

 

해시테이블과 딕셔너리 모두 키와 값을 이용하며 내부적으론 해싱의 과정을 거치는 자료구조이지만 몇 가지 차이점이 존재한다.

해시테이블의 경우 키와 값으로 object 타입을 받기 때문에 어떤 자료형이던 key와 value로 사용할 수 있지만 그와 동시에 컴파일러가 코드를 확인하는 단계에서 형식의 유효성을 보장하지는 않는다는 점과 object타입의 사용시 발생하는 박싱,언박싱으로 인한 성능 저하가 발생할 수 있다는 단점을 갖고 있다.

 

여기서 형식의 유효성을 보장하지 않는다는 것은 컴파일러는 어떤 형식이든 받을 수 있지만, 실제로 실행 중에 올바른 형식이 사용되었는지에 대한 보장이 없다는 것이다. 이는 오동작이나 형식 변환시 발생하는 잠재적인 오류 가능성이 존재한다는 것을 뜻한다.

 

반대로 딕셔너리는 해시테이블과 반대로 object 타입을 받는 것이 아니라 generic을 사용하기 때문에 형식 안정성을 보장한다. 특정 형식의 키와 값만을 허용한다는 것이다.

또한 내부적으로 해시 충돌을 줄이고 성능을 높이기 위한 최적화가 적용되어 있어 성능적으로도 향상할 수 있다.