[자바] HashMap 기초 개념

HashMap

자바에서는 다양한 상황에서 적용할 수 있는 자료구조 알고리즘을 적용해놓은 클래스들을 제공을 해주고 있습니다.

그 중 HashMap에 대한 개념을 알아보려합니다.

HashMap 은 해시함수를 통해 키와 값을 매핑하는 방식으로 데이터를 다루는 자료구조 알고리즘을 구현한 클래스 입니다.

ArrayList 클래스와 비교해보겠습니다.

ArrayList는 선형 자료구조 알고리즘을 배열을 통해 구현한 클래스로 배열을 생성하고 그 배열의 값에 객체의 주소를 넣는 방식으로 구현되어 있습니다.

아래와 같이 객체 3개가 있을 때

Object object_1 = "object_1";
Object object_2 = "object_2";
Object object_3 = "object_3";

(편의상 위 이미지처럼 각각 6번지, 12번지, 9번지의 메모리 주소에 객체가 할당되었다고 합시다.)

3개의 객체는 add() 메소드를 통해 배열의 index 0부터 차례로 각각의 주소가 담기게 됩니다.

List<Object> list = new ArrayList<Object>();        
list.add(object_1);
list.add(object_2);
list.add(object_3);

HashMap 은 어떨까요?

마찬가지로 아래 이미지와 같이 객체 3개가 있다고 합시다.

위 세 객체들의 메모리 주소를 HashTable에 담게되는데 순차적으로 0번 index부터 차례로 담았던 ArrayList와는 달리 담을 위치의 index를 "키" 를 통해 구하게 됩니다.

키를 해싱한 값, 즉 Hash함수("키"); 가 반환하는 값을 index로 정해서 객체의 메모리를 저장합니다.

아래와 같은 코드를 예로 들면

Map<String, Object> map = new HashMap<String, Object>();
map.put("key1", object_1);
map.put("key2", object_2);
map.put("key3", object_3);

아래와 같은 방식으로 저장된다는 말입니다.

해시 값이 겹친다면?

해시함수를 통해 index를 구하는 과정에서 index가 겹칠 수 있기 때문에 해시함수는 값을 고르게 반환하도록 만들어야 합니다.

그렇다고 하더라도 해시 값이 같을 수 있습니다.

Integer, Long과 같은 객체들은 각각이 의미하는 값 자체를 해시 값으로 사용한다면 충돌을 모두 피할 수도 있겠지만 String이나 POJO 에 대해 완전한 해시 함수(서로 다른 키에 대해 항상 다른 해시 값 갖는 해시 함수)는 거의 불가능 하다고 합니다.

그렇다면 HashMap에 요소를 추가하기위해 키를 해싱하였더니 그 자리에 다른 값이 들어있다면 어떻게 할까요?

다른 값을 반환하도록 다시 해싱하는 방법도 있지만 일반적으로 아래 그림과 같이 링크를 생성해서 LinkedList로 관리합니다.

이상적인 HashMap 구조

이상적인 해시함수 결과는 아래 그림과 같지만

적절하지 않은 해시함수를 사용한다면 아래 그림과 같은 경우가 될 수도 있습니다. 배보다 배꼽이 커진 경우입니다.

저장 공간에 대해

배열에서는 100개의 데이터가 저장된다고 확정되있다면 그에 맞게 100개 분의 메모리 공간만을 할당해놓는 것이 최적입니다.

하지만 HashMap에서는 100개의 데이터가 저장된다고 확정되있더라도 100개의 공간만을 할당한다면 해시 충돌 확률이 매우 높아 성능 저하로 이어지기 떄문에 100개 분의 메모리 공간보다 더욱 많은 공간을 할당해야 합니다.

좀 더 깊은 내용은 링크를 통해 확인하실 수 있습니다.