자료구조 - 해시테이블

해싱(hashing)이란

각각 데이터를 고유한 숫자 값으로 표현하고 이를 이용해 특정 데이터의 존재 여부를 확인하거나 데이터를 추출하는 작업

 

해시 함수(hash function)란

주어진 데이터(key)를 고유한 숫자 값인 해시(Hash Value)로 표현해 주는 함수이다.

•  키는 해시 함수의 입력 부분으로 데이터 자체이거나 구분하는 값이다.
• 해시 값은 해시 함수의 출력 부분으로 뒤에 후술할 해시 테이블의 인덱스가 된다.

이러한 해시 함수를 통해 데이터를 고유한 숫자 값으로 변환하고, 해시 테이블에 접근해 데이터를 조회하거나, 추출한다.

 

---

해시테이블(Hash Table)

1. 데이터가 저장되는 곳
2. 해시 함수를 통해 산출된 값을 인덱스로 하여 해당 데이터를 저장
3. 서로 다른 키가 해시 함수를 통과하면서 같은 해시 값을 가지게 되면 충돌이 일어난다.

key(키) : 데이터를 찾기 위한 고유 식별자로 중복 X

Value(값) : 키와 연결된 실제 데이터, 중복 저장 O

해시 함수 : 키의 값을 입력받아 고정된 길이의 숫자로 변환하는 함수

버킷 : 실제 데이터가 저장되는 메모리 공간(배열의 각 요소)

해시 테이블: 버킷들의 배열

 

바나나로 살펴보자

• 바나나를 해시함수에 넣으면 04라는 값이 나온다
• 이때 바나나라는 키의 해시 값은 04가 된다.
• 이렇게 해시 함수를 통해 산출된 해시 값은 해시 테이블의 인덱스가 된다.
• 해시 테이블의 04번 인덱스가 가리키는 곳은 1800원이 저장되어 있다.(바나나의 가격)

 

사과와 배를 보면 해시 함수를 통과하면서 같은 해시 값을 가지게 되는데 이런 경우는 충돌이 일어난다.

 

---

해시 충돌(Collision)

1. 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써 해시 테이블에 같은 위치에 2개 이상의 데이터가 저장되려는 현상이다.
2. 해시 충돌을 해결하는 대표적인 방법으로는 Chaining 기법과, Open Addressing 기법이 있다.

 

Chaining 기법

• 해시 테이블 저장공간 이외의 공간을 활용하는 기법이다.
• 연결 리스트를 활용한다.

3000원은 사과 가격

1. 사과와 배가 해시 함수를 통해 02라는 같은 해시 값을 가진다.
2. 사과 가격 3000원 뒤에 연결 리스트를 사용해 배의 가격을 추가한다.

 

Open Addressing 기법

• 다른 주소를 사용해 충돌을 해결하는 방법이다.
• 오픈 주소법에서는 3가지 방법이 있다.
  • Linear Probing
  • Quadratic Probing
  • Double Hashing
• 연결 리스트를 사용하지 않는다는 점에서 Chaining 기법과 차이가 있다.

 

Linear Probing(선형탐사) 기법

03에 배의 가격이 들어갔다.

1. 사과와 배가 같은 해시 값을 가진다.
2. 중복되는 해시 값인 02의 다음 값 03부터 순회하여 빈 공간을 찾는다.
3. 03이 비어있다면 빈 공간에 배의 가격을 입력한다.

 

Quadratic Probing(제곱 탐사) 기법

 

1. 사과와 배가 같은 해시 값을 가진다.
2. 빈 공간을 찾기 위해 제곱수로 이동한다.
3. 먼저 1의 제곱수로 이동하여 빈 공간인지 확인한다.
4. 만약 빈공이 아니라면 2의 제곱수만큼 (4칸)을 이동한다.
5. 비어있다면 빈 공간에 배의 가격을 넣는다.

선형 탐사와 제곱탐사의 문제점?

규칙성으로 인해 위치가 정해져 있다.

 

Double Hashing(이중해싱) 기법

1. 사과와 배가 같은 해시 값을 가진다.
2. 해시 값에 한번 더 해싱하여 규칙성을 없앤다.
3. 만약 한번 더 해싱하여도 같은 빈 공간이 없다면 또 해싱하여 빈 공간을 찾아간다.

 

---

해시 테이블의 장단점과 사용 사례

장단점

장점	단점
검색 속도가 빠르다	충돌이 발생할 수 있다.
중복 검사 과정이 빠르고 간단하다.  - 키를 기준으로 데이터를 저장하므로	메모리 사용량이 많다  - 배열 기반이므로 빈공간이 생길 가능성이 높다.
유연한 키-값 저장과 동적으로 크기 조절이 가능하다.  - 다양한 타입의 데이터 저장 가능	데이터 삽입 순서를 보장하지 않는다.

 

 

해시 테이블 사용

