자료구조, 해쉬 테이블(Hash table)
Hash table 란 무엇인가?
해쉬 테이블은 자료 구조 중 제일 중요하다고 손꼽힐 정도로 기본적이면서도 실제 실무에서도 자주 쓰이는 자료 구조 중 하나이다. 가장 쉽게 표현할 수 있는 예제가 도서관에서의 책장을 표현할 수 있다. 총 9 칸으로 이뤄진 책장이라고 생각을 했을 때, 만약 도서관 사서 라면 책을 어떻게 구분을 할 수 있을까? 아마도 필자라면 ㄱ으로 시작하면 첫번째칸, ㄷ으로 시작하면 3번째칸 과 같은 규칙으로 한글 자음 순서대로 구분을 할 것이다.
이렇게 분류를 하게 되면 새로 추가를 할 때도 혹은 책을 찾을 때도 정해진 규칙대로 찾을 수 있어 쉬워질 것이다. 이처럼 해시 테이블은 데이터 검색을 효율적으로 하기 위해 사용되는 자료 구조이다.
Hash table 의 구조
해쉬 테이블은 키(key)와 값(value)이 한 쌍이 되는 데이터들의 집합체이다. 해쉬 테이블 은 아래의 사진과 같이 데이터를 hash function 을 통해 해싱을 한 후, 배열 안에 저장을 하는 형태이다.
위에서 배열 안에 저장을 하려면 미리 배열의 크기가 지정이 되어있어야 한다. 다른 한편으로는 해시 테이블의 성능은 공간을 팔아 얻어낸 성능이라고도 한다.
Hash table 의 개념
사람과 그 사람의 역할에 대한 데이터를 한번 해쉬 테이블을 이용하여 구현을 해보겠다. 역할은 Director, Designer, Developer, Project Owner(PO) 로 총 가지의 역할로 나누고 사람들을 할당해보겠다. 아마 아래와 같은 형태로 구현이 될 것이다.
이 중 Martin 이라는 사람의 역할을 찾아보려고 한다고 했을 때, 처음에는 Martin 이 어느 공간에 저장되어 있는지 알 수 가 없을 것이다. 그렇다면 Index 번호 0번부터 해서 탐색을 할 것이다. 이 경우 데이터를 읽으려 할때 걸리는 시간 복잡도는 O(n) 선형탐색 이다. 이러한 탐색은 데이터의 양이 비례해서 시간 복잡도가 늘어나는 구조라서 방대한 양의 데이터를 다루는 데에는 좋지 않은 구조이다. 이 때 배열 안에 저장을 할 때 해시 함수를 이용해 저장을 하면 위와 같은 문제점을 해결할 수 있다.
Hash function
해쉬 함수란 주어진 데이터를 고정 길이의 불규칙한 숫자로 변환하는 함수를 가르킨다. 여기에서 이 불규칙한 숫자는 데이터를 요약한 것이다. 대체적으로 해시 테이블과 함께 쓰여지며, 빠른 데이터 검색을 위한 소프트웨어에서 많이 사용된다.
해시 함수를 구현 방법에 대한 예제는 다음과 같다. 일단 Martin 이라는 데이터를 ASCII 코드로 변환을 해보겠다.
위의 ASCII 코드는 10진수를 이용해서 변환한 값이다. 이렇게해서 얻은 값을 각자 더한다.
77 + 97 + 114 + 116 + 105 + 110 = 619
여기에서 첫번째 방법은 배열의 length 값을 가지고 할당을 하는 방법이다. 위에서 말했듯 해시 테이블은 먼저 공간을 할당한다. 그렇다면 그 공간의 갯수를 구할 수 있을 것이고 그 공간 안에 위에서 구한 총합을 나누면 된다.
위와 같이 하게 되면 좋은 점은 어떠한 값이든 할당한 공간의 크기를 넘지는 못할 것이다.
다시 해시 테이블로 돌아와서 위의 John, Martin, Susan 그리고 Irene 을 해시 테이블 자료 구조 안에 저장을 하면 다음과 같을 것이다. (방식은 위에서 위에서 설명한 hash function 을 가지고 ACSII 코드 변환 후 저장하였다.)
John(74+111+104+110=399), Susan(83+117+115+97+110), Irene(73+114+101+110+101=499) 의 각각의 나머지는 John 은 4, Susan 은 0, Irene 은 4 이다. 차례대로 넣으면 Irene 까지는 문제가 없이 대입이 된다. 하지만 Irene 의 경우 값을 배열에 담으려고 하니, 이미 John 이 해당 Index 에 값이 들어가 있다. 이런 경우를 충돌 이라고 표현을 한다. 이 경우는 배열 안에 List 형태로 값을 넣어주면 된다.
위와 같이 충돌이 발생하는 경우 자료 구조 리스트를 사용해서 기존의 데이터 뒤에 연결하는 경우를 연쇄법 또는 체이닝 이라고 표현한다. 이 방법 외에도 충돌을 해결하는 방법은 개방 주소법 등 몇가지가 더 있다. 필요 혹은 상황에 따라서 충돌을 해결하면 된다.