Hash

자바의 컬렉션에서 객체의 해시값을 사용하는 자료구조가 있다. 

대표적으로 HashTable을 예로 오늘 설명하겠습니다~

 

자,, 우선 해시? 해싱? 

 

Hash

해시란 임의의 데이터의 길이를 고정된 데이터의 길이로 변환하는 데이터 변환 기법중에 하나다. 이 변환 과정에서 사용하는 함수를 해시 함수라고 하고 변한하는 과정을 해싱이라고 한다. 

 

그렇다면 왜 임의의 길이를 고정된 데이터의 길이로 변환할 필요가 있을까?

해시 함수의 키로 들어온 값으로 만든 해시 코드는 정수이기 때문에 배열 공간을 고정된 크기만큼 만들어둔 후(해시 버킷) 해시 코드를 배열의 크기로 나머지 연산 후 배열에 나누어 담을 수 있게 되면 이후 검색시 다이렉트로 검색이 가능하기 때문에 O(1)의 시간복잡도로 접근이 가능하다. 

 

 

그런데 이 경우 객체의 key로 입력한 객체의 hashcode 함수를 통해 나온 값으로 맵핑한 결과가 다른 객체와 동일한 경우가 생기는데 이것을 hash collision이라 한다. 

이렇게 해시 충돌이 생기면 버킷 내부에서 링크드 리스트로 연결(chaning)이 되는데 

이 경우 너무 많은 key가 해시 충돌로 같은 버킷에 들어가게 되면 결국 검색시에 최대 O(n) 시간 복잡도가 소요된다. 

 

해시 충돌의 다른 방식으로 Open Adrressing이 있는데 

이는 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식으로 

• 선형 탐색: 해시충돌시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입
• 제곱 탐색: 해시충돌시 제곱만큼 건너뛴 버켓에 데이터를 삽입
• 이중 해시: 해시충돌시 다른 해시함수를 한 번 더 적요한 결과를 이용

이 방식의 장점은

• 외부 저장공간 없이 해시테이블 안에서 데이터 저장 및 처리 가능
• 외부 저장공간에서의 추가적인 작업이 없다.

단점은

• 해시함수의 성능에 전체 해시테이블의 성능이 결정된다.
• 데이터의 길이가 늘어나면 그에 맞는 저장소를 마련해야한다.

 

두 방식 비교

 

위의 chaning 방식은 jdk7까지의 구현은 조금씩 달라졌지만 알고리즘은 링크드 리스트를 사용했었는데

jdk8부터는 일정 개수 이 하의 컬렉션에서 객체의 해시값을 사용하는 자료구조가 있다.