2022. 12. 29. 17:10ㆍ카테고리 없음
해시 테이블
해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형(ADT)을 구현하는 자료구조입니다. 해시 테이블의 가장 큰 특징은 대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이라는 점입니다.
해시
해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수를 의미합니다. 해시 테이블의 핵심은 해시 함수입니다. 해시 함수의 예제는 아래와 같습니다. 예제에서 입력값의 길이는 제 각각인데 화살표로 표시한 함수(해시 함수)를 통과하면 2바이트의 고정 크기 값으로 매핑되고 있습니다.
ABC -> A1
1324BC -> CB
AF32B -> D5해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱(Hashing)이라 하며, 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법중 하나입니다. 해싱은 최적의 검색이 필요한 분야에 사용되며, 심볼 테이블(일반적으로 해시 테이블로 구현) 등의 자료구조를 구현하기에도 적합합니다.
성능 좋은 해시 함수들의 특징은 아래와 같습니다.
- 해시 함수 값 충돌의 최소화
- 쉽고 빠른 연산
- 해시 테이블 전체에 해시 값이 균일하게 분포
- 사용할 키의 모든 정보를 이용하여 해싱
- 해시 테이블 사용 효율이 높을 것
비둘기집 원리(무조건 충돌)
비둘기집 원리란, n개 아이템을 m개 컨테이너에 넣을 때, n > m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어 있다는 원리를 뜻합니다. 이처럼 해시 함수에서도 비둘기집 원리에 따라서 9개의 공간에 있는 곳에 10개의 아이템이 들어온다면 반드시 1번 이상은 충돌이 발생하게 됩니다. 다만, 좋은 해시 함수라면 충돌을 최소화하여 단 1번의 충돌만 일어나겠지만, 좋지 않은 해시 함수는 심하면 9번 모두 충돌이 발생할 수도 있습니다. 따라서 여러번 충돌하는 것은 그만큼 추가 연산을 필요로 하기에 가급적 충돌을 최소화하는 것이 좋습니다.
로드 팩터
로드 팩터(Load Factor)란 해시 테이블에 저장된 데이터 개수 n을 버킷의 개수 k로 나눈 것입니다(load factor = n / k). 로드 팩터 비율에 따라 해시 함수를 재작성해야 될지 또는 해시 테이블의 크기를 조정해야 할지를 결정합니다. 또한 이 값은 해시 함수가 키들을 잘 분산해 주는지를 말하는 효율성 측정에도 사용됩니다. 일반적으로 로드 팩터가 증가할수록 해시 테이블의 성능은 점점 감소하게 되며, 자바 10의 경우 0.75를 넘어설 경우 동적 배열처럼 해시 테이블의 공간을 재할당합니다.
(충돌여부를 버킷에서 적재율을 구하는 건데 키 갯수 나누기 버킷의 크기로
해서 1의 이상일경우에는 충돌이 일어날수있다고 나타내는 지표이다.)
이것을 활용해서 할수 있는 것은 충돌이 났을것을 알고 해결하는 지표를 보여 줄수 있습니다.
Separate chaining: 추가적인 공간을 활용하여 해결하는 방식
*Linkedlist사용:해시 테이블의 기본 방식이기도 한 개별 체이닝은 충돌 발생 시 연결 리스트로 연결하는 방식입니다.
장단점:
추가적인 메모리를 쓰는 것이 Linkce list가 길어지면 탐색하는데 오래 걸린다. O(n)이 된다.
데이터의 개수가 많아지면 레드-블랙 트리에 저장하는 형태로 병행해 사용하기도 했습니다.
Openaddressing: 충돌 발생시 인접한 비어있는 공간(bucket)에 저장
이미 확보된 배열만으로 순수히 충돌을 해결하는 방식
*Linear probing : 고정폭으로 이동하여공간을찾음
가장 간단한 방식인 선형 탐사(Linear Probing)방식을 사용한 그림입니다. 선형 탐사 방식은 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행합니다. 특정 위치가 선점되어 있으면 바로 그다음 위치를 확인하는 식입니다. 이렇게 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입하게 됩니다. 즉, 가장 가까운 다음 빈 위치를 탐사해 새 키를 삽입하는 것입니다.
단점: 충돌 횟수로 1씩 더해준다.
이럴 경우 군집 현상이 발생하게 된다 .
삭제를 할때 연결 고리 역할을 했던것이 없어졌을 경우 값이 없다고 인식하고 값이 들어가는 문제가 발생할수 있다.
해결책
*삭제시 Delete같은 상징적인 형태로 표시
단점 삭제시 이후 위치를 확인해야 한다.
*삭제시 key 들을 한칸씩 위로 올려준다.
리해싱(Rehashing) 작업
오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없습니다. 따라서 일정 이상 채워지면, 즉 기준이 되는 로드 팩터 비율을 넘어서게 되면, 그로스 팩터(Growth Factor)의 비율에 따라 더 큰 크기의 또 다른 버킷이 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어납니다. 이는 동적 배열에서 공간이 가득 찰 경우, 더블링으로 새롭게 복사해서 옮겨가는 과정과 유사합니다.
*Quadratic probing:제곱수로 이동하여 빈 공간을 찾음
장단점: 비교횟수가 위에 비해서 적었다 , 군집현상에 빠지지 않게 하기 위해서 제곱수를 한다.
충돌 횟수가 늘어나도 같은 곳을 계속 확인 할수 밖에 없다.
*Double Hashing :또 다른 hash function을 사용하여 빈 공간을 찾음
장단점: 앞서 있던것은 어떻게든 군집현상이 일어날수 밖에 없다.
충돌이 발생했을때 전혀다른 2nd hash function을 사용해서 최종적으로 hash값을 구한다.
모든 공간에 다 접근할수있다 서로소가 아닌경우 한번도 접근하지 않은 메모리가 존재할수있다.
jdk7까지는 linkedlist를 사용한 separate chaining을 활용
jdk8에서 linkedlist와 red black tree를 혼용한 separate chaining을 활용
=>key-value 쌍이 숫자가 적을때는 linked list를 적용하다가 임의의 인덱스에 대해서 충돌한 key-value쌍의 갯수가 임계치를 넘어가게 되면 linkedlist를 red black tree로 해서 해결한다.
탐색을하게 되면log(n) 이 걸린다.
참고:https://www.youtube.com/watch?v=dKqv1mQotNU