자 서른 일곱 번째 키워드인 해싱테이블을 알아 볼 것이다.

이전에 해시코드를 알아보면서 조금 알아보았다. 이번엔 해싱테이블이 뭔지,
해싱테이블안에서 다른 개념과 충돌, 처리과정을 상세하게 알아보았다.

해싱테이블이 뭐에요?

해싱 테이블(Hash Table)은 컴퓨터 과학에서 널리 사용되는 자료구조로, 데이터를 키-값(Key-Value) 쌍으로 저장하고 빠르게 검색할 수 있도록 설계되었다고 한다.
해싱 테이블은 해시 함수(Hash Function)를 사용하여 키를 해시 값(Hash Value)으로 변환하고, 이 해시 값을 인덱스로 사용하여 데이터를 배열 또는 리스트와 같은 버킷(Bucket)에 저장한다.

주요 개념

해시 함수(Hash Function)

• 해시 함수는 임의의 길이를 가진 입력(키)을 고정된 길이의 해시 값으로 매핑하는 함수이다. 좋은 해시 함수는 입력 키를 균등하게 분포시키고 충돌을 최소화한다.

버킷(Bucket)

• 해싱 테이블에서 데이터를 저장하는 배열이나 리스트의 각 요소를 버킷이라고 한다. 해시 값은 버킷의 인덱스로 사용된다. 하나의 버킷에 여러 개의 키-값 쌍이 저장될 수 있다.

충돌(Collision)

• 서로 다른 두 키가 같은 해시 값을 가질 때 충돌이 발생합니다. 해시 함수의 특성상 충돌은 피할 수 없다고 한다.

장단점

장점

1. 빠른 검색 속도: 평균적으로 O(1)의 시간 복잡도로 검색, 삽입, 삭제가 가능하여 매우 빠른 속도를 제공.
2. 효율적인 메모리 사용: 적절한 해시 함수와 충돌 해결 방법을 사용하면 메모리를 효율적으로 사용가능.

단점

1. 충돌 문제: 충돌이 발생하면 검색 및 삽입 속도가 저하. 이를 해결하기 위한 추가적인 기법이 필요.
2. 해시 함수 설계: 좋은 해시 함수를 설계하는 것이 중요. 해시 함수가 균등하게 분포되지 않으면 성능이 저하될 수 있음.

동작 과정

1. 데이터 삽입: 키를 해시 함수에 넣어 해시 값을 계산합니다. 이 해시 값을 인덱스로 하여 버킷에 데이터를 저장한다.

2. 데이터 검색: 검색할 키를 해시 함수에 넣어 해시 값을 계산하고, 이 해시 값을 인덱스로 하여 해당 버킷에서 데이터를 검색한다.

3. 데이터 삭제: 삭제할 키를 해시 함수에 넣어 해시 값을 계산하고, 이 해시 값을 인덱스로 하여 해당 버킷에서 데이터를 삭제한다.

사용예시

해싱 테이블은 데이터베이스 인덱싱, 캐시 구현, 집합(Set) 연산 등 다양한 분야에서 사용된다고 한다.
예를 들어, 데이터베이스에서 특정 값을 빠르게 검색하기 위해 해싱 테이블을 사용할 수 있다.

해싱테이블 - DAT 이 뭐에요?

Direct Address Table(DAT)은 해싱 테이블의 특별한 형태로, 키가 직접 배열의 인덱스가 되는 구조이다.
이 방식은 해싱 테이블의 기본 개념을 더욱 단순화하여 구현한 것으로, 특정한 조건에서 매우 효율적일 수 있다.

주요 개념

직접 주소 매핑(Direct Address Mapping)

• DAT에서는 각 키가 배열의 인덱스와 직접적으로 대응된다. 즉, 키 자체가 배열의 인덱스로 사용되므로 해시 함수가 필요 없다.

배열(Array)

• DAT는 정적 배열을 사용하여 데이터를 저장한다. 배열의 크기는 키의 최대값에 의해 결정된다.
  배열의 각 요소는 하나의 데이터 항목을 저장한다.

장단점

장점

1. 빠른 접근 속도: 키가 직접 배열의 인덱스로 사용되기 때문에 O(1)의 시간 복잡도로 데이터에 접근할 수 있다.
2. 단순한 구조: 해시 함수나 충돌 해결 방법이 필요 없으므로 구조가 단순하고 구현이 쉽다.

단점

1. 메모리 낭비: 키의 범위가 클 경우, 사용되지 않는 많은 배열 요소들이 낭비될 수 있다.
2. 제한된 사용: 키의 범위가 작고 연속적인 경우에만 효율적이다. 키가 매우 큰 경우나 비연속적인 경우에는 비효율적이라고 한다.

동작과정

1. 데이터 삽입: 키를 배열의 인덱스로 사용하여 데이터를 삽입한다.

2. 데이터 검색: 키를 배열의 인덱스로 사용하여 데이터를 검색한다.

