[자료구조] HashMap

▶ Java  Collection 자료구조 전체 구조

 

 

▶ HashMap이란? 

Key와 value 쌍으로 구성된 비선형 자료구조이다. 

 

▶ 언제 쓰나? 

- Key : Value 형태로 저장되기 때문에 Key를 직접 설정하고 접근하는 일이 잦을 때 사용한다. 

- 검색, 삽입, 제거 연산의 시간 복잡도가 O(1)이기 때문에 해당 연산이 많은 경우 효율적이다. 

- 하지만 들어온 순서를 반영하지 않기 때문에 들어온 순서 정보가 필요 없을 때 사용해야 한다. 

 

▶ 어떻게 쓰나? 

선형 자료구조가 아니기 때문에 버킷에 저장되는 위치를 Hash 함수를 이용해 구한다. 

버킷의 해당 인덱스에 데이터를 저장한다. 

 

▶ HashMap의 문제점 - 충돌

이 때 Key는 String이 될 수도 있고, 객체도 될 수 있기 때문에 가능한 경우가 거의 무한에 가깝다. 

하지만 인덱스의 경우 한정된 크기이기 때문에 어쩔 수 없이 충돌이 발생한다. 

 

이 문제를 해결하기 위한 방법이 2가지가 있는데

Open Addressing과 Seperate Chaining이다.

 

Open Adderssing은 하나의 버킷을 이용하고, 충돌이 나는 경우 다음 인덱스에 저장을 하는 방법이다.

 

Java의 경우 Seperate Chaining 방법을 사용하는데

이는 충돌이 날 경우 linked list나 Red-Black Tree로 연결하여 저장하는 것이다. 

특정 숫자가 넘아갔을 때 탐색의 효율성을 높이기 위해 linked list를 Red-Black Tree로 바꾸어 저장한다.

 

또한 전체 버킷의 75% 이상이 채워지면 버킷의 크기를 2배늘리고 shift 연산을 통해 모든 데이터의 위치를 재할당한다.