• 중복확인이 쉬워 웹페이지 캐시를 구현할 때 사용한다. (바뀐 정보의 유무를 빠르게 조회할 수 있다.)
• 키 - 값 형태의 연관 데이터를 다룰 때 주로 사용된다.
• 파이썬의 딕셔너리 타입도 해시테이블 기법을 사용한다.
  • 해시테이블의 개념을 이용해 파이썬의 딕셔너리를 구현했다.
  • 파이썬은 선형조사 방식으로 충돌을 해결한다.
  • 파이썬 3.6 버전부터는 순서가 보장된다. -> 메모리 절약

 

---

코드 구현

간단한 해시 테이블 구현하기

class SimpleHashTable:
    def __init__(self, size=10):
        self.size = size
        # 지정된 크기만큼 빈 버킷을 생성
        self.table = [[] for _ in range(self.size)]

    def _hash_function(self, key):	#해시함수
        # 파이썬 내장 hash() 결과의 절대값을 테이블 크기로 나눈 나머지 활용
        return abs(hash(key)) % self.size

    def put(self, key, value):	#데이터 삽입과 수정
        hash_index = self._hash_function(key)
        bucket = self.table[hash_index]

        # 같은 키가 버킷에 존재하는지 확인 (존재하면 값 업데이트)
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        # 새로운 키라면 버킷에 추가
        bucket.append((key, value))

    def get(self, key):	# 데이터 검색 
        hash_index = self._hash_function(key)
        bucket = self.table[hash_index]

        # 버킷을 돌며 키가 일치하는 데이터를 탐색
        for k, v in bucket:
            if k == key:
                return v
        return None # 찾는 데이터가 없을 때
        
# 크기가 10인 해시 테이블 생성
fruit_market = SimpleHashTable(10)

# 데이터 저장 (과일 이름 - 가격)
fruit_market.put("Apple", 3000)
fruit_market.put("Banana", 1500)
fruit_market.put("Cherry", 5000)

# 데이터 조회
print("Apple의 가격:", fruit_market.get("Apple"), "원")   # 출력: 3000 원
print("Banana의 가격:", fruit_market.get("Banana"), "원") # 출력: 1500 원

# 해시 테이블 확인하기
print("\n--- 과일 마켓 해시 테이블 내부 상태 ---")
for idx, bucket in enumerate(fruit_market.table):
    print(f"버킷 {idx}: {bucket}")

 

출력결과

 

 

 

해시 충돌 예제 (체이닝 기법)

class ChainingHashTable:
    def __init__(self, size=5):
        self.size = size
        # 해시 테이블 생성
        # 충돌 시 여러 데이터를 담기 위해 리스트로 초기화.
        self.table = [[] for _ in range(self.size)]

    def _hash_function(self, key):
        # 파이썬 내장 해시 사용을 위해 abs(hash(key))
        return abs(hash(key)) % self.size

    def put(self, key, value):
        hash_index = self._hash_function(key)
        bucket = self.table[hash_index]

        # 같은 키가 있다면 값을 업데이트 (중복 방지)
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        # 같은 키가 없다면 리스트의 뒤에 추가(체이닝)
        bucket.append((key, value))

    def get(self, key):
        hash_index = self._hash_function(key)
        bucket = self.table[hash_index]

        # 해당 인덱스를 돌며 키 탐색
        for k, v in bucket:
            if k == key:
                return v
        return None  # 찾으려는 과일이 없을 경우
        
        


# 해시 테이블 생성
fruit_market = ChainingHashTable(3)

# 데이터 삽입
fruit_market.put("Apple", 3000)
fruit_market.put("Banana", 1500)
fruit_market.put("Cherry", 5000)
fruit_market.put("Melon", 4000)
fruit_market.put("Grape", 2000)

# 데이터 출력
print("--- [조회 결과] ---")
print(f"Apple의 가격: {fruit_market.get('Apple')}원")
print(f"Melon의 가격: {fruit_market.get('Melon')}원")
print(f"없는 과일(Pear): {fruit_market.get('Pear')}")

# 체이닝 시각화
print("\n--- [해시 테이블 내부 버킷 구조] ---")
for idx, bucket in enumerate(fruit_market.table):
    # 한 버킷에 데이터가 2개 이상 있다면 충돌이 발생하여 체이닝된 상태
    print(f"버킷 {idx}: {bucket}")

 

 

출력결과

 

 

실행을 할 때마다 결과가 다르게 나오는데,,,

    def _hash_function(self, key):
        # 파이썬 내장 해시 사용을 위해 abs(hash(key))
        return abs(hash(key)) % self.size
        
        !!! 이 코드 때문 !!!!

 

파이썬 내장 함수를 사용했는데 파이썬은 보안상의 이유로 새로 실행될 때마다 내부적으로 사용할 임의의 비밀 난수를 생성한다.

실행할 때 마다 새로운 난수 값을 부여하기 때문에 해시 함수 결과 값이 바뀐다.

=> 당연히 테이블 크기로 나눈 나머지 값(%3)도 다르게 나오는 것!!!

 

아스키코드 값을 더하는 방식으로 대체 할 수 있다.