[자료구조] 해시 테이블

이번 글에서는 해시 테이블에 대해 알아보겠습니다. 삼성 SW역량테스트 B형에서는 C++ 컨테이너, 파이썬의 모듈 등 이미 구현된 자료구조는 쓸 수 없어서 직접 구현해야 합니다. 그 경우를 제외하고는 해시 테이블을 직접 구현하는 일은 거의 없으므로 구현보다는 기능과 활용을 중심으로 다룰 예정입니다. 구현은 접은글로 자세하게 작성했으니 궁금하면 참고해 주세요.

 

 

1. 해시 테이블이란?

해시 테이블은 아주 많은 양의 데이터를 저장하고 접근할 때 빠른 속도로 찾을 수 있는 자료구조입니다. 코테같은 알고리즘에서는 주로 1억이 넘어가는 데이터 ????를다루는데 쓰일까?

많은 양의 데이터를 저장하고 탐색하는 경우 아무리 빨라도 O(n)의 시간복잡도를 가집니다. 하지만 해시 테이블은 key, value를 이용하여 O(1)로 찾을 수 있습니다.

특징

• 이진 탐색 트리보다 빠르다.
• 충돌 해결
•  

2. 원리

1) 충돌 회피1

2) 충돌 회피2

 

 

2. STL에서 해시 테이블 사용하기

unordered_st, unordered_map으로 사용할 수 있습니다. 하지만 해시테이블은 일반 cache rate hit때문에 일반 배열보다 속도가 느리므로 배열의 인덱싱을 사용할 수 있으면 최대한 배열로 사용하는 것이 좋습니다. 

 

 

 

 

10만, 1억짜리 배열을 쓸 때 이용

멤버 함수	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환
clear	저장한 모든 원소를 삭제
empty	비어있는지 확인해주는 기능저장한 원소가 있으면 false, 없으면 true 반환
end	마지막 원소 다음의 반복자를 반환, 즉 사용하지 않은 영역 반환
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제
find	Key와 연관된 원소의 반복자 반환
insert	원소 추가
lower_bound	지정한 Key의 요소가 있다면 해당 위치의 반복자를 반환
rbegin	역방향으로 첫 번째 원소의 반복자를 반환
rend	역방향으로 마지막 원소 다음의 반복자를 반환
size	원소의 개수를 반환
upper_bound	지정한 Key 요소가 있다면 해당 위치 바로 다음 위치의 반복자 반환

주로 insert, find, erase를 쓴다.