[면접을 위한 CS 전공지식 노트][자료구조] Hash Table

1. 해시 테이블이란?

 해시 테이블은 데이터를 효율적으로 저장하고, 검색하기 위한 자료구조로 키(key)와 값(value)을 쌍으로 하여 데이터를 관리한다.  해시테이블은 해시 함수를 사용하여 키를 해시값으로 변환하고 이를 기반으로 저장할 배열의 인덱스를 결정하여 데이터를 저장하거나 검색한다.

 

- 해시 테이블의 주요 특징

1) 해시 함수: 해시테이블은 해시 함수를 이용하여 키를 해시 값으로 변환한다. 해시 함수는 임의의 길이를 가진 데이터를 고정된 길이의 값으로 매핑하는 함수이다. 이 때 동일한 키는 항상 동일한 해시값으로 매핑되어야 한다. 해시 값은  배열의 인덱스와 연결되며, 이를 통해 데이터가 저장되거나 검색된다.

 

2) 해시 충돌: 해시 함수의 특성상 서로 다른 데이터가 같은 해시 값으로 매핑 될 수 있다. 이러한 상황을 해시 충돌이라고 하는데 해시 충돌은 피할 수 없는 현상이고, 해시 테이블의 성능을 저하시킬 수 있다. 이러한 해시 충돌은 적절한 방식으로 처리해야 한다.

 

3) 해결방법1. 개별 체이닝: 개별 체이닝 방식은 해시 충돌이 발생할 경우 충돌이 발생한 해당 해시 값의 연결리스트에 값을 추가해주는 방식이다. 해시 함수로 인해 같은 해시 값으로 매핑된 값들은 연결리스트로 관리된다.

 

4) 해결방법2. 개방 주소법: 개방 주소법은 충돌이 발생할 경우, 다른 빈 슬롯을 찾아 데이터를 저장하는 방식이다. 선형 탐사, 이차 탐사, 이중 해싱 등이 사용될 수 있다. 이 방식에서는 충돌이 발생할 경우 적절한 위치를 찾아 데이터를 저장하므로, 해시 테이블의 크기에 따라 성능이 달라질 수 있다.

 

2. 해시 함수

 해시 함수는 임의의 크기를 가진 데이터를 고정된 길이의 값으로 매핑하는 함수이다. 주로 암호학, 컴퓨터 과학, 데이터베이스, 압축 알고리즘 등 다양한 분야에서 사용되고 해시 테이블을 비롯한 많은 자료구조에서 중요한 역할을 한다. 해시 함수의 목적은 빠른 검색과 저장, 데이터 무결성 검사, 데이터 변환 등을 위해서 사용 된다.

 

해시 함수의 특징 및 원리

1) 고유한 매핑: 해시 함수는 주어진 입력에 대해 항상 고유한 해시 값(출력)을 반환해야함.

2) 고정된 크기: 해시 함수는 입력 데이터의 크기에 상관없이 항상 고정된 크기의 출력을 생성해야한다.

3) 고르게 분포: 좋은 해시 함수는 입력공간을 출력공간으로 고르게 분포시켜야 한다. 해시 값들이 너무 밀집되거나 희소해지는 것을 방지해야함.

4) 빠른 계산: 해시 함수는 빠르게 계산되어야 한다. 효율적인 해시함 수는 입력 데이터를 빠르게 처리하여 해시 값을 반환 할 수 있어야 한다

5. 역향성(One-Way Function): 해시함수는 일방적 함수로, 해시 값을 기반으로 입력 값을 추론하는 것이 어려워야 한다. (보안 관점에는 중요하다.)

6) 효율적인 충돌 최소화: 해시 함수의 입력 공간 보다 출력공간이 작기 때문에 어느정도의 충돌은 피할 수 없으나, 좋은 해시 함수는 충돌이 발생할 확률을 최소화 하도록 설계되어야 한다.

 

3. 해시 충돌

 해시 충돌은 해시 함수가 서로 다른 두 개의 입력에 대해서 동일한 해시값을 생성하는 상황을 말한다. 해시 함수는 입력 데이터를 고정된 크기의 해시 값으로 변환하는데, 입력 데이터의 공간이 무한 하다고 하면, 해시 값의 공간은 유한하기 때문에 어느 정도의 충돌은 피할 수 없다.

해시 충돌을 효과적으로 관리하기 위해 고려해야하는 것들

1) 해시 함수의 선택: 충돌을 최소화하려면 좋은 해시함수를 선택 해야 한다. 입력 데이터의 분포와 출력 범위를 고려하여 충돌이 적게 발생하는 함수를 설계해야 한다.

2) 적절한 자료구조 선택: 개별 체이닝이나 개방 주소법 중 어떤 방식을 사용할 지 데이터의 특성과 애플리케이션의 요구 사항에 따라 선택되어야 한다.

3) 로드 팩터 관리: 해시 테이블이 얼마나 채워져 있는지를 나타내는 로드 팩터를 관리하여 해시 충돌을 줄일 수 있다.

4) 재해싱(Rehashing): 로드 팩터가 일정 수준을 초과하면 해시 테이블을 다시 조정하는 과정을 수행하는 것으로 충돌을 해결하고 해시 테이블의 성능을 최적화 할 수 있다.

4. 개별 체이닝(Separate Chaining)

 개별 체이닝(Separate Chaining)은 해시 충돌을 해결하는 방법 중 하나로, 해시 테이블의 각 버킷마다 연결 리스트를 사용하여 충돌된 데이터들을 저장하는 방식이다. 해시 함수가 서로 다른 입력에 대해 같은 해시 값이 나올 때 해당 버킷에 데이터가 있으면 연결리스트에 새 데이터를 추가하는 방식으로 충돌을 처리하는 방식이다.

 

