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

+ Recent posts