[강의노트] 해시 테이블 - 1

해시 테이블 - 1

해시 테이블에 대한 강의 내용을 정리한 포스팅입니다. 개인 공부를 위해 작성되는 게시글이니 참고해주세요.

 

해시테이블

해시테이블은 키 - 주소 매핑에 의해 구현된 사전 ADT 이다. (이전에 선형트리 사전, 이진탐색트리 사전을 배웠었다)

키 - 주소 매핑에 대한 예시를 들면 학번을 키 값으로 설정해서 학번에 따라 방 배정을 했을경우 학번 - 방번호에 대한 매핑이 된 것

예시로는 컴파일러의 심볼 테이블, 환경변수들의 레지스트리 등이 있다.

 

해시테이블 은 버켓 배열 + 해시 함수이다. 위의 예시에서 방 이 버켓 배열이라면, 학번을 3으로 나누었을때 나머지에 따라서 방을 분배하자 와 같은 아이디어가 해시함수에 해당된다고 할 수 있다.

 

항목들의 키를 주소(즉, 배열 첨자)로 매핑함으로서 1차원 배열에 사전 항목들을 저장한다.

 

성능은 탐색, 삽입 삭제에서는 O(n)이 최악시간, 기대시간은 O(1)

버켓 배열

버켓 배열에 대한 설명은 사진을 참조하자. 크게 어려운 개념이 없으므로 내용 생략.

 

 

해시함수

키 값이 주어졌을때 버켓 배열로 어떻게 매핑할 것인가? 에 대한 로직을 의미

 

사전의 항목 (k, e)는 키값 k와 키에 대응하는 원소 e로 이루어져있다.

이때 사전을 해시테이블로 구 현하기 위해, 테이블로 원소 e 값을 옮겨야하는데 그때 해시함수 h를 사용한다.

 

항목의 키값 k에 대해 i= h(k) 를 계산하고 테이블의 i 인덱스에 원소 e 값을 저장한다.

다시 말하면, 항목의 키 k에 대한 해시값을 인덱스로 사용해서 테이블에 항목의 원소를 저장한다.

간단한 예시를 알아보자.

아래의 예시에서 사용한 해시함수 로직은 단순히 전화번호의 마지막 4자리의 숫자에 맞게 테이블에 삽입하는 로직을 사용했다.  

 

해시함수에 대해서 상세하게 알아보자

해시함수는 두 함수의 복합체로 이루어져있다. 해시코드맵과 압축맵 두 함수로 이루어져있는데, 해시코드맵은 키를 정수 값으로 바꾸는 과정이고, 압축맵은 전환된 정수값을 테이블 인덱스에 매핑하는 과정이다.

 

해시코드맵과 압축맵에 대한 예시를 보고 이해하자. 

학번의 경우 마지막 4자리 수를 취하는 것이 해시코드맵

식별자의 경우 문자 합을 통해 정수를 뽑아내는 것이 해시코드맵

 

이러한 해시코드맵의 로직에 대한 몇가지 방법이 존재한다.먼저 메모리주소와 정수캐스트에 대해서 알아보자

메모리주소는 비트로 이루어진 2진수 주소를 10진수로 바꾸는 과정

키 개체가 가지는 메모리의 주소를 정수로 바꾸는 것.

 

정수 캐스트는 키의 비트 값을 10진수 정수로 바꾸는 과정

 

요소합은 예를들어 total 이라는 키가 있을때, 각 알파벳의 대응되는 값을 합하는 것

이 경우 문자의 순서에 의미가 있는 문자열 키를 쓰게되면, 다른 문자열(구분이 필요한)인데 합이 같아지는 경우가 있으므로 부적합함

 

다항누적은 요소합을 보완한 방법으로, 요소합에 각 요소의 위치에 따른 별도 계산을 추가해서

위의 예시에서는 p(z) 에 대한 식을 활용함.

이렇게 해서 요소합의 단점을 보완한 것

 

다음으로 압축맵은 해시함수의 h2함수로 두번째 과정을 말하는 것이다.