개별 체이닝의 동작 방식

1) 해시 테이블 초기화: 해시 테이블이 생성될 때, 각 버킷은 비어 있는 연결리스트로 초기화.

2) 데이터 삽입: 데이터를 해시 테이블에 삽입하려면, 먼저 해당 데이터의 해시 값을 계산한 다음, 그 해시 값에 해당하는 버킷을 확인한다. 버킷이 비어 있다면 데이터를 비어있는 연결리스트에 추가하고, 버킷에 이미 데이터가 있는 경우에는 연결리스트에 추가적으로 데이터를 추가 한다.

3) 데이터 검색: 데이터를 검색할 때도 마찬가지로 해시 값을 계산하여 해당 버킷으로 이동한 후, 연결리스트에서 검색을 수행한다.

4) 데이터 삭제: 데이터를 삭제할 때도 해당 버킷으로 이동한다음 연결리스트에서 데이터를 찾아 삭제한다.

개별 체이닝의 장점

1) 충돌을 효과적으로 관리할 수 있다. 충돌이 발생하더라도 연결리스트를 통해 데이터를 저장 할 수 있으므로 해시 테이블의 성능을 유지할 수 있다.

2) 연결리스트의 길이가 짧다면 데이터 검색의 평균 시간 복잡도가 O(1)에 가까울 수 있다.

개별 체이닝의 단점

1) 연결리스트의 길이가 길어지면 (일반적으로 로드 팩터의 크기가 큰 경우), 데이터 검색 성능이 저하될 수 있다.

2) 메모리 사용량이 크다. 각 버킷마다 연결리스트를 유지해야 하므로 추가적인 메모리가 필요하다.

5. 개방 주소법(Open Address)

 개방 주소법(Open Address)은 해시 충돌을 해결하는 다른 방법 중 하나로, 충돌이 발생할 경우 빈 슬롯(버킷)을 찾아 데이터를 저장하는 방식이다. 개방 주소법은 연결리스트를 사용하지 않고 해시 테이블 내부에 데이터를 저장하므로 메모리 사용이 효율적이다.

개방 주소법의 동작 방식

1) 선형 탐사: 충돌이 발생할 경우 다음 빈슬롯으로 이동하여 데이터를 저장한다. i번째 슬롯에서 충돌이 발생할 경우 i+1 번째, i+2번째슬롯 순서로 비어있는 슬롯을 찾아 저장한다.

2) 이차 탐사: 충돌이 발생할 경우, 일정한 간격(제곱수로 증가하는 간격)으로 빈 슬롯을 찾아 데이터를 저장한다. 선형탐사의 단점인 클러스터링(데이터가 뭉치는 현상)을 완화하기 위해 사용된다.

3) 이중 해싱: 두 개의 해시 함수를 사용하여 다른 빈 슬롯을 찾아 데이터를 저장하는 방식. 첫 번째 해시 함 수로 계산한 해시 값이 충돌일 경우 두 번째 해시함수를 이용하여 추가적인 오프셋을 계산하여 다음 빈 슬롯을 찾는다.

 

개방 주소법의 장점

1) 메모리 사용이 효율적이다. 연결리스트를 사용하는 개별 체이닝과 비교했을 때 데이터를 저장하는데 더 적은 메모리를 사용한다.

2) 데이터 검색 성능이 더 좋을 수 있다. 빈 슬롯을 찾아 데이터를 저장하므로, 연결리스트의 길이에 의한 성능 저하를 피할 수 있다.

개방 주소법의 단점

1) 클러스터링 현산: 선형 탐사와 같은 방식으로 해시충돌을 해결할 때 같은 해시 값으로 매핑된 데이터가 서로 인접한 슬롯에 저장되는 클러스터링 문제가 발생할 수 있다.

2) 로드 팩터의 제한: 개방 주소법은 로드팩터(해시 테이블에 저장된 데이터 수/ 버킷의 수)를 잘 관리해야 한다. 로드 팩터가 너무 커지면 성능이 저하될 수 있다.

6. 정리

- 해시 테이블은 데이터를 효율적으로 저장하고, 검색하기 위한 자료구조로 키(key)와 값(value)을 쌍으로 하여 데이터를 관리한다.  해시테이블은 해시 함수를 사용하여 키를 해시값으로 변환하고 이를 기반으로 저장할 배열의 인덱스를 결정하여 데이터를 저장하거나 검색한다.

- 해시 함수는 임의의 크기를 가진 데이터를 고정된 길이의 값으로 매핑하는 함수이다.해시 함수의 목적은 빠른 검색과 저장, 데이터 무결성 검사, 데이터 변환 등을 위해서 사용 된다.

- 해시함수에 서로 다른 값을 입력 했으나 같은 해시 값이 나오는 경우가 있다. 이를 해시 충돌이라고 한다.

- 해시 충돌을 해결 하는 방법으로는 개별 체이닝(separate chainning) 방법과 개방 주소법(open addressing) 방법이 있다.

- 개별 체이닝 방법은 연결리스트를 이용하여, 해시 충돌이 발생했을 경우 연결리스트에 데이터를 계속해서 연결하는 방식이고, 개방 주소법은 해시 충돌이 발생했을 때 인접한 슬롯에 데이터를 저장하는 방식이다.

 

 

참조

면접을 위한 CS 전공지식 노트