자바 해시맵(HashMap)

자바 해시맵(HashMap)

해시맵(HashMap)과 해시테이블(HashTable)을 정의하면 "키에 대한 해시 값을 사용하여 값을 저장하고 조회하며, 키-값 쌍의 개수에 따라 동적으로 크기가 증기하는 associative array"라고 할 수 있다. 

어떤 수들 N에 대하여 M크기만큼의 배열을 만들고 해시함수를 통해 index를 계산해서 O(1) 시간에 접근 가능하게 만든다. 다음은 간단히 해시 함수 함수를 구현한 것이다.

int index = X.hashcode() % M;

해시 충돌(Hash Collision)

해시함수를 통해 계산된 index값에 이미 다른 자료가 저장되어 있는 경우 이를 해시 충돌이라고 한다. 

자바에서 해시 충돌을 막는 두 가지  방법

Open Addresing 방법

데이터를 삽입하려는 해시 버킷이 이미 사용 중이라면 다른 해시 버킷에 해당 데이터를 삽입하는 방식이다. 데이터를 저장, 조회할 해시 버킷을 찾을 때는 선형 검색법(linear probing), 2차 검색법(quadratic probing) 등의 방법을 사용한다. 

* Open Addressing을 해결하는 4가지 방법

(1) 선형 탐사

해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동합니다.

(2) 제곱 탐사

선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다르다.

(3) 이중 해싱

클러스터 방지를 위해, 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 또 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용

(4) 재해싱

해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것

Seperate Chaining 방법

해시함수를 통해 도출된 인덱스가 서로 같은 자료들을 연결 리스트(Linked List)로 연결하는 방법이다.

자바 7까지는 해시충돌난 자료들을 연결리스트로 연결했지만, 자바 8에서는 자료의 개수가 8개 이상이 될 때는 트리 형태로 만든다. 또 6개로 줄어들면 다시 링크드 리스트로 만든다. 해시 충돌 나는 자료들의 개수가 많아지면 트리를 통해 특별한 저장공간을 사용하지만 빠른 성능으로 값을 찾아낼 수 있다.