키-값으로 데이터를 저장하는 해시 테이블(Hash Table)

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

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

해시 테이블은 해시 함수(Hash Function)를 통해 해당 키의 저장 위치(주소)를 계산합니다.

예를 들어, 해시 테이블에 이름과 전화번호를 저장한다고 가정해보겠습니다.

여기서 해시 함수는 전화번호 숫자의 합을 구해 10으로 나눈 나머지를 사용할 수 있습니다.

만약 전화번호가 010-1234-5678이라면, 해시 함수는 0+1+0+1+2+3+4+5+6+7+8 = 37을 계산하고, 이를 10으로 나눈 나머지인 7을 해시 코드로 사용합니다.

이렇게 해시 코드를 사용해 데이터를 저장하면, 전화번호를 키로 사용해 데이터를 빠르게 검색할 수 있습니다.

해시 함수로 계산된 주소에 데이터를 저장하고, 이후에 데이터를 검색할 때는 동일한 해시 함수를 사용해 저장 위치를 찾아 데이터를 가져옵니다.

해싱은 데이터를 해시 함수를 통해 고유한 해시 코드로 변환하는 과정입니다.

해시 코드는 데이터의 특성을 반영한 고유한 값이며, 이 값은 데이터를 저장할 주소(인덱스)로 사용됩니다.

예를 들어 위 전화번호 예시에서 010-1234-5678의 해시 코드는 7이며, 이 해시 코드는 데이터를 저장할 주소(인덱스)를 결정합니다.

해시 충돌은 서로 다른 키가 동일한 해시 코드를 가지는 경우 발생합니다.

해시 충돌이 발생하면, 동일한 해시 코드를 가진 데이터를 어떻게 저장할지 결정해야 합니다.

예를 들어 위 예시에서 010-4321-8765의 해시 코드도 7이기 때문에, 2번쨰로 해시코드가 7인 데이터는 별도의 처리가 필요합니다.

대표적으로 해시 충돌을 처리하는 방법은 동일한 해시 코드 값을 가진 데이터를 연결 리스트(Linked List)로 연결하는 방식인 체이닝(Chaining)입니다.

아래는 파이썬으로 간단한 해시 테이블을 구현한 예제입니다.

복사
# 해시 테이블 초기화
hash_table = ["", "", "", "", "", "", "", ""]

# 키를 해시 값으로 변환
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(2, 'Apple')
save_data(11, 'Banana')

# 데이터 검색
print("Key2:", read_data(2))
# 출력: Apple
print("Key11:", read_data(11))
# 출력: Banana

위 코드에서 해시 함수 hash_function는 정의되어 있으며, key로 전달된 데이터를 8로 나눈 나머지를 반환합니다.

예를 들어 save_data(11, 'Banana')를 호출하면, 11을 해시 함수에 전달해 3을 반환합니다.

이후 hash_table[3]에 'Banana'를 저장하게 됩니다.

해시 테이블은 키를 사용해 직접 데이터에 접근하기 때문에, 평균적으로 상수 시간 O(1) 안에 데이터의 추가, 검색, 삭제가 가능합니다.

이렇게 해시 테이블은 데이터를 빠르게 검색할 수 있는 자료구조로 데이터베이스, 캐싱(Caching, 데이터 임시 저장) 등 다양한 분야에 활용됩니다.

하지만 동일한 해시 코드로 인한 데이터 검색과 삽입 성능이 상수 시간 O(1)에서 선형 시간 O(n)으로 저하될 수 있습니다.

또한 해시 테이블은 데이터 삽입 순서를 보장하지 않기 때문에, 데이터 순서가 중요한 경우 리스트와 같은 다른 자료구조를 사용하는 것이 적합합니다.