해시 테이블
해시 테이블 ?
- Key, Value를 통해 데이터를 1:1로 저장하는 자료구조 중 하나이다. key를 통해 값(Value)을 검색하는데 이 때 시간 복잡도는 상수값인 O(1)이다.
- 해시 테이블의 index는 키 값을 해시 함수(단방향 수식)에 대입하여 나온 결과값에 의해 결정된다.
- 해시 함수를 사용해 키 값을 인덱스로 변환하는 과정을 해싱이라고 표현한다.
해싱 ?
키값을 해시 함수에 대입시켜 계산한 결과를 인덱스로 사용하여 값에 접근할 수 있게 하는 방법이다.
해시 함수 ?
키 값을 값이 저장되는 인덱스로 바꾸기 위한 함수. 이 때 결과값은 중복 없이 충돌이 일어나지 않게 고유한 값으로 리턴해야 한다. 충돌이 적게 일어날 수록 좋은 해시 알고리즘이다.
고유한 값을 생성하는 해시 알고리즘은 다양하다. 대표적으로
Division Method- 나눗셈 법으로, 숫자 key를 테이블의 크기로 나눈 나머지 값을 인덱스로 사용한다.Digit Folding- key의 문자열을 ASCII 코드로 변환하여 그 값을 합한 뒤 인덱스로 사용한다.Multiplication Method- 곱셉법으로, 숫자로 된 Key값 K와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같은 계산을 해준다. h(k)=(kAmod1) × m
해시
해시 테이블의 키를 해시 함수에 넣게 되면 나오는 결과가 해시이다.
해시의 충돌 ?
고유 값을 만들어 인덱스에 값을 넣으려고 하는데 그 인덱스에는 이미 값이 존재하여 충돌이 일어나는 것을해시 충돌(Hash Collision)이라고 한다. 이를 해결하는 방법은 여러가지인데, 크게는 분리 연결법, 개방 주소법이 존재하고 그 중 가장 대표적으로체이닝,선형 탐색이 있다. 물론 더 많은 방법도 존재하는데 일단 아는 것만 정리하고 나중에 추가할 예정이다.
체이닝- 저장하고자 하는 저장소인 버킷(또는 슬롯)에 값이 존재한다면 기존 값과 새로운 값을 연결 리스트(Linked List)로 연결하는 방법이다.개방 주소법(선형 탐색)- 충돌이 일어났을 때 체이닝과 달리 1:1 매핑을 지키기 위해서 테이블의 비어있는 공간에 데이터를 저장하는 방법이다. 만약 테이블의 공간이 비어있지 않다면 테이블의 공간을 늘려 놓는다.
체이닝의 리해싱(ReHashing)
체이닝은 자료 구조에 배열의 크기보다 더 많은 값을 담을 수 있다. 추가를 하면 링크드 리스트에 추가되기 때문이다. 따라서 체이닝을 사용하면 적재율이 1을 넘어갈 수 있다.
하지만 적재율이 1을 넘어간다는 것은 각 배열에 존재하는 링크드 리스트에 요소들이 많아졌다는 것을 의미한다. 만약 무언가를 배열에서 찾아야 한다면 해당 인덱스의 배열이 가진 링크드 리스트에 포함된 각 요소들을 탐색하며 찾아야 하기 때문에 효율적이지 않다.
이 때는 배열의 크기보다 큰 새로운 배열을 생성해 기존 배열의 요소들을 리해싱하여 새 배열에 옮기는 작업을 통해 적재율을 낮춘다.
정리
- 해시 테이블이란 키 - 값 형태로 데이터를 다루는 자료구조이다.
- 해시 테이블의 삽입, 삭제, 검색의 시간 복잡도는 O(N)이다. 하지만 체이닝 방식에서 최악의 경우 O(N)의 복잡도가 나올 수 있다.
- 해시 테이블에서 특정 키를 구분하기 위한 함수를 해시 함수라고 한다.
- 해시 테이블에서는 키를 hashCode 함수에 넣고 반환된 정수를 버킷 또는 슬롯의 인덱스로 사용한다.
- 해시 함수의 특징은 대략적으로 다음과 같다.
- 빨라야 한다.
- 같은 객체에 대해 같은 값을 반환해야 한다.
- 데이터의 충돌을 최대한 피해야 한다.
- 일방향성을 갖는다.
- 해시 함수가 충돌을 피하기 위해 다음과 같은 방법이 있다.
- 체이닝
- 개방 주소법
- 선형 조사법
- 2차원 조사법
- 더블 해싱
- 자바에서 구현된 해시 테이블의 최대 적재율은 3/4이다. 3/4가 넘으면 테이블의 크기를 2배로 늘려 리해싱한다.
