Hashing(JAVA)

# Hashing

해싱(hashing)이란 해시함수(hash function)를 이용해서 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다.
해시함수는 데이터가 저장되어 있는 곳을 알려 주기 때문에 다량의 데이터 중에서도 원.하.는. 데이터를 빠르게 찾을 수 있다.

해싱을 구현한 컬렉션 클래스로는 HashSet, HashMap, Hashtable 등이 있다. Hashtable은 컬렉션 프레임웍이 도입되면서 HashMap으로 대체되었으나 이전 소스와의 호환성 문제로 남겨 두고 있다. 가능하면 Hashtable대신 HashMap을 사용하도록 하자.

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

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

이해를 돕기위해 실생활에 비유한 예를 하나 들어보겠다.

한 간호사가 많은 환자들의 데이터 중에서, 원하는 데이터를 쉽게 찾을 수 있는 방법이 없을까를 고민하다가 주민등록번호의 맨 앞자리인 생년을 기준으로 데이터를 분류해서 10개의 서럽(배열)이 나눠 담는 방법을 생각해냈다. 예를 들면 71냔생, 72년생과 같은 70년대생 환자들의 데이터는 같은 서랍에 저장된다. 이렇게 분류해서 저장해두면 환자의 주민번호로 태어난 년대를 계산해서 어느 서랍에서 찾아야 할지를 쉽게 알 수 있다.

(동명이인이 있을 수 있기 때문에 이름보다는 주민등록번호를 키로 사용한다.)

이미 배운 바와 같이 링크드리스트는 검색에 불리한 자료구조이기 때문에 링크드리스트의 크기가 커질수록 검색속도가 떨어지게 된다.
이는 하나의 서랍에 데이터의 수가 많을수록 검색에 시간이 더 걸리는 것과 같다.

반면에 배열은 배열의 크기가 커져도, 원하는 요소가 몇 번째에 있는지만 알면 빠르게 데이터를 찾을 수 있다.

- 출처 및 참고자료 : JAVA의정석(남궁성 저)