minjgziii

💡 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)만에 가능하게 함