읽고 나면 진짜 쉬워지는 자료 구조 - 10. 해시 테이블
삽입과 탐색에 최적화된 동적 자료 구조
🔖 10.1 키를 사용한 저장과 탐색
해시 테이블의 매커니즘
모든 가능한 값에 대해 배열의 각 인덱스를 미리 할당하는 것은 메모리 사용량이 너무 크고 비효율적임. (e.g. 10억 개의 숫자를 저장하려면 크기가 10억인 배열이 필요)
대신, 값을 저장할 때 키를 특정한 규칙으로 변환하여 저장 위치를 찾는 방법이 더 효율적임
이때 해시 함수를 사용하여 키를 특정한 해시 값으로 변환하고, 해당 값을 배열의 인덱스로 활용함
해시 함수는 입력값을 고정된 크기의 숫자(해시 값)로 변환하는 역할을 하며, 이를 통해 빠르게 데이터를 탐색할 수 있음
정리하자면, 해시 테이블은 "키 → 해시 함수 → 인덱스 변환 → 값 저장" 방식으로 동작하는 자료구조다.
🔖 10.2 해시 테이블
해시 테이블의 역할
수학적인 매핑으로 키 공간을 압축한다.
원래의 키를 테이블상 위치(해시 값)로 매핑하는 해시 함수를 통해 큰 키 공간을 작은 영역으로 축소시킨다.
해시는 정수가 아닌 값들을 정수 범위로 매핑할 수 있기에 키가 정수가 아닐 때 생기는 문제를 해결할 수 있다.
충돌
큰 키의 집합을 더 작은 해시 값의 집합으로 매핑하는 수학 함수의 경우, 때로 충돌이 발생할 수밖에 없다.
이때 해시 테이블의 크기를 늘리거나 더 나은 해시 함수를 선택해 충돌을 완화할 수도 있지만 키 공간이 상자 개수보다 크다면 충돌을 완전히 제거하는 것은 어렵다.
따라서 같은 위치를 차지하려는 둘 이상의 데이터를 잘 처리하는 방법이 필요하다.
해시 테이블에서 충돌을 처리하는 방법에는 체이닝과 선형 탐색이 있다.
체이닝
체이닝은 각 상자 안에 추가 구조를 사용해 해시 테이블의 충돌을 처리하는 방법이다.
각 상자에 고정된 데이터 혹은 단일 데이터에 대한 포인터를 저장하는 대신, 연결 리스트의 '머리'를 가리키는 포인터를 저장한다.
장점은 모든 원소에 대해 연결 리스트를 스캔하지 않는다는 점이다. 해시 값이 일치하는 원소가 있는 경우에만 연결 리스트를 스캔한다.
즉, 모든 원소가 있는 큰 리스트를 탐색하는 대신, 특정 해시 값에 해당하는 상자에 있는 작은 리스트만 탐색하면 된다.
선형 탐색
충돌을 처리하는 다른 방식으로는 인접한 상자를 사용하는 방법이 있다.
이미 다른 키가 있는 상자에 데이터를 삽입해야 한다면, 바로 다음 상자로 넘어가서 그 상자를 살펴본다.
빈 상자나 동일한 키를 가진 데이터의 상자를 찾을 때까지 계속 반복한다.
즉, 선형 탐색은 키의 해시 값에 해당하는 인덱스에서 시작해, 찾으려는 키를 찾을 때까지 진행하거나, 찾을 수 없다는 결론을 내릴 때까지 계속 한다.
대신, 선형 탐색을 하는 해시 테이블은 각 상자에서 연결 리스트를 사용하지 않기 때문에 키 값의 조합을 저장하기 위해 wrapper 자료 구조를 사용한다.
선형 탐색의 장점은 해시 테이블이 최초에 할당한 배열을 더 잘 활용하고, 상자 수준의 연결 리스트 탐색 부가 비용이 들지 않는다는 장점이 있다.
단점은 루프를 돌면서 더 많은 원소를 살펴 보아야 한다는 것, 각 원소의 키가 우리가 탐색하려는 대상의 키와 일치하지 않을 수도 있다는 점이 있다.
🔖 10.3 해시 함수
좋은 해시 함수
좋은 해시 함수와 나쁜 해시 함수의 차이는 해시 테이블과 연결 리스트의 차이가 비슷한 효과를 나타낸다.
해시 함수는 매번 같은 키를 같은 해시 상자에 매핑해야 한다. 이게 안되면 해시 테이블에 이미 항목을 삽입했는데 탐색에 실패할 수 있다.
해시 함수는 모든 키를 제한된 범위로 매핑해야 하고, 이 범위는 해시 테이블에 있는 상자 개수에 해당한다.
해시 테이블의 용례
해시 테이블은 원소의 집합을 추적할 때 특히 유용하다.
BFS, DFS에서 이미 방문한 집합을 저장할 때 해시 테이블이 좋은 메커니즘을 제공한다.
Last updated