HashMap이란?

HashMap이란?

 

일단, 이름 자체에서 내부 구현을 추측해보았다. Hash란 인덱스를 통해 데이터의 저장위치를 찾는 알고리즘이고, Map이란 key와 value 쌍으로 데이터를 저장하는 방식이다. 그럼 이 둘을 조합한 HashMap은  key와 value의 쌍으로 이루어진 데이터를 인덱스를 이용해 저장 또는 검색하는 자료구조다.

 

해시의 종류는 크게 두가지로 나뉜다. 하나는 Open Addressing이고 다른 하나는 Separate Chaining이다. java에서 실제로 사용하는 해싱기법은 Separate Chaining이므로 이 부분만 정리하도록 하겠다. 메모리는 한정적이기 때문에 현실적으로 모든 객체에 대해 고유한 인덱스를 갖게 하는 해시함수를 설계하는 건 비효율적이다. 한 WAS에서도 여러 HashMap자료구조를 사용할 수 있는데 미리 확보할 해싱메모리가 너무 크면 안 좋은 것이다. (메모리 크기에 따라 해싱함수를 적절하게 짜는 게 해싱의 핵심이라고 한다) 필연적으로 해시충돌은 발생할 수밖에 없는데 이때 충돌한 데이터를 chain 형식으로 엮는 방법이 separate chaining이다

위 그림은 인덱스가 같은 값을 연결리스트 형태로 저장한 구조다.

 

인덱스는 어떻게?

key와 value 형태의 데이터를 저장할 때 인덱스는 key의 해시코드값을 버킷개수로 나눈 나머지를 이용한다. 버킷의 개수는 데이터의 양이 늘어남에 따라 2배씩 늘어나게 되는데 2의 배수로 구한 나머지 값은 bit단위로 보게 되면 모든 bit를 효율적으로 이용하지 못하고 특정한 하위 몇 bit만 계산을 위해 사용됨을 알 수 있다. 이는 결국 해시충돌이 특정 버킷에만 밀집하게 되는 결과를 초래하게 된다.

 

 

보조 해시

이를 해결하기 위해 객체의 해시코드를 중간에 조작하는 보조해시를 이용하기도 한다.

 

 

연결리스트에서 트리로

그럼에도 충돌된 데이터가 일정량 이상 늘어나게 되면 결국 검색에서 매우 비효율적인 자료구조가 된다. 한 버킷에서 원하는 데이터를 찾기 위해 O(n)이 소요되기 때문이다. 이를 해결하기 위해 데이터의 개수가 일정량 이상이 되면 연결리스트 형식의 separate chaining을 트리구조로 전환하여 성능을 개선한다. 다만, 트리구조는 메모리 소모가 크기 때문에 상대적으로 데이터의 개수가 적은 경우 연결리스트 형식을 사용하도록 설계되어 있다.