오늘 뭐했냐/개발에 대한 주저리
23.09.18 해시테이블 다시 학습
스스로에게
2023. 9. 19. 23:11
해시 테이블
해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.
구성요소
버킷 (Bucket)
- 해시 테이블의 각 슬롯을 나타내며, 하나 이상의 키-값 쌍을 저장할 수 있다.
- 충돌 해결 방법에 따라 버킷의 구현이 달라진다.
해시 함수 (Hash Function)
- 키를 받아 정수 값을 반환하는 함수로, 반환된 정수 값은 버킷의 인덱스로 사용된다.
- 해시 함수는 균등하게 값을 분포시켜야 하며, 동일한 키에 대해서는 항상 동일한 해시 값을 반환해야 한다.
- 해시 함수의 품질과 특성은 해시 테이블의 성능, 효율성, 그리고 안정성에 큰 영향을 미친다.
충돌 해결 메커니즘 (Collision Resolution Mechanism)
- 두 개 이상의 키가 같은 버킷에 매핑될 때, 이를 해결하기 위한 방법이다.
리사이징 (Resizing)
- 일부 해시 테이블 구현체는 *로드 팩터(load factor)가 일정 수준을 넘어가면 해시 테이블의 크기를 조절한다.
- 리사이징은 해시 테이블의 성능을 유지하며, 오버헤드를 관리한다.
*로드 팩터(load factor) : 적재율이라고도 하며 해시 테이블에서 현재 사용 중인 버킷의 비율을 나타낸다.
(저장된 항목의 수 / 전체 버킷 수)
- 낮은 적재율: 해시 테이블에 많은 빈 버킷이 있을 때, 저장 공간은 비효율적으로 사용되지만, 충돌의 가능성이 줄어듭니다. 이로 인해 메모리 사용이 비효율적이게 된다.
- 높은 적재율: 해시 테이블에 대부분의 버킷이 채워져 있을 때, 메모리 사용은 효율적이지만 충돌의 가능성이 증가하며, 따라서 검색, 삽입, 삭제 연산의 성능이 저하될 수 있다.
장점:
- 빠른 검색, 삽입, 삭제: 만약 충돌이 적절히 관리되면, 이러한 연산들의 평균 시간 복잡도는 O(1)이다.
- 키-값 매핑: 키와 값을 연결하여 저장하는 것이 직관적이고 사용하기 쉽다.
- 유연성: 다양한 데이터 타입의 키를 사용할 수 있다.
단점:
- 공간 복잡도: 메모리 사용이 비효율적일 수 있다.
- 충돌: 해시 함수의 선택과 해시 테이블의 크기에 따라 충돌이 발생할 수 있고, 충돌이 많이 발생하면 연산의 시간 복잡도가 증가할 수 있다.
- 복잡성: 충돌을 관리하는 로직이나 리사이징 로직 등, 구현이 복잡할 수 있다.
특징:
- 동적 크기 조절: 일부 구현에서는 해시 테이블의 크기를 동적으로 조절하여, 로드 팩터가 너무 높거나 낮아지지 않도록 관리합니다.
- 순서 보장 안됨: 해시 테이블에 저장된 항목들의 순서는 키의 순서나 삽입 순서와 관련이 없습니다.
대표적인 충돌 해결 매커니즘
체이닝 (Chaining):
- 해시 테이블의 각 슬롯에 연결 리스트(또는 다른 자료구조)를 저장하여 충돌이 발생할 경우 해당 슬롯의 연결 리스트에 항목을 추가하는 방식이다.
위 그림을 보면 John Smith 와 Sandra Dee 의 인덱스가 152 로 충돌하게 된 경우인데, 이 때 Sandra Dee 를 John Smith 뒤에 연결함으로써 충돌을 처리하는 것을 볼 수 있다. 하지만 충돌이 많아질 수록 동일 버킷에에 체이닝이 많아지며 속도 또한 느려진다.
오픈 어드레싱 (Open Addressing):
- 충돌이 발생할 경우, 다른 슬롯을 찾아 데이터를 저장하는 방식이다. 아래 방식 외에도 다른 방식이 있을 수 있다.
- 선형 탐사 (Linear Probing): 일정한 간격으로 다음 슬롯을 검사
- 이차 탐사 (Quadratic Probing): 제곱한 간격으로 다음 슬롯을 검사
- 더블 해싱 (Double Hashing): 두 번째 해시 함수를 사용하여 다음 슬롯을 결정
해시 테이블은 속도가 빠르며, 사이즈 조절이 쉽다는 장점이 있지만 충돌 문제로 인한 메모리 사용은 비효율적이다. 그래서 충돌 해결을 위한 매커니즘을 어떻게 사용하냐, 어떤 해시 함수를 사용하냐의 차이에 따라서 효율이 달라진다.