Java의 정석 3판을 보며 공부한 내용을 정리하였습니다.
남궁성님께 많이 배우고 있습니다.
해싱과 해싱함수
해싱(Hashing)이란 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법이다.
-
해시함수는 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
-
해싱을 구현한 클래스로는 HashSet, HashMap, HashTable 등이 있다.
-
Hashtable은 컬렉션 프레임웍이 도입되면서 HashMap으로 대체되었으나, 이전 소스와의 호환성 문제로 남겨둔 것이다.
(가능하면 Hashtable 대신 HashMap을 사용하자!)
해싱에서 사용하는 자료구조는 다음과 같이 배열과 링크드 리스트의 조합으로 되어 있다.
그림 1. 배열과 링크드 리스트의 조합
저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 곳에 연결되어 있는 링크드 리스트에 저장!
그림 2. HashMap에 저장된 데이터를 찾는 과정
그림 2에서 배열의 각 요소는 링크드 리스트가 저장되어 있고 여기에 실제 데이터가 담기게 된다.
- 이 자료구조를 사용하여 데이터를 찾는 과정은 다음과 같다.
검색하고자 하는 값의 키로 해시함수를 호출한다.
해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.
링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.
- 하나의 배열에 링크드 리스트가 최소한만 저장되어야 빠른 검색결과를 얻을 수 있다.
그러려면 저장될 데이터의 크기를 고려하여 HashMap의 크기를 적절하게 지정해줘야 하고,
해시함수가 서로 다른 키에 대해 중복된 해시코드의 반환을 최소화해야 한다.
그래서 제일 중요한 건 해시함수의 알고리즘이다.
- HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 hashCode()를 해시함수로 사용한다.
Object클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘을 사용해서 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일해 훌륭한 방법이다.
String클래스의 경우 서로 다른 두 객체에 대해 equals()로 비교해서 true이고, hashCode()의 반환값도 같아야 같은 것으로 인식한다.
그래서 새 클래스 정의할 때 equals()를 재정의오버라이딩 해야되면 hashCode()도 재정의 해주어야 한다.
