[Java 기초 공부] 해싱과 해싱함수
해싱이란 해싱함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 다량의 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, HashTable 등이 있다. Hashtable은 컬렉션 프레임웍이 도입되면서 HashMap으로 대체 되었으나 이전 소프트웨어 호환 문제로 남겨 두고 있다.
해싱에서 사용하는 자료구조는 배열과 링크드 리스트의 조합으로 되어있다.
해싱 예제 1
| ① 검색하고자 하는 값의 키로 해시함수를 호출 ② 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다. ③ 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다 |
링크드 리스트는 검색에 불리한 자료구조 이기 때문에 링크드 리스트의 크기가 커질수록 검색속도는 떨어지게 된다.
반면에 배열은 크기가 커져도, 원하는 요소가 몇 번째에 있는 지만 알면 아래의 공식에 의해서 원하는 값을 찾을 수 있다.
배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size + n
그래서 실생활과는 맞지 않지만, 하나의 서랍에 많은 데이터가 저장되어 있는 형태보다는 많은 서랍에 하나의 데이터만 저장되어 있는 형태가 더 빠른 검색 결과를 얻을 수 있다.
그러기 위해서는 HashMap의 크기를 적절하게 지정해야하고, 해시함수가 서로 다른 키에 대해서 중복된 해시코드의 반환을 최소화해야만 HashMap에서 빠른 검색시간을 얻을 수 있다.
해싱을 구현하는 과정에서 제일 중요한 것은 해싱함수의 알고리즘이며, 이예제에서 사용된 해시 함수의 알고리즘은 주어진 키의 첫 번째 문자만 뽑아서 정수로 반환하기만 하면 되는 코드이다.
int hashFuction(String key) {
return Integer.parseInt(key.substring(0,1);
}알고리즘이 간단한 만큼 성능은 좋지 않아서 서로 다른 키에 대해서 중복된 해시코드를 반환하는 경우가 많다.
실제로는 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 Object클래스에 정의된 HashCode()를 해싱함수로 사용한다. 이는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 이를 호출한 결과가 서로 유일한 훌륭한 방법이다.
String클래스의 경우 HashCode()를 오버라이딩해서 내용으로 해시코드를 만들어 낸다. 그래서 다른 인스턴스일지라도 같은 문자열을 가졌다면 같은 해시코드를 얻는다.
HashSet 내용에서 서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 HashCode()의 반환값이 같아야 같은 객체로 인식한다. HashMap에서도 이와 같은 방법으로 객체를 구별하며, 이미 존재하는 키에 대한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다.
그래서 새로운 클래스를 정의할 때 equals()를 재정의 오버라이딩 해야한다면 HashCode()도 같이 재정의해서 equals()의 반환값이 true인 두 객체에 대해서 HashCode()의 반환값이 항상 같도록 해야한다.
그렇지 않으면 HashMap과 같은 클래스에서는 두 객체를 다른 것으로 인식하고 따로 저장할 것이다.