얻어낸 정수값을 0,... M-1 의 버켓배열에 매핑하는 것

 

충돌해결

위에서 해시함수를 통해 키값을 매핑하는 과정을 배웠는데, 충돌이란 키를 해시화 했을때 그 결과가 같은 경우를 말함

그림으로 나타내면 다음과 같음

그럼 충돌을 어떻게 해결할 수 있을까?

분리연쇄법

그림을 보면 이해하기 쉽다. 버켓에 바로 저장하는 것이 아니라, 포인터를 이용해서 연결리스트를 달아두는 것

즉 버켓 A[i]는 리스트 L 에 대한 참조를 저장하고 있는 것이다. (실제 항목을 저장하는 것이 아닌)

 

이렇게하면 단순하고, 빠르다는 장점이 있지만 테이블 외부의 추가적인 리스트를 요구한다

예시를 살펴보자.

참고에 나와있는 설명은, 만약 리스트에 항목을 추가할 경우

테일포인터를 유지한다면 테일포인터를 통해 맨 뒤에 삽입하고

유지하지 않는다면 리스트 맨 앞에 삽입하는 것이 유리하다는 뜻.

findElement 에서 반환 값의 findElement는 서로 다른 것임에 주의하자

A[v].findElement(k)는  버켓배열에 연결되어있는 리스트에서 원소 탐색하는 것

 

개방주소법

충돌 항목을 테이블의 다른 셀에 저장하는 방법이다. 이때 다른 셀에 저장하는 방식을 바로 다음 비어있는 셀에 넣거나

몇칸 이동한 셀에 넣거나 등의 여러 방식을 선택할 수 있다.

 

외부 메모리를 사용하지않으므로, 공간을 절약할 수 있지만 삭제가 어렵다고 한다.

 

삭제가 어려운 이유는 1~10번 방에 충돌 항목들을 차례대로 넣었다고 가정하자. 이때 3번방의 항목을 삭제했을 때,  empty 상태가 되므로 그 다음 탐색 실행에서 3번방까지만 가도 탐색이 끝났다고 판단할 수 있다. 

이러한 오류를 방지하기 위해 삭제 알고리즘을 짜야해서 조금 어려워짐. 상세한 내용은 후에 다루게 된다

 

세가지의 개방주소법을 알아보자.

 

1. 선형조사법

선형조사법은 바로 다음의 비어있는 셀에 저장해서 충돌을 처리하는 방법.

즉 다음 순서에 의해 버켓을 조사한다.

위의 예시가 진행된 결과 군집화가 된 모습

 

2. 2차 조사법

바로 다음의 비어있는 셀이 아닌, 제곱으로 증가하는 형태 순서에 의해 버켓을 조사

0 -> 1 -> 4 -> 9 . . .

이 경우에 M이 소수가 아니거나 버켓 배열이 반 이상차면

비어 있는 버켓이 남아 있더라도 찾지 못할 수 있다.

선형 조사법 결과 생성된 1차군집화를 피하지만, 2차 군집화가 형성됨

 

3. 이중해싱

점점 충돌해결의 구조가 복잡해진다.

잠깐 전의 내용을 상기해보자.

 

1번 선형조사법 --> 단순히 다음 비어있는 셀에 저장

2번 2차조사법 --> 제곱꼴로 증가하면서 셀 조사

3번 이중해싱 --> 조사순서를 정해주는 h'을 두어서 결과에 맞게 셀 조사

 

즉 해싱함수 h 이외에 충돌시에 몇번째 뒤에 넣을지 정해주는 h' 함수를 추가로 두는것

이렇게하면 같은 해시값을 가지는 키들도( 즉 충돌이 일어나는 경우에) 상이한 조사값을 가지기때문에

군집화가 최소화 된다.

 

 

 

위의 내용에 대한 수도코드 알고리즘이다.

여기서 getNextBucket 메소드에 선형조사, 2차조사 , 이중해시 중 하나가 쓰이게 됨