반응형
김희성의 개발자 면접 cs 강의/ 스터디
Hash Collision (해시 충돌)
- 서로 다른 Key 값에 대해서 Hash 함수의 반환 값이 동일한 경우를 말한다.
- key의 값의 경우의 수는 무한하지만 메모리상 버킷사이즈는 줄일 수 밖에 없다. (Java에서 HashMap<>()의 initial Capacity는 16으로 정의되어있음) 그 때 버킷사이즈를 늘리기위해 리사이징하는 과정에서 해시 충돌 발생
- 연산 속도도 빠르며, 해시 충돌이 가능 한 발생하지 않아야 성능이 좋은 Hash 함수라 할 수 있다.
Hash Collision (해시 충돌) 해결 방법
- Open Addressing
- 해시 충돌이 발생한 경우 비어있는 버킷을 찾아서 저장한다.
- 해시 충돌이 발생한 경우, 탐색/접근의 시간 복잡도가 O(N) 으로 증가한다.
- 비어있는 버킷을 찾는 알고리즘
- Linear Probing (선형 프로빙) (예시)
- Quadratic Probing (이차식 프로빙)
- Double Hashing (이중 해시)
- Chaining
- 해시 충돌이 발생한 버킷에 Linked List(Bin) 를 만들고, 해당 Linked List에 데이터를 저장한다.
- Linked List로 연결할 경우 접근/탐색 에 O(N)의 시간이 걸리기 때문에 성능 이 저하된다
- Linked List로 연결했을 경우 성능 저하 문제를 해결하기 위해 BST 를 사용할 수 있다.
- Java 에서는 Chaining 전략을 사용하며 해시 충돌이 발생한 버킷에 대해 7개 Bin 까지는 Linked List로, 8개 이상이 되면 BST (Red-Black Tree)로 변경한다. 반대로 8개에서 Remove에 의해 Bin의 개수가 줄어들면, 6개에서 Linked List로 변경한다.
Load Factor : 저장할 데이터의 수 대비 너무 작은 버킷 사이즈로 인해 성능이 저하되는 것을 방지하 기 위해 HashTable(HashMap)은 데이터가 어느 수준(Load Factor)이 이상 추가되면, 버킷의 사이즈를 늘리고(2배) Rehashing 을 수행한다.
- O(N)
반응형
'Backend > CS' 카테고리의 다른 글
[자료구조] 알고리즘 (3) | 2024.03.16 |
---|---|
[자료구조] Priority Queue (0) | 2024.03.13 |
[자료구조] HashTable (HashMap, unordered_map(set)) (0) | 2024.02.23 |
[자료구조] Queue, Deque, Stack (0) | 2024.02.22 |
[자료구조] Array, ArrayList (0) | 2024.02.21 |