해싱과 해싱함수

자바의정석 3rd Edition 2권을 참조하였습니다.

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=76083001 

Java의 정석

 

해싱이란 해시함수(hash function)을 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법

해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.

해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable 등이 있다.

Hashtable은 컬렉션 프레임워크가 도입되면서 HashMap으로 대체되었으나 이전 소스와의 호환성 문제로 남겨 두고 있다.

가능하면 Hashtable대신 HashMap을 사용하자.

 

해싱에서 사용하는 자료구조는 배열과 링크드 리스트의 조합으로 되어있다. 

 

 

저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장하게 된다.

주민번호 맨 앞자리인 생년을 기준으로 데이터를 분류해서 10개의 서랍(배열)에 나눠 담는 방법

이렇게 분류하면 환자의 주민번호로 태어난 년대를 계산해서 어느 서랍에서 찾아야 할지 쉽게 알 수 있다.

아래 그림은 79년생 환자의 주민번호를 키로 해시함수를 통해 7이라는 해시코드를 얻은 후,

배열의 7번째 요소에 저장된 링크드 리스트에서 원하는 데이터를 검색하는 과정

링크드 리스트는 검색에 불리한 자료구조이기 때문에 링크드 리스트의 크기가 커질수록 검색속도가 떨어진다.

배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size * n

해싱을 구현하는 과정에서 제일 중요한 것은 해싱함수의 알고리즘이며, 이 예에서 사용된 해시함수의 알고리즘은 주어진 키(주민번호)의 첫 번째 문자를 뽑아서 정수로 반환하기만 하면 되므로 아래의 코드와 같이 표현 가능하다.

int hashFunction(String key) {
	return Integer.parseInt(key.substring(0,1);
}

간단한 알고리즘인 만큼 성능이 좋지 않아 중복된 해시코드를 반환하는 경우가 많다.

 

실제로는 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용

hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 생성하기에

모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 훌륭한 방법이다.

 

String클래스의 경우 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다.

그래서 다른 String인스턴스라도 같은 내용의 문자열이면 hashCode()의 결과가 같다.

서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다.

HashMap에서도 같은 방법으로 객체를 구별하며, 이미 존재하는 키에 대한 값을 저장하면 기존의 값을 덮어쓴다.

그래서 새로운 클래스를 정의할 때 equals()를 재정의 오버라이딩해야 한다면 hashCode()도 같이 재정의해서 equals()의 결과가 true인 두 객체의 hashCode()의 결과값이 항상 같도록 해주어야 한다.

그렇지 않다면 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 equal()의 호출 결과가 true지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장할 것이다.