[자료 구조] 해시테이블(Hash Table)이란? (특징, 시간복잡도, 파이썬 사용, 사용 사례)

 

해시테이블은 효율적인 데이터 검색을 가능하게 하는 자료구조 중 하나입니다. 키(Key)를 값(Value)에 매핑하여 데이터를 저장하는 방식으로, 해시함수를 사용해 데이터의 저장 위치를 결정합니다. 해시함수는 키를 고유한 숫자(해시코드)로 변환하여, 이 숫자를 기반으로 데이터가 저장될 위치를 빠르게 찾을 수 있게 합니다.

 

 

주요 특징

• 빠른 데이터 접근 속도: 해시 함수를 통해 데이터의 저장 위치를 바로 찾을 수 있기 때문에, 평균적으로 상수 시간 O(1) 내에 데이터에 접근할 수 있습니다. 하지만, 해시 충돌(Hash Collision)이 발생하는 경우, 이 시간은 늘어날 수 있습니다.
• 해시 충돌(Hash Collision): 서로 다른 키가 동일한 해시값을 가질 때 발생합니다. 해시 테이블은 충돌을 관리하기 위해 여러 전략을 사용할 수 있는데, 대표적인 방법으로 체이닝(Chaning)과 오픈 어드레싱(Open Addressing)이 있습니다.
  • 체이닝: 충돌이 발생한 요소들을 연결 리스트로 연결하여 저장하는 방법입니다.
  • 오픈 어드레싱: 충돌이 발생하면, 다른 빈 슬롯을 찾아 데이터를 저장하는 방법입니다.
• 동적 확장: 해시 테이블의 크기가 동적으로 커질 수 있습니다. 저장할 데이터가 많아지면, 해시 테이블의 크기를 자동으로 확장해 충돌의 빈도를 줄이고 데이터 접근 시간을 최적화할 수 있습니다.
• 키-값 쌍: 데이터는 키와 값의 쌍으로 저장됩니다. 이렇게 함으로써 데이터에 대한 빠른 접근뿐만 아니라, 키를 통한 데이터의 유일성도 보장할 수 있습니다.

 

 

시간 복잡도

해시테이블의 시간복잡도에 대한 설명은 해시테이블의 기본 작동 원리와 해시 충돌을 처리하는 방법에 크게 의존합니다. 해시테이블은 키를 사용하여 데이터를 저장하고 검색하는 구조로, 이와 관련된 주요 연관은 삽입(insert), 삭제(delete), 그리고 검색(search)입니다. 

 

평균 시간 복잡도

키가 잘 분산되어 있고, 해시 함수가 균형 잡힌 분포를 제공한다고 가정할 때, 해시테이블의 평균 시간 복잡도는 다음과 같습니다.

• 삽입: O(1)
• 삭제: O(1)
• 검색: O(1)
• 최선의 경우이며, 해시 함수가 키를 해시테이블 내의 버킷들 사이에 잘 분포시키고, 해시 충돌이 거의 발생하지 않는 상황을 가정

최악의 시간 복잡도

해시테이블에서 최악의 시간 복잡도는 모든 키가 동일한 해시 값을 가지고 해시 충돌이 발생하는 경우를 가정할 때 발생합니다. 이 경우, 데이터는 해시테이블의 동일한 위치에 집중되고, 특히 체이닝 방식으로 해시 충돌을 처리하는 경우에는 연결 리스트를 모두 탐색해야 할 수 있습니다. 

• 삽입: O(n)
• 삭제: O(n)
• 검색: O(n)
• 여기서 n은 해시테이블에 저장된 키/값 쌍의 수입니다. 하지만, 이는 극단적인 사례이며, 실제 사용에서는 적절한 해시 함수와 해시테이블 크기 조정, 충돌 방지 메커니즘을 통해 평균 시간 복잡도를 상수 시간에 가깝게 유지할 수 있습니다.

 

 

파이썬에서의 해시 테이블(Hash Table) 사용

파이썬에서 해시 테이블은 주로 딕셔너리(Dictionary) 형태로 사용됩니다. 딕셔너리는 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 구조로, 해시 테이블을 기반으로 합니다. 파이썬의 딕셔너리는 내부적으로 해시 테이블을 사용하여 효율적으로 데이터를 저장하고 검색할 수 있게 해 주며, 기본적인 CRUD 작업을 빠르게 수행할 수 있게 해 줍니다.

#딕셔너리 생성
my_dict = {'name':'John', 'age':30, 'city':'New York'}

#데이터 접근하기
prnit(my_dict['name']) #출력 John

#데이터 추가하기
my_dict['email'] = 'John@example.com'

#데이터 업데이트 하기
my_dict['age'] = 31

#모든 키와 값 출력하기
for key, value in my_dict.items():
	print(f"{key}: {value}")

 

 

사용 사례

1. 사용자 인증 시스템: 웹 서비스나 애플리케이션에서 사용자의 로그인 정보(ex: 사용자명, 이메일)를 키로 하고, 해당 사용자의 암호화된 비밀번호나 세션 정보를 값으로 하는 해시테이블을 사용하여, 사용자 인증을 빠르고 효율적으로 처리합니다. 해시 메커니즘이 사용되어, 비밀번호는 직접 저장되지 않고 그 해시값이 저장되어 보안이 강화됩니다.
2. 빠른 데이터 검색을 위한 캐시 메모리 구현: 데이터베이스 쿼리, 웹 페이지의 결과, 계산 중간 결과 등 접근 속도를 높이기 위해 자주 사용되는 데이터를 메모리에 캐시 형태로 저장하는데 해시 테이블이 사용됩니다. 키값에 따라 데이터를 찾아 사용함으로써 프로그램의 전체 성능을 향상시킵니다.
3. DNS(Domain Name System) 해석: 인터넷에서 도메인 이름을 IP 주소로 변환할 때, DNS 서버는 해시테이블을 사용하여 효율적으로 도메인 이름과 IP 주소의 매핑을 관리합니다. 상당히 빠른 검색 속도로 인터넷 사용자가 도메인 이름을 통해 웹 사이트에 접속할 수 있게 해 줍니다.
4. 컴파일러나 인터프리터에서의 심볼 데이터 관리: 프로그래밍 언어의 변수명, 함수명 등의 식별자와 그에 대응하는 메모리 주소나 타입 정보를 관리하는데 해시테이블이 사용됩니다. 이를 통해, 컴파일러 또는 인터프리터는 코드 내의 식별자를 빠르게 찾고 그에 해당하는 작업을 수행할 수 있습니다.
5. 중복 항목 제거: 데이터 처리 과정에서 중복 항복을 식별하고 제거하는 과정에서 해시테이블이 큰 역할을 합니다. 데이터 항목을 해시테이블에 저장하면서 이미 존재하는지 빠르게 확인하고, 중복된 항목은 추가하지 않음으로써 중복을 제거할 수 있습니다.

 

오늘은 해시 테이블에 대해서 알아보았습니다.

ArrayList, LinkedList도 함께 보시면 좋으니 참고해 주세요!

2024.04.29 - [IT] - [자료구조] ArrayList VS LinkedList

[자료구조] ArrayList VS LinkedList