해싱(Hashing)
해싱(Hashing)이란 해시함수(Hash Function)를 이용하여 해시 테이블(Hash Table)에 데이터를 저장하는 방법을 말합니다.
해시함수는 데이터가 저장되어 있는 위치를 알려주기 때문에 많은 데이터 중에서도 원하는 데이터를 빠르게 찾아낼 수 있습니다.
해싱을 구현한 클래스는 HashMap, HashSet, Hashtable등이 있습니다.
Hashtable은 Collection Class로 들어가면서 HashMap으로 대체되었지만, 호환성을 위해 남겨져 있습니다.
따라서 Hashtable보다는 HashMap을 사용하는 것을 권장합니다.
해싱에서 사용하는 자료구조는 배열과 링크드리스트의 조합이며, 자세히 보면
배열의 요소안에 링크드 리스트가 저장되어 있는 구조입니다.
자바의 정석에 나와있는 그림을 보면서 설명하겠습니다.
- 검색하고자 하는 값을 가진 Key로 해시함수를 호출한다.
- 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 요소에 접근한다.
- 요소안에 링크드리스트들을 조회하여 값을 찾는다.
해싱은 위의 3단계 절차를 따라서 동작합니다
위의 예시에서는 구현된 해시함수는 주민등록번호의 첫 번째 자리를 해시코드값으로 만드는 간단한 해시함수입니다
따라서 앞자리가 7로 시작하는 주민등록번호는 배열 7번째방에 링크드 리스트로 값이 저장되어 있습니다
하지만 실제로 해시함수를 저렇게 간단히 사용하지는 않습니다
왜냐하면, 해싱으로 저장되는 데이터는 배열의 요소안에 있는 링크드리스트에 저장됩니다
링크드리스트는 크기가 클수록 검색효율이 안좋아지기 때문에 해시테이블의 한 배열요소안에는 데이터의 개수가 1개인것이 가장 이상적입니다.
해시 테이블(Hash Table)
위 이미지에서 왼쪽이 효율이 안좋은 해시테이블, 오른쪽이 이상적인 해시테이블이라고 할 수 있습니다
오른쪽의 해시테이블은 링크드리스트가 각 방마다 1개씩 있는 형태를 가지기 때문에, 검색속도가 매우 뛰어납니다.
이러한 해시테이블을 구현하기 위해서 가장 중요한 것은 해시함수입니다.
해시함수가 각각의 key마다 다른 해시코드를 반환하도록 구현한다면, 이상적인 해시테이블의 구조를 구현할 수 있을것입니다
해시함수(Hash Function)
HashMap처럼 해싱을 구현한 Collection클래스에서는 Object클래스의 hashCode()를 해시함수로 사용합니다
Object 클래스의 hashCode()는 객체의 주소를 기반으로 해시코드를 생성하기 때문에 거의 모든 객체에 대해서 서로다른 해시코드를 반환합니다.
String클래스는 이러한 hashcode()를 클래스의 특징에 맞게 재정의하여 사용하고 있습니다.
String 클래스는 문자열의 내용을 기반으로 해시코드를 생성하도록 구현되어 있습니다.
따라서 다른 객체지만 같은 문자열을 가지고 있다면 hashCode가 동일한 것입니다.
HashCode와 equlas
만약 사용자가 임의의 hashcode를 구현하고싶어서 Object 클래스의 hashcode를 오버라이드 했다면, 반드시 equals와 함께 오버라이드 해야합니다.
왜냐하면, 같은 객체라는 것은 equlas메서드의 반환값이 true인 동시에 동일한 hashcode값을 가져야 하기 때문입니다.
서로다른 객체가 다른 hashcode값을 가지는 경우는 거의 없지만, 더 확실하게 객체의 일치여부를 판단하기 위해 hashcode와 equals를 함께 오버라이드 하는것입니다.
간단히 요약하면 hashcode와 equals는 세트다라고 생각하시면 될 것 같습니다.
