고정 헤더 영역
상세 컨텐츠
본문
해시 테이블은 'Key: Value'의 쌍을 저장하는 구조로, 고유한 Key를 기반으로 빠르게 데이터를 검색할 수 있게 해주는 자료구조이다.
이론적으로는 해시 테이블에서 원소를 찾는 것이 연결 리스트에서 원소를 찾는 것(최악의 경우 O(n)의 수행시간을 가진다)만큼 오래 걸릴 수 있지만 실제로 해싱은 성능이 탁월하다. 합리적인 가정 하에서 해시 테이블에서 원소를 찾는 데 걸리는 평균 수행시간은 O(1)이다. (출처: Introduction to Algorithms)
해싱(Hashing)이라는 개념은 1930년대에 처음 사용되었으며, 데이터 저장 및 검색 분야에 큰 혁신을 가져왔다고 한다.
'Hash'라는 단어는 'hack'에서 유래되었는데, 원래 의미는 '잘게 자르다'이다. 데이터를 작은 부분으로 나누어 처리한다는 개념에 부합하면서 이런 이름이 붙었다고 한다.
해시 테이블의 장단점은 다음과 같다.
| 장점 | 단점 |
| 1. 평균적으로 데이터의 삽입, 삭제, 검색이 (O(1))의 시간 복잡도를 가진다. 2. 키와 값을 쌍으로 저장하기 때문에 데이터 검색이 용이하다. |
1. 해쉬 충돌이 발생할 가능성이 있다. 2. 메모리 사용량이 배열에 비해 크게 될 수 있다. |
해시 테이블은 효율적인 데이터 검색이 필요한 다양한 분야에서 응용된다. 예를 들어,
- 데이터 베이스: 대용량 데이터에서 원하는 정보를 빠르게 찾아냄에 있어서 해시 테이블은 거의 필수적인 자료구조로 여겨진다.
- 캐싱: 웹 서버에서 사용되는 캐시 메모리에 데이터를 저장하고 검색하는 데 사용된다.
- 언어 번역기: 단어나 구문의 매핑을 빠르게 찾기 위해 사용된다.
이제 해시테이블에 대해 조금 더 디테일하게 알아보자.
1. 해시 - 해시 함수 - 해싱
우선, Hash - Hash Function - Hashing - Hash Table은 연결된 개념이기도 하고 이름도 비슷하고.. 등등 대충 뭉뚱그려 이해하고 넘어갈 가능성이 높다. 그래서 각각의 개념을 찝어서 내용을 정리해보았다.
<선요약>
1. 해시: 데이터의 고유한 대표 값
2. 해싱: 해시 값을 얻기 위한 과정
3. 해시 함수: 데이터를 입력받아 해시 값을 반환하는 함수
4. 해시 테이블: 해싱과 해시 함수를 기반으로 동작하며, 키-값 쌍을 저장하고 검색하는 데이터 구조
해시 (Hash)
정의: 어떠한 데이터를 대표하는 고정된 길이의 값. 보통 해시 값이라고도 표현한다.
- 해시는 해시 테이블에서 Key를 해시 함수에 넣어서 얻어진 결과값(인덱스)을 의미하며, 원본 Key 자체를 의미하는 것은 아니다.
특징:
- 동일한 입력에 대해서는 항상 동일한 '해시 값'을 생성한다.
- 서로 다른 입력이 동일한 해시 값을 갖는 경우를 해시 충돌이라고 한다. (해시 테이블에서 중요한 이슈! 뒤에서도 다룬다)
예시: MD5, SHA-256과 같은 해시 알고리즘을 통해 문자열이나 파일의 내용을 고정된 길이의 해시 값으로 변환한다.
해시 함수 (Hash Function)
정의: 데이터를 입력으로 받아 고정된 길이의 해시 값을 반환하는 함수
특징:
- 동일한 입력은 항상 동일한 '출력'을 반환한다. (따라서 동일한 '해시 값'을 반환함)
- 서로 다른 입력이 동일한 출력을 반환할 가능성이 있다. (따라서 동일한 '해시 값' 반환 가능 -> 해시 충돌)
- 고정된 길이의 출력을 반환한다.
예시: 위에서 언급한 MD5, SHA-256, CRC32 등
해싱 (Hashing)
정의: 해시 함수를 사용하여 [데이터 -> 해시 값]으로 변환하는 과정
목적:
- 데이터의 무결성 검사
- 데이터를 고유하게 대표하는 값 생성
특징:
- 해싱을 통해 생성된 '해시 값'은 데이터의 고유한 식별자(Identifier) 역할을 할 수 있다.
- 해싱은 다양한 응용처에서 활용된다. (ex: 데이터베이스, 암호화, 빠른 검색 등)
해시 테이블 (Hash Table)
기본 개념
정의: 해시 테이블은 'Key: Value'의 쌍을 저장하는 데이터 구조이다.
핵심요소:
- 키 (Key): 데이터를 찾기 위해 사용되는 식별자이다. 키와 키는 중복되지 않는다. 즉, 유일한 값으로 존재한다.
- 값 (Value): 키와 연결된 실제 데이터. 우리가 접근하고자 하는 대상이다.
- 해시 함수 (Hash Function): 키를 받아서 고유한 인덱스(해시 값)를 생성하는 함수이다.
1) 키(Key)를 해시 함수에 입력하여 해시 값을 얻고, 2) 얻은 해시 값을 인덱스로 사용하여 값을 저장하거나 검색한다.
배열(Array)과의 유사성 및 차이점
배열과 비교하며 공부하는 방식이 해시 테이블을 더욱 깊게 이해하는데 도움을 주는 것 같다.
유사성:
- 둘 다 인덱스를 사용하여 데이터에 빠르게 접근할 수 있는 자료구조이다. 기본적으로 둘 다 임의의 위치를 O(1)에 접근할 수 있다.
차이점:
- 연속적 vs 불연속적:
- 배열은 연속된 메모리 공간에 데이터를 저장하며, 인덱스는 0부터 시작하는 숫자이다.
- 해시 테이블은 불연속적인 메모리 공간에 데이터를 저장하며, 인덱스는 해시 함수를 통해 얻은 해쉬 값이다.
- 특정 조건이 만족한다면, 해시 테이블은 직접 주소 테이블(일반적으로 말하는 배열) 대비 공간 효율적이다.
해시 테이블은 실제 저장된 키의 개수에 비례하는 크기를 가지는 배열을 사용하므로, 실제 저장된 키의 개수가 가능한 키의 전체 개수보다 상대적으로 작은 경우 일반 배열에 직접 주소화 방법을 사용하는 것보다 효율적이다.
(...)
직접 주소화 방법의 단점은 명백하다. 전체 집합 U가 크다면 일반적인 컴퓨터의 메모리 공간에서는 크기 |U|를 가지는 테이블 T를 저장하는 것은 비실용적이거나 불가능하다. 게다가 실제 저장되는 키들의 집합 K는 U에 비해 상대적으로 작아서 T를 위해 할당된 대부분의 공간은 낭비된다.
사전에 저장된 키들의 집합 K가 모든 가능한 키들의 전체 집합 U에 비해 훨씬 작을 때 해시 테이블은 직접 주소 테이블보다 훨씬 작은 공간을 필요로 한다. 검색에 소요되는 시간이 단지 O(1)인 이점을 유지하면서 사용 저장 공간을 O(|K|)로 줄일 수 있다. 다만 직접 주소화 방법에서는 이 수행시간이 최악의 경우 수행시간에 해당되지만, 해시 테이블을 이용한 방법에서는 이것이 평균 수행시간이 된다.
(...)
이때 해시 테이블의 크기 m은 일반적으로 |U|보다 훨씬 작다. "키 k를 갖는 원소가 위치 h(k)에 해시된다"고 말하고 "h(k)는 키 k의 해시 값이다"라고 한다.
(출처: Introduction to Algorithms, p.254-257)
위 그림에서 h(k2) = h(k5) 부분에 주목해보자. 두 개의 인덱스(해시 값)가 같은 위치에서 충돌하게 되었다.
이것이 해시 테이블에서 가장 중요한 이슈 중 하나인 '해시 충돌'이다.
해시 충돌
해싱을 이용하는 경우, 키 두 개가 동일한 위치에 해시되는 경우가 있다. 이를 충돌(Collision)이라고 한다.
충돌로 발생하는 부작용] 대표적인 방법이 1) 체이닝(오픈 해시법)과 2) 오픈 주소법(개방 주소화 방법)이다.
체이닝(Chaining)
체이닝이란, 해시값이 같은 데이터들을 연결 리스트로 연결하는 방법을 의미한다. 연결 리스트로 연결한 모양이 체인 같다고 해서 붙여진 이름이다.
같은 위치에 해시되는 모든 원소를 같은 연결 리스트에 넣는다. T[j]는 연결 리스트(위치 j에 해시된 모든 원소로 이루어진 리스트)의 Head Node를 가리키는 포인터를 가지고 있다. 원소가 존재하지 않는다면 T[j]는 nil(값이 없음. null과 비슷한 개념) 값을 가진다.
업데이트 예정:
- 적재율
- 오픈주소법
- 좋은 해시 함수의 조건
참고:
Introduction to Algorithms
Do it! 자료구조와 함께 배우는 알고리즘 입문
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/main/DataStructure#hash-table
https://baeharam.netlify.app/posts/data%20structure/hash-table
'Computer Science > 자료구조 (Data Structure)' 카테고리의 다른 글
| 자료구조 | 이진 트리, 트리 순회(Tree Traversal) (0) | 2023.10.20 |
|---|---|
| 자료구조 | 트리(Tree) (1) | 2023.10.20 |
| 자료구조 | 이중 연결 리스트, 원형 연결 리스트 (0) | 2023.10.17 |
| 자료구조 | 연결 리스트(Linked List) (0) | 2023.10.17 |
| 자료구조 | 배열, 스택, 큐 (0) | 2023.10.16 |
