gksrudtlr
|2025. 3. 18. 02:30
해시 테이블
- 해시 테이블이란?
- 키와 값의 쌍으로 데이터를 저장하는 비선형 자료구조
- 해시 함수를 사용하여 키를 고유한 해시 값으로 변환하고, 이 해시 값을 배열의 인덱스로 사용해 데이터를 저장
- 주요 요소
- 해시 함수: 키를 입력받아 고정된 크기의 정수로 출력하는 함수, 이 값을 index로 사용함
- 키-값 쌍: 각 데이터는 키와 값의 ㅜ상으로 저장되며, 키는 고유한 값으로 값을 찾기위한 인덱스 역할
- 버킷 또는 슬롯: 해시 테이블 내의 위치나 주소를 의미, 해시 값에 따라 키-값 쌍이 저장
- 작동 원리
- 데이터 삽입: 키-값 쌍으로 해시 함수에 입력해 해시를 얻고, 그 값을 index로 배열에 데이터를 저장
- 데이터 검색 : 특정 키에 해당하는 값을 찾기 위해 해시 함수를 사용해 해시 값을 계산하여 해당 index의 배열에 값을 검색
- 충돌 해결: 해시 함수가 동일한 값을 반환하면 체이닝이나 개방 주소법과 같은 기법을 사용해 충돌 해결
- 장점
- 빠른 검색 속도: 평균적으로 O(1) 의 시간 복잡도를 가짐
- 효율적인 삽입 및 삭제: 키-값 쌍의 삽입과 삭제가 효율적
- 단점
- 해시 충돌과 같은 문제로 검색 기능이 저하될 수 있음
- 해시 함수의 품질에 따라 성능이 좌우될 수 있음
해시 함수
- 역할
- 키를 일정한 범위의 숫자로 변환
- 변환된 숫자를 해시 테이블의 크기에 맞게 index로 변환
- 해당 인덱스에 데이터 저장
- 조건
- 결과값이 일정 범위 유지
- 동일한 입력에 대해 항상 동일한 출력 - 이를 결정성이라하며 동일한 입력값에 대해 항상 동일한 해시값을 출력하는 특성
- 충돌이 적게 발생
- 해시 함수 기법
- 나눗셈법
- h(x) = x mod m(m은 소수)
- 키를 소수(prime number)로 나누고 나머지를 인덱스로 사용
- 충돌이 적고 간단하지만, 테이블 크기르씬중하게 설정해야함
- 곱셈법
- h(x) = floor(m*(A*x mod 1)) (A는 0과 1사이 상수, 보통 황금비 0.618 사용)
- 나눗셈법과 유사하지만 충돌이 적고, 소수를 찾을 필요 없음
- 문자열 해싱
- 문자열을 숫자로 변환 후 다향식 방식으로 해싱
- hash(s) = (s[0]+s[1]*p+s[2]*p^2+...+s[n-1}*p^(n-1)) mod m
- 보통 p는 31, m은 매우 큰 소수 사용
충돌 기법
- 충돌 기법이란?
- 동일한 해시 값이 여러 개의 키에 대해 발생할 수있는데 이를 해시 충돌이라하며 이를 해결하는 기법
- 체이닝(Chaining)
- 링크드 리스트를 활용하여 같은 인덱스에 여러개의 데이터를 저장하는 방식
- 검색할 땐 해당 위치의 링크드 리스트를 순회해야 함
- 충돌이 많아지면 리스트가 길어져 탐색 성능이 떨어짐
- 개방 주소법(Open Addressing)
- 해시 테이블 내에 충돌이 발생한 데이터를 새로운 위치에 저장하는 방식
- 대표적 기법
- 선형 탐사(Linear Probing)
- 충돌 발생시 일정 간격(보통1)을 더해 빈 공간을 찾음
- h(k,j) = (h(k)+i) mod m
- 데이터가 밀집되는 클러스터링(Clustering)문제 발생할 수 있음
- 이중 해싱(Double Hashing)
- 두 새의 해시 함수 사용해 충돌시 다른 간격으로 이동
- h(k,i) = (h1(k)+i*h2(k)) mod m
- 클러스터링 문제 완화 가능
- 모든 키가 동일한 해시 값을 생성
- 최악의 해시 충돌
- 키-값 쌍이 동일한 해시 테이블에 저장되어 검색 성능 저하 및 삽입 삭제 성능 저하
- 개방 주소법이 체이닝 기법에 비해 가지는 장단점
- 체이닝 기법
- 장점
- 각 버킷에 연결 리스트를 사용해 충돌을 해결하므로 구현이 간단
- 필요한 만큼 메모리를 사용해 메모리 효율성이 좋음
- 단점
- 연결 리스트를 따라 이동하므로 캐시 적중률이 낮을 수 있음
- 마찬가지로 길이가 길어지면 검색 시간이 증가
- 개방 주소법
- 장점
- 연속된 메모리 공간에 데이터 저장해 캐시 적중률 높음
- 연결 리스트가 필요하지 않아 메모리 할당 및 해제의 오버헤드가 줄어듬
- 단점
- 여러 탐색 기법을 사용하므로 구현이 복잡
- 해시 테이블이 큰 경우, 비어있는 공간이 많아질 수 있어 메모리 효율성이 낮음
- 해시 테이블의 특정 영역에 데이터가 집중되는 현상인 클러스터링 문제가 발생해 검색 성능이 낮아질 수 있음
unordered_map & unordered_set
- hash table로 구현된 자료구조로 삽입, 삭제, 검색 모두 평균 O(1)이라는 시간 복잡도를 갖음
- 데이터가 정렬되지 않은 상태로 저장됨
- 데이터 순서가 중요하지 않다면 가장 효율적임
- 삽입이 매우 빠르고 정렬 상태 유지를 위한 추가 작업이 불필요해 메모리가 효율적
- unordered_set
- 중복을허용하지 않음
- 값의 존재를 빠르게 확인 가능
- 주요 함수
- insert(value): 원소 삽입
- erase(value): 원소 삭제
- find(value): 원소 검색
- count(value) 원소의 개수 반환(항상 0,1중 하나)
- clear() : 모든 원소 제거
- unordered_map
- key-value 쌍을 저장하는 해시테이블
- key는 유일함
- 주요 함수
- insert({key, value})
- operator[key] : key에 해당하는 value에 접근
- erase(key): key-value 제거
- find(key):key-vlaue 검색
- count(key):key의 존재 여부 확인(항상0,1중 하나)
