<Ch8 - 컬렉션 API 개선>

[hongxeob]

범위

• 8.1 컬렉션 팩토리 : @dqgthb
• 8.2 리스트와 집합 처리 : @SeungAh-Hong
• 8.3 맵 처리 : @jeongyuneo
• 8.4 개선된 ConcurrentHashMap : @deingvelop

관련하여 본인이 잘 모르겠거나, 같이 알면 좋을만한 지식을 질문하고 아래 댓글로 남겨주세요.

질문들을 통해 같은 주제를 다양한 관점에서 보고, 더욱 깊은 지식 습득을 목표로 합니다!
이곳에서 질문에 관한 내용을 구체적으로 토의해도 좋습니다!

[jeongyuneo]

Hash 충돌 시 해결법

1. 체이닝(Chaining)
   버켓 내에 연결리스트(Linked List)를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 데이터들을 연결하는 방식이다.
2. 개방 주소법(Open Addressing)
   체이닝의 경우 버켓이 꽉 차더라도 연결리스트로 계속 늘려가기에, 데이터의 주소값은 바뀌지 않는다.(Closed Addressing)
   하지만 개방 주소법의 경우에는 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방 주소법이라고 한다. 개방 주소법은 대표적으로 3가지가 있다.
   • 선형 탐색(Linear Probing): 해시 충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터 삽입
   • 제곱 탐색(Quadratic Probing): 해시 충돌 시 제곱만큼 건너 뛴 버켓에 데이터 삽입
   • 이중 해시(Double Hasing): 해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용