본문으로 건너뛰기
실습하기

해시 테이블(Hash Table)

해시 테이블(Hash Table)은 키(Key)와 값(Value)의 쌍으로 데이터를 저장하는 자료구조로, 빠른 데이터 검색, 삽입, 삭제를 할 수 있습니다.

해시 테이블은 사물함과 비슷한 개념으로, 사물함의 번호는 '키(key)'에, 사물함 안의 물건은 '값(value)'에 해당합니다.

해시 테이블에서 '해시 함수'는 주어진 키를 받아 그 키에 해당하는 사물함의 '주소'를 계산합니다. 이 주소는 키가 저장되는 위치를 가리키며, 덕분에 키를 사용하여 매우 빠르게 값을 찾을 수 있습니다.

파이썬에서는 해시 테이블 구조가 '딕셔너리(Dictionary)' 형태로 구현되어 있습니다.


해시 테이블의 작동 원리​

  • 해싱(Hashing): 키를 해시 함수를 통해 해시 코드(Hash Code)로 변환하는 과정을 뜻합니다. 이 해시 코드는 저장될 데이터의 주소를 결정합니다.

  • 해시 충돌(Hash Collision): 두 개의 다른 키가 같은 사물함 번호(주소)를 가리키는 경우가 발생할 수 있습니다. 충돌은 서로 다른 키가 동일한 해시 코드로 변환되는 경우를 뜻합니다.

  • 해시 함수(Hash Function): 해시 테이블은 해시 함수를 사용해 키(Key)를 해시 코드로 변환합니다. 이 해시 코드는 저장될 값의 인덱스로 사용됩니다. 좋은 해시 함수는 충돌을 최소화하고, 데이터를 해시 테이블에 고르게 분포시킵니다.


해시 테이블의 구현​

해시 테이블 구현 예시
hash_table = list([0 for i in range(10)])

def get_key(data):
    return hash(data)

def hash_function(key):
    return key % 8

def save_data(data, value):
    hash_address = hash_function(get_key(data))
    hash_table[hash_address] = value

def read_data(data):

    hash_address = hash_function(get_key(data))
    return hash_table[hash_address]

save_data('Key1', 'Value1')

save_data('Key2', 'Value2')

print("Key1:", read_data('Key1')) # Value1

print("Key2:", read_data('Key2')) # Value2

해시 테이블의 장점과 단점​

장점:​

해시 테이블의 주요 장점은 다음과 같이 요약할 수 있습니다:

  1. 빠른 데이터 접근 및 검색: 해시 테이블은 평균적인 상황에서 데이터를 추가, 검색, 삭제하는 데 상수 시간(O(1))이 소요됩니다. 이는 키를 사용하여 직접 해당 값에 접근할 수 있기 때문입니다.

  2. 효율적인 메모리 사용* 해시 테이블은 데이터를 효율적으로 저장하며, 필요에 따라 동적으로 크기를 조절할 수 있습니다.

  3. 키-값 쌍 데이터 구조: 키-값 쌍 구조로 인해 데이터를 구조화하고 관리하기 쉽습니다. 이를 통해 데이터를 직관적으로 삽입, 검색, 삭제할 수 있습니다.

단점:​

  1. 충돌(Collision) 발생: 서로 다른 키가 동일한 해시 값을 가질 때 발생하는 충돌은 해시 테이블의 성능을 저하시킬 수 있습니다. 충돌이 빈번하게 발생하면 해시 테이블의 평균적인 접근, 검색, 삭제 시간이 상수 시간(O(1))에서 최악의 경우 선형 시간(O(n))으로 증가할 수 있습니다.

  2. 순서 유지 불가능: 해시 테이블은 데이터의 순서를 유지하지 않습니다. 즉, 키-값 쌍이 추가된 순서대로 데이터를 검색하거나 반복할 수 없습니다. 이 때문에 데이터의 순서가 중요한 경우에는 해시 테이블이 적합하지 않을 수 있습니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!