Hash Table
# 해시 테이블(Hash Table)이란
자료 구조의 한 종류로, key와 value라는 쌍으로 이루어진 값들의 리스트이다. 특정 프로그래밍 언어에만 있는 것이 아닌, 다양한 프로그래밍 언어에서 사용할 수 있는 자료구조이다.
다음은 해시 테이블이 아닌 일반적인 배열이다.
list = [
{ name: "A", age: 20 },
{ name: "B", age: 21 },
{ name: "C", age: 22 },
{ name: "D", age: 23 },
{ name: "E", age: 24 },
]
만약 이 배열에서 "E"의 나이를 찾고 싶다면, 차례대로 하나하나 확인하는 선형 검색을 해야할 것이다. 그러나 선형 검색은 원소를 하나하나 확인해야 하기에 시간이 오래 걸린다는 단점이 있다. 이때 바로 해시 테이블을 이용할 수 있다.
list = {
"A": 20,
"B": 21,
"C": 22,
"D": 23,
"E": 24,
}
이렇게 해시 테이블로 표현된 자료에서 만약 E의 나이를 찾고 싶다면 선형 검색을 할 필요 없이 list["E"]라고만 작성하여도 바로 E의 나이를 출력해낼 수 있다.
선형 검색의 시간 복잡도는 O(N)이다. 따라서 데이터가 증가할수록 검색을 위한 시간도 오래 걸린다. 그러나, 해시 테이블의 시간 복잡도는 O(1)이다. 즉, 데이터의 크기와 관련 없이 검색에 소요되는 단계는 딱 하나이다. 선형 검색과 비교하면, 매우 빠른 속도로 검색을 할 수 있다.
# 해시 테이블 활용 : 데이터 검색하기
list = [ "A", "B", "C", "D", "E" ]
만약 이 배열에서 "F"라는 원소가 존재하는지 확인하고자 한다면, 원소를 하나하나 확인하는 선형 검색을 해야할 것이다. 그러나 다음과 같이 해시 테이블로 표현하면 선형 검색을 하지 않고도 빠르게 원소의 유무를 확인할 수 있다.
list = {
"A": true,
"B": true,
"C": true,
"D": true,
"E": true,
}
list["E"]; // true
list["F"]; // undefined
# 해시 함수 (Hash Function)
문자를 숫자로 변환하는 과정을 해싱(Hashing)이라고 한다. 또한, 글자를 특정 숫자로 변환할 때 사용한 코드를 해시 함수라고 한다. 해시 함수를 이용하면 key 값을 숫자로 변환할 수 있다. 따라서, 해시 테이블을 만들 때 해시 함수를 이용하여 key 값을 숫자로 변환하고, 숫자로 변환된 key 값은 value의 index가 된다.
참고 자료
책 '누구나 자료 구조와 알고리즘 개정2판' 8장
'CS > 자료구조' 카테고리의 다른 글
[자료구조] Stack과 Queue (0) | 2023.10.06 |
---|---|
[자료구조] 정렬 (0) | 2023.04.02 |
[자료구조] Big O (0) | 2023.03.24 |
[자료구조] 선형 검색과 이진 검색 (0) | 2023.03.20 |
[자료구조] 배열 (0) | 2023.03.11 |