해쉬 테이블
키(key)에 데이터(value)를 저장하는 데이터 구조를 해쉬 테이블이라고 한다.
해위 테이블의 특징
1. key를 통해서 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빠르다
2. 자바 경우 Map을 인터페이스로 하여 HashTable을 구현해 사용하고 있다.
해쉬 테이블의 용어
해쉬: 임의 값을 고정 길이로 변환하는것
해쉬 테이블: 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조
해싱 함수: key에 대한 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
해쉬 값(digest) or 해쉬 주소: key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 key에 대한 위치를 일관성 있게 찾을 수 있음
해쉬 테이블 만들어보기
Hashtable<String, String> test = new Hashtable<String, String>(5); // key,value 타입이 String이고 크기가 5인 해쉬 테이블 생성
test.put("1번","아샷추")
test.put("2번","아아")
test.put("3번","카페라떼")
해쉬 테이블의 장단점
장점
1. 데이터의 저장/ 읽는 속도가 빠르다.
2. 해쉬는 키에 대한 데이터가 있는지 확인이 쉬움
단점
1. 일반적으로 저장공간이 좀더 많이 필요하다. (데이터와 해쉬 값을 넣어줬기 때문)
2. 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함
(위의 코드를 기준으로 Viva와 Vic은 같은 키에 들어감 V의 아스키코드를 나눈값을 해쉬 주소로 하기 때문)
해쉬 테이블은 어디에서 많이 사용되는지
- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문이다.)
위의 3가지 경우 모두 기존의 있는 값의 탐색이 많은 경우에 해당한다.
자바에서 제공하는 해쉬 함수
hashCode(): 해당 인스턴스가 저장된 주소값을 기준으로 해쉬 값을 생성한다.
Coffee a = new Custom("아샷추");
Coffee b = new Custom("아아");
System.out.println("a객체 : " + a.hashCode());
System.out.println("b객체 : " + b.hashCode());
결과:
a객체: 154897513
b객체: 1587328576
해쉬 함수를 사용하여 해쉬 테이블에 저장하기
Hashtable<Integer, Coffee> test = new Hashtable<Integer, Coffee>(5); // key,value 타입이 Integer,Coffee 크기가 5인 해쉬 테이블 생성
test.put(a.hashCode()%5,a) // 해쉬 테이블의 크기가 5이기 때문에 5를 나눠줌
test.put(b.hashCode()%5,b)
해쉬 테이블의 충돌
해쉬 테이블의 가장 큰 문제점은 같은 해쉬 값을 가진 데이터들을 어떻게 처리하는지가 가장 큰 문제이다. 예를들어 위의 코드에서는 해쉬 함수를 %5 이라는 코드를 통해서 해쉬 값을 0 ~ 4사이로 지정하였는데 저장한 데이터 중에서 같은 해쉬 값을 갖는 경우 충돌이 발생을 하는데 어떻게 이런 문제를 해결하는지가 관건이다.
해쉬 테이블의 충돌에는 open Hashing 기법과 close Hashing 기법으로 나뉜다.
open Hashing
open Hashing 기법은 해쉬 테이블 저장공간 외의 공간을 활용하는 기법이다.
그 중에서도 Chaining기법이 가장 대표적이다. Chaining 기법은 충돌이 일어난 해쉬 값을 링크드 리스트라는 자료 구조를 사용해서 데이터를 추가로 뒤에 연결하는 기법이다.
close Hashing
close Hashing 기법은 해쉬 테이블 저장공간 안에서 충돌을 해결하는 기법이다.
그 중에서도 Linear Probing기법이 가장 대표적이다. Linear Probing 기법은 충돌이 일어난 해쉬 값에 들어가야하는 데이터를 다음 비어있는 해쉬 값에 대신 넣는 방법이다.
비교적 Chaining 기법 보다 복잡하지만 저장공간 활용도가 높다는 장점이 있다.
해쉬 테이블의 충돌을 최소화 하기위한 방법
해쉬 테이블의 충돌을 줄이는 방법은 여러가지 방법이 있지만 그중 가장 간단하고 일반적인 방법은 단순하게 해쉬 테이블의 크기를 늘려주는 것이다. 지금까지는 해쉬 테이블을 5로 설정하여 해쉬주소를 5개만 가지게 하였다면 이를 10개로 늘리면 충돌이 일어나는 횟수를 단순 계산으로 절반가량 줄일수있다.
Coffee a = new Custom("아샷추");
Coffee b = new Custom("아아");
System.out.println("a객체 : " + a.hashCode());
System.out.println("b객체 : " + b.hashCode());
결과:
a객체: 154897513
b객체: 1587328576
해쉬 함수를 사용하여 해쉬 테이블에 저장하기
Hashtable<Integer, Coffee> test = new Hashtable<Integer, Coffee>(10); // key,value 타입이 Integer,Coffee 크기가 10인 해쉬 테이블 생성
test.put(a.hashCode()%10,a) // 해쉬 테이블의 크기가 5에서 10으로 늘려줌 크기가 2배로 증가한 만큼 충돌 가능성이 2배로 적어졌다.
test.put(b.hashCode()%10,b)