HashMap HashCollision

HashMap?

컬렉션 프레임워크의 Map인터페이스를 구현한 클래스

key와 value를 묶어서 하나의 데이터 Entry로 저장
hasing을 사용해 많은 양의 데이터 검색 하기 좋다

해싱과 해시함수

해싱이란?
해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법
해싱에서 사용하는 자료구조는 배열과 링크드리스트의 조합

데이터를 찾는 과정

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게되고
-> 그곳에 저장되어 있는 링크드 리스트에 저장하게 된다

해시의 성능

• 링크드 리스트의 크기가 커질수록 속도 저하
• 배열은 크기가 커져도 된다
  

왼쪽이 성능좋은 해시 오른쪽이 성능 안좋은 해시(노드 크기는 신경 ㄴㄴ)

해시의 성능을 좋게 하려면?

1. 링크드 리스트에 최소한의 데이터만 들어있는게 좋다
2. HashMap의 크기를 적절하게 지정한다
3. 해시함수가 서로 다른 키에 대해 중복된 해시코드 반환을 최소화해야함

java에서 해싱구현은 어떻게 하는지??
Object클래스에 정의된 hashCode를 함수로 사용한다(객체의 주소를 이용하는 알고리즘)

---

HashMap Collision

해시충돌이란?

다른 내용의 데이터를 해시함수에 넣었을 때 같은 값을 같게 될때 발생

해시충돌 해결하기

1. 체이닝
   연결 리스트로 데이터를 연결하는 방식
   

• 장점
  1. 연결 리스트만 사용하면 된다
  2. 성능 저하가 Linear 하게 발생

2. 개방주소법
   해시충돌이 일어나면 다른 버킷에 데이터를 삽입
   1. 선형탐색
   2. 제곱탐색
   3. 이중해시

• 장점
  1. 포인터 X 추가적인 저장공간 X
  2. 삽입 삭제시 오버헤드 적음
  3. 데이터 적을때 유리함

---

Q
HashMap에 대해서 설명해주시고, Hash Collision 발생 시 자바는 어떻게 대처하나요?
A
HashMap은 자바의 Collection중 하나인 Map인터페이스를 구현한 클래스로 key와 value를 묶어서 하나의 데이터 Entry로 저장합니다.
중복을 허용하지 않으며 hasing을 사용해 많은 양의 데이터 검색 하기 좋습니다.

해시충돌은 서로다른 데이터를 해시함수에 넣었을 때 같은 값을 가지며 발생합니다.
Hash Collision 발생시 자바는 체이닝과 개방주소법으로 대처합니다
체이닝은 기존 데이터 에 새로운 데이터를 연결리스트 형식으롤 연결하는 방법입니다.
개방주소법은 비어있는 인덱스(버킷)에 값을 넣는 방법 입니다.
선형탐색, 제곱탐색, 이중해시 등이 있으며 삽입 삭제시 오버헤드가 적고 추가적인 저장공간이 필요없다는 장점이 있습니다.