해시 테이블(Hash Table) |
데이터를 담을 테이블을 미리 크게 만들어두고 입력받은 데이터를 해시함수로 해시한 후 나온 해시값을 이용해 key-value 구조로 저장하는 자료구조
과일과 가격을 표로 저장한다고 하면
| 과일 | 가격 |
| 사과 | 1000 |
| 포도 | 1500 |
| 수박 | 5000 |
위와 같은 형태가 될텐데 만약 과일의 종류가 수천만가지가 된다면 표에서 사과를 찾기 위해 너무 오랜 시간이 걸릴 수 있음
반면 Hash Table이라면 각각의 이름에 해싱을 해서 Key(유일한 값)를 만들고 그 키를 이용해서 자료에 접근하는 방식으로 O(1)로 접근이 가능
방법을 간단히 표현하자면 "사과"라는 텍스트를 어떤 해싱함수에 넣으면 결과로 6이 나온다고 해본다면 6번 key에 접근해서 해당 value를 찾을 수 있음
| key | value |
| ... | |
| 5 | |
| 6 | 1000 |
| 7 | |
| ... |
용어정리 |
1) Key
- 데이터의 저장과 탐색을 위한 고유의 값
- 데이터 저장시 데이터가 해시함수에 입력되고 그 결과값으로 key를 얻어 해당 key값의 위치에 데이터가 저장된다.
2) bucket
- 버킷은 Hash Table의 크기이자 Hash Function의 결과범위이다.
- 아래 그림에서 bucket은 갈색으로 칠해진 부분으로 bucket의 크기는 4이고 bucket의 범위는 0~3이다.
3) slot
- slot은 한개의 bucket에 저장될 키 값의 개수이다.
- 위의 그림에서는 slot의 크기는 3이다.
- 결론적으로 위 그림의 Hash Table의 저장공간은 12칸이다.
- slot은 위 사진처럼 정적배열형태로 만들어질 수도 있고, 동적할당되는 리스트형태로 만들 수도 있다.
4) Hash Function
- 해시함수란 data를 해시로 변환하는 함수이다.
- data를 해시함수를 통해 key로 변환하고 해당 key의 위치에 값을 보관하는 것
Hash Table의 치명적 단점 |
Hash의 충돌
Hash Table은 O(1)로 값에 접근할 수 있는 엄청난 속도를 가졌지만 이는 Table이 비어있을때에만 가능하다.
예를들어 apple을 해싱한 결과로 840이 나와서 840위치에 값을 넣었다고 해보자.
그런데 그 후 수천만/수천억개의 단어들을 해싱하다보면 apple이 아닌 다른 단어도 해싱한 결과가 840이 나오게 될 수 있다.
이런 상황을 Hash의 충돌이라고 한다.
이 경우 새로운 공간을 찾아가야하는데 대부분의 공간이 가득차있다면 모든 칸을 확인하는 지경에 이를 수 있으므로 O(1)이 아닌 O(N)이 될 수 있다.
또한 Hash 충돌이 한번 일어나게 되면 그 지역에서는 충돌이 계속 일어나게 되므로 그 근처에 자료가 몰리게 된다.
그러므로 Key의 분포도가 최대한 넓어질 수 있는 Hashing 알고리즘을 만들어야 한다.
Hash 충돌시 해결방법
그러나 아무리 좋은 Hashing 알고리즘을 만들어도 저장할수 있는 공간에는 늘 한계가 있으므로 Hash 충돌 발생시 해결법이 있다.
- 개방주소법(Open addressing)
- slot이 정적배열인 경우 사용하는것으로 예상됨
- 충돌이 일어난 인덱스의 모든 slot이 가득차있다면 다음 인덱스를 확인해서 비어있다면 해당 위치에 삽입
- Index만 증가시켜주면 되므로 안정적이고 쉬운 방법
- 체이닝(Chaning)
- slot이 동적할당이 가능한 Linked list인 경우 사용하는것으로 예상됨
- 충돌이 일어난 지점을 사용하되 Linked list로 묶는 방법
- 해시테이블 이외의 주소를 추가로 할당해서 확장해서 사용할 수 있다는 장점이 있음
개방주소법은 인덱스만 증가시켜 주면 되므로 안정적이고 쉬운 방법이고, 체이닝은 해시테이블 이외의 주소를 추가로 할당해서 확장해서 사용할 수 있다는 장점이 있음
그러나…
하지만 위의 방법들도 임시방편일 뿐 문제를 완벽히 해결해주는것은 아니다.
그러므로 기억장소 공간 사용비율이 75%를 넘어가면 Hash Table의 크기를 resizing하는것이 좋다.
다만 문제는 더 큰 해쉬결과값들이 나오는 해쉬함수를 새로 적용해야 하므로 기존의 값들도 다 새로 해싱해야하는 비효율이 발생한다.
Hash의 동작원리 |
Hash에서 Key를 생성하기 위한 알고리즘이 여러 종류 있는데 그 중 유명한 알고리즘으로는 MD-5나 SHA가 있음
해시를 만드는 예시)
"apple"이라는 문자열을 해싱하려고 할 때, 소수 5381을 이용해본다면
| 문자 | a | p | p | l | e |
| ASCII | 97 | 112 | 112 | 108 | 101 |
절차 1) Hash 값을 왼쪽으로 5번 비트연산시킨다.
절차 2) 원본 Hash 값을 더한다.
절차 3) 한 문자의 ASCII 값을 더한다.
절차 4) 위의 결과를 모둔 문자에 대해 반복한다.
절차 5) 최종 값이 해시테이블의 범위를 벗어난다면 나머지 연산을 취한다.
Hash 테이블의 최대 크기를 8191라고 가정한다면 위의 절차들은 아래와 같다.
| 문자 | a | p | p | l | e |
| ASCII | 97 | 112 | 112 | 108 | 101 |
즉 "apple"이 해싱된 결과는 840이며, apple의 key값이 곧 840이 되는 것
테이블의 840번 키에 들어있는 value로 바로 접근이 가능하게 되는 것이다.
헷갈릴 수 있는 것 |
C++ STL의 map은 해시테이블이 아님
map은 과거에는 이진탐색트리로 구현되었었고, 최근엔 레드블랙트리로 구현되었다고 함
map은 자료를 정렬해서 보관하지만 HashMap은 자료를 정렬하지 않음.
그러므로 map은 탐색할때 O(logN)을 보장하지만, HashMap은 Hash충돌때문애 O(1)을 보장하지 않음
※ 참고문헌