Hash Table
hash는 내부적으로배열을 사용해 데이터를 저장해 빠른 검색 속도- 특정한 값을 검색 하는데 고유 인덱스로 접근해 평균적으로 시간 복잡도 O(1)
- collision이 발생하는 경우 O(n)
- 해시 함수를 이용해 데이터와 연관된 고유한 숫자를 만들어 이를 인덱스로 사용
Hash Function
- 해시 함수에 의해 반환된 데이터의 고유 숫자 값을
hashcode라고 함 - 저장되는 값들의 key 값을 해시 함수를 통해 작은 범위의 값들로 변경
- 어설픈 해시함수를 적용해 key 값을 결정하는 경우 동일한 key 값이 발생함 -> 하나의 key 값에 여러 데이터가 존재할 수 있게 됨 -> 이를
collision이라 부름 collistion: 서로 다른 두 개의 키가 같은 인덱스로 hashing되면 같은 곳에 저장할 수 없음
collision을 피해야하는 hash function 의 조건
일반적으로 좋은 hash function은 키의 일부를 참조해 해시 값을 만들지 않고 키 전체를 참조해 해시 값을 만들어 냄. 하지만, 좋은 해시 함수는 키의 특성을 따름
hash function을 무조건 1:1 로 만드는 것보다 collision을 최소화하는 방향으로 설계하고발생하는 collision을 대응하는 것이 더 중요
1:1로 대응되는 것이 거의 불가능하고 그런 hash function을 만들어봤자 일반적인 배열과 다른 점이 없고 메모리를 많이 차지하게 됨
collision이 많아질 수록 검색시 시간 복잡도가 O(1) -> O(n) 에 가까워짐
hashing된 인덱스에 이미 다른 값이 있다면 새 데이터를 저장할 다른 위치를 찾은 뒤에 저장할 수 있음 -> 충돌 해결
충돌(collision) 해결 방법
기본적인 2가지 방법
Open Address 방식(개방 주소법)
해시 충돌이 발생하면, 다른 해시 버킷에 해당 자료를 삽입하는 방식
다른 해시 버킷을 찾는 방법 3가지
1. Linear Probing 순차적으로 탐색해 비어있는 버킷을 찾을 때까지 진행
2. Quadratic probing 2차 함수를 이용해 탐색 위치 찾음
3. Double hashing probing 하나의 해시 함수에서 충돌 발생시 2차 해시함수를 사용해 새로운 주소 할당
Separate Chaining 방식(분리 연결법)
일반적으로 Open Addressing은 Separate Chaning보다 느림
개방 주소의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst case 발생 빈도가 높아짐
반면, 분리 연결 방식은 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조절할 수 있다면 Worst case에 가까워 지는 빈도를 줄일 수 있음 Java7의 경우 해당 방식 사용해 HashMap 구현
Separate Chaining 방식의 2가지 구현 방식
- LinkedList 활용 - 각각의 버킷들을 연결리스트로 만들어 충돌이 발생하는 경우 해당 bucket의 list에 추가, 연결리스트를 활용해 삭제, 삽입이 간단하지만 작은 데이터들을 저장할 때 연결리스트 자체의 오버헤드가 부담. OpenAddress 방식에 비해 테이블의 확장을 늦춤
- Tree 활용(Red Black Tree) - 기본적인 알고리즘은 Separate Chaining과 동일하며 연결 리스트 대신 트리를 사용하는 방식, 연결 리스트를 사용할 것인가 트리를 사용할 것인가의 기준은 하나의 해시 버킷에 할당된 key-value 쌍의 개수, 데이터의 개수가 적으면 연결리스트를 사용하는 것이 맞음. 트리는 기본적으로 메모리를 많이 사용하기 때문. 데이터 개수가 적을 때 Worst case의 성능 차이가 거의 없음
데이터가 적다는 것의 기준? - key-value 쌍의 개수.
6개와 8개로 나뉨
7은 어디로??? 6개에서 7이 되면 트리가 되고 7에서 6이 되면 링크드리스트로 변경하면 비용이 너무 많이 할당됨.
Open address vs separate chanining
둘 다 worst case에서 O(m)
Open address는 연속된 공간에 데이터가 저장되기 때문에 캐시 효율이 높음
데이터의 개수가 충분히 적은 경우 open address를 사용하는 것이 좋음
보조 해시 함수
key의 해시 값을 변형해 해시 충돌 가능성을 줄임
separate chaining 방식을 사용할 때 함께 사용되며 worst case 에 가까워지는 경우를 줄여줌
Resize
해시 버킷의 개수가 적으면 메모리 사용을 줄일 수 있지만 충돌이 발생할 확률이 상승.
hash map은 key-value 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두배로 늘려 ㅊ충돌 문제를 어느정도 해결
참고자료
