💡 Map
- K - V (Key - Value) 쌍 형태의 데이터 쌍으로 저장하는 자료구조
- Key는 해시를 하지만 Value는 해시를 하지 X
- Key를 이용해서 Value를 얻는 식으로 주로 사용
- Key는 중복될 수 없지만, Value는 중복 가능
- 동일한 Key에 데이터를 넣으면 기존 Value가 업데이트 됨
💡 Set
- Key만 저장하는 자료구조
- Map과 동일하게 Key는 중복될 수 없음 => 중복 제거용으로 자주 사용!
💡 HashMap / HashSet
▶️ O(1)
- 어떤 데이터(Key)가 존재하는지
- Key에 대한 Value에 접근 / 삭제
- Key - Value 저장
▶️ O(N)
- 어떠한 Value가 존재하는지 탐색
💡 해시 충돌
- 다른 내용의 데이터가 같은 Key를 갖는 것
다음의 상황을 가정해 보자.
1~21억개의 데이터가 hash를 통과한다. 하지만 해시 테이블의 사이즈 10,000이다.
이런 경우엔 해시 충돌이 일어날 수 밖에 없다.
해시 충돌이 많아지면 해시 테이블의 성능이 떨어진다.
💡 체이닝(Chaining)
해시 충돌 전략 중 하나인 체이닝(Chaining)에 대해 설명하겠다.
해시 충돌이 발생할 경우 Linked list에 데이터를 추가하는 방식이다.
해시 충돌이 가능한 적게 일어나도록 해야한다.
왜❓❕
시간 복잡도를 줄이기 위해 해시 테이블을 사용하는 건데,
해시 충돌이 많이 일어나게 되면 탐색 과정이 O(N)으로 시간복잡도가 커진다!
(Linked list에 연결된 모든 원소를 탐색해야 하기 때문에)
자바 8 버전부터는충돌이 8개 이상이면, 이진 탐색 트리로 바꾸어 O(logN)만에 가능하게 함
'알고리즘' 카테고리의 다른 글
[알고리즘] BFS (너비 우선 탐색)이란? (0) | 2024.01.07 |
---|---|
[알고리즘] CH01. Analyzing Algorithms and Problems (0) | 2023.03.04 |
[알고리즘] 다이나믹 프로그래밍 (0) | 2023.03.03 |
[알고리즘] sort - 안정정렬/불안정정렬 (0) | 2023.02.26 |