해싱

해싱과 해시함수

Hashing이란 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다.

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

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

배열과 링크드 리스트의 조합

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

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

 

<HashMap에 저장된 데이터를 찾는 과정>

1. 검색하고자 하는 값의 키로 해시함수를 호출한다.

2. 해시함수의 계산결과(해시코드)로 해당 값이 저장되어 있는 링크드 리스트를 찾는다.

3. 링크드 리스트에서 검색한 키와 일치하는 데이터를 찾는다.