3. 데이터 삭제: 키를 배열의 인덱스로 사용하여 데이터를 삭제한다.

사용예시

DAT는 키의 범위가 작고 예측 가능한 경우에 유용하다고 한다. 예를 들어, 학생의 성적을 저장할 때 학생 ID가 1부터 1000까지 연속적으로 부여된 경우에 DAT를 사용할 수 있다.

해싱테이블 - 충돌 이 뭐에요?

해싱 테이블에서 충돌(Collision)은 두 개 이상의 키가 같은 해시 값을 갖게 되는 경우를 말한다.
이는 해시 함수의 특성상 불가피하게 발생할 수 있다. 해싱 테이블은 효율적으로 데이터를 저장하고 검색할 수 있는 자료구조지만, 충돌이 발생하면 성능이 저하될 수 있다.

왜 발생을 할까?

충돌은 해시 함수가 무한한 키 공간을 유한한 해시 값 공간으로 매핑하기 때문에 발생한다.
해시 함수가 키를 배열의 인덱스로 변환할 때, 서로 다른 키가 동일한 해시 값을 가질 수 있다.

상황

1. 상황 1 - 동일한 해시 값을 갖는 서로 다른 키
   예를 들어, 문자열 "apple"과 "grape"가 같은 해시 값을 가질 수 있다. 해시 함수가 문자열의 길이를 기반으로 해시 값을 생성한다고 가정한다면, 문자열의 길이가 5인 "apple"과 "grape"는 동일한 해시 값을 가질 수 있다.

2. 상황 2 - 해시 테이블이 가득 찬 경우
   해시 테이블이 가득 차서 모든 버킷이 이미 사용 중인 경우에도 충돌이 발생할 수 있다. 이 경우 새로운 키를 저장할 위치를 찾는 과정에서 충돌이 발생한다.

해싱테이블 - 충돌해결 이 뭐에요?

해싱 테이블에서 충돌은 불가피하게 발생할 수 있다. 이를 해결하기 위해 여러 기법이 사용된다.
대표적인 충돌 해결 방법으로는 체이닝(Chaining)과 개방 주소법(Open Addressing)이 있다.
각 방법은 충돌을 효과적으로 처리하는데 서로 다른 접근 방식을 취한다.

체이닝

체이닝은 각 버킷에 연결 리스트(Linked List)를 두어, 충돌이 발생한 데이터를 리스트에 저장하는 방법이다. 즉, 동일한 해시 값을 가진 키들이 하나의 버킷에 체이닝으로 연결된다고 한다.

사용가능한 상황

1. 데이터가 균등하게 분포되지 않는 경우: 체이닝은 해시 값이 불균등하게 분포되더라도 성능이 크게 저하되지 않는다.
2. 동적인 데이터 크기: 연결 리스트를 사용하기 때문에, 데이터의 크기가 동적으로 증가할 수 있다.
3. 삭제 연산이 빈번한 경우: 체이닝은 삭제 연산을 쉽게 수행할 수 있다. 리스트에서 해당 항목만 삭제하면 되기 때문이다.

개방주소법

개방 주소법은 충돌이 발생하면 다른 빈 버킷을 찾아 데이터를 저장하는 방법이다. 주요 기법으로는 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다.

사용가능한 상황

1. 메모리가 제한된 경우: 개방 주소법은 추가적인 메모리 구조를 사용하지 않기 때문에, 메모리 사용을 최소화할 수 있다.
2. 고정된 데이터 크기: 해시 테이블의 크기가 고정되어 있고, 데이터의 크기가 예측 가능한 경우에 유리하다.
3. 클러스터링을 피하고 싶은 경우: 선형 탐사나 이차 탐사와 같은 기법을 사용하면 클러스터링 문제를 완화할 수 있다.

체이닝과 개방 주소법의 비교

체이닝

1. 장점
   해시 테이블의 크기에 비해 많은 데이터를 저장할 수 있다.
   데이터의 삽입, 삭제가 용이하다.

2. 단점
   연결 리스트를 위한 추가 메모리가 필요하다.
   해시 값의 분포가 불균형할 경우, 특정 버킷에 많은 데이터가 몰릴 수 있다.

개방 주소법

1. 장점
   메모리 사용량이 적다.
   모든 데이터가 해시 테이블 내에 저장되므로, 추가적인 메모리 구조가 필요 없다.

2. 단점
   해시 테이블이 꽉 찰 수 있으며, 이 경우 성능이 급격히 저하될 수 있다.
   클러스터링 문제가 발생할 수 있다.(특히 선형 탐사)

결론 - 느낀 점

이번 키워드 같은 경우는 워낙 방대해서 양이 많아졌다.
확실히 자료구조에 대해서는 정보도 많지만 이해하기 어려운 내용이라 많은 자료를 찾아보았다.

C#에서 사용한 Dictionay가 생각나는데 해시테이블은 앞으로 중요하게 다룰 것 같으니
예제도 연습하며 익혀야 겠다.