[자료구조] 해시테이블, 해시 함수, 해싱(Hashing), 로드 팩터(Load factor), 개별 체이닝, 오픈 어드레싱

---

해시테이블 

딕셔너리 구조.

가장 큰 특징은 , 대부분의 연산이 시간 복잡도가 O(1)이라는 점.

덕분에 데이터 양에 관계 없이 빠른 성능을 기대할 수 있다.

 

해시 함수

해시 함수란, 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수

 

ABC -> A1

1434BC -> CB

AF32B -> D5

(여기서 화살표 역할을 하는 함수가 바로 해시 함수)

 

해싱(Hashing)

해시 테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱(Hashing)이라 하며,

해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요한 기법 중 하나다.

 

해싱은 최적의 검색이 필요한 분야에 사용되며, 심볼 테이블 등의 자료구조를 구현하기에도 적합하다.

 

 

성능이 좋은 해시 함수의 특징

• 해시 함수 값 충돌의 최소화 (해싱해서 같은 값이 나오지 않게 하는 것. ABC -> A1, 142C -> A1 해싱값이 같으면 input이 다른 것을 알기 어렵다.)
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 값이 균일하게 분포
• 사용할 키의 모든 정보를 이용하여 해싱
• 해시 테이블 사용 효율이 높을 것

 

그렇다면 충돌은 얼마나 많이 발생할까? 생각보다 빈번하게 일어난다.
같은 생일을 가진 사람이 있을 확률은,  생일의 가짓수는 365개이므로, 366명 정도가 있어야 할 것 같지만,
실제로는 23명만 모여도 50%를 넘고, 57명이 모이면 그때부터 99%를 넘어선다.

# 생일 문제를 시뮬레이션하여 23명의 사람들 중에서 같은 생일을 가진 사람이 있는지를 확인하는 코드

def test_birthday_problem():
    import random
    TRIALS = 100000
    same_birthdays = 0

    for _ in range(TRIALS):
        birthdays = []
        for i in range(23):
            birthday = random.randint(1, 365)
            if birthday in birthdays:
                same_birthdays += 1
                break
            birthdays.append(birthday)

    print(f"{same_birthdays / TRIALS * 100}%")


if __name__ == "__main__":
    test_birthday_problem()​

로드 팩터(Load Factor) 방이 얼마나 차 있는가?
해시 테이블에 저장된 개수 n을 버킷의 개수 k로 나눈것
load factor = n / k

저장 공간이 100개가 있을 때 80개의 데이터가 들어있으면 로드팩터 0.8
(공간을 80% 점유)

로드 팩터 비율에 따라서 해시 함수를 재작성해야 될 지 또는 해시 테이블의 크기를 조정해야할 지를 결정한다.
파이썬에서는 해시맵의 디폴트 로드 팩터를 0.66으로 정했으며 '시간과 공간 비용의 적절한 절충안'이라고 얘기한다.

일반적으로 로드 팩터가 증가할 수록 해시 테이블 성능은 점점 감소하게 되며,
자바 10의 경우 0.75를 넘어설 경우 (저장할 수 있는 공간이 4개가 있는데 3개가 찼을 경우)
동적 배열처럼 해시 테이블의 공간을 재할당한다. (어차피 빈공간 많이 없으니까 빈공간을 늘려버림)

 

 

mod(모듈러 연산=나눗셈 연산)

가장 단순하면서도 널리 쓰이는 정수형 해싱 기법

 

h(x) = x mod m

 

여기서 m의 값을 정하는 것이 매우 중요하다. (mod 함수가 결국 해시함수이므로)

m은 해시 테이블의 크기로, 일반적으로 2의 멱수(2의 제곱수, 2, 4, 8, 16 ...)에 가깝지 않은 소수를 선택하는 것이 좋다.

매우 단순한 방법이지만, 실무에서는 이미 많은 키 세트가 충분히 랜덤한 상태고, 실제로 잘 동작한다.

해시 테이블의 크기가 m=10 이라고 가정합니다.
해시 함수는 h(x) = x mod  10입니다.

x=15일 때: h(15)=15mod  10=5
15는 해시 테이블의 5번 인덱스에 저장됩니다.

x=23일 때:h(23)=23mod  10=3
23은 해시 테이블의 3번 인덱스에 저장됩니다.

따라서 m이 해시 테이블의 크기인 이유는 모듈러 연산을 통해 키 값을 항상 0에서 m−1 사이의 유효한 인덱스로 변환할 수 있기 때문입니다. 

 

 

해시함수는 충돌을 최소화하는 것이 중요하다.

충돌이 완전히 없을 수는 없다. 

 

충돌에 대응하는 방법

1. 개별 체이닝

해시 테이블의 기본 방식. 충돌 발생 시 이 그림과 같이 연결 리스트로 연결하는 방식

위와 같이 윤아와 서현의 해시 값이 겹칠 경우.

먼저 온 윤아는 일단 할당한 후, 서현이 와서 충돌했을 때 서현은 윤아에 연결 리스트로 연결한다. (체이닝)

 

흔히 해시 테이블이라고 하면 말하는 방식이 바로 이 개별 체이닝이다.

 

간단한 원리

1. 키의 해시 값을 계산한다.
2. 해시 값을 이용해 배열의 인덱스를 구한다.
3. 같은 인덱스가 있다면 연결 리스트로 연결한다.

잘 구현한다면 대부분의 탐색은 O(1)이지만,

최악의 경우, 즉 모든 해시 충돌이 발생했다고 가정할 경우에는 O(n)이 된다. 

(모두 linked list로 연결되므로 연결 리스트를 쓰는것보다 못함)

 

 

 

2. 오픈 어드레싱

충돌 발생 시, 다른 빈 공간을 찾아서 넣는 방식

충돌이 일어나면, 테이블 공간 내 탐사(Probing)을 통해 빈 공간을 찾아 해결하며, 이 때문에 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다.

위와 같이 유리와 서현이가 겹칠 경우, 늦게 들어온 서현이는 다른 빈공간인 3에 저장하였다.

 

선형 탐사(Linear probing)의 한 가지 문제점은

해시 테이블에 저장되는 데이터들이 고르게 분포되지 않고 뭉치는 경향(성능↓)이 있다는 점이다.(클러스터링) 

또한 오픈 어드레싱 방식은 버킷 사이즈보다 큰 경우에는 삽입할 수 없다.

따라서 일정 이상 채워지면, 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 과정이 일어난다.

 

 

파이썬의 해시 테이블 구현 방식

 

면접 시 "해시 테이블로 구현된 파이썬의 자료형을 제시하라"는 질문을 받는다면 주저 없이 딕셔너리라고 대답할 수 있어야 한다.

 

그렇다면 파이썬의 해시테이블은 충돌 시 어떤 방식을 사용할까?

파이썬의 해시테이블은 오픈 어드레싱 방식으로 구현되어 있다.

 

오픈 어드레싱의 한 방식인 선형 탐사 방식은 일반적으로 체이닝에 비해 성능이 더 좋다.

그러나 슬롯의 80% 이상이 차게되면 급격한 성능 저하가 일어난다.

성능표 (아래=0 에 있을 수록 성능 좋은 것)

 

모던 언어들은 오픈 어드레싱 방식을 채택해 성능을 높이는 대신, 로드 팩터를 작게 잡아 성능 저하 문제를 해결한다.

(0.6 쯤 되었을 때 그냥 미리 방을 더 늘려버리는 방식으로 해결)

 

 

해시테이블의 시간복잡도

Insertion, Deletion, Search : O(1)

으로, 대단히 유용한 자료구조이다.

 

해시 테이블의 핵심 아이디어: 각 입력마다 고윳값을 준다!

"거기 가면 거의 비어있어 or 혼자 있어"를 보장해줌

 

하지만 고윳값을 가지는 게 쉬울까?

ex. 생일 중복 문제 ➡️ 쉽지 않다.

 

➡️  우리가 해시 테이블을 쓸 때 key 값의 중복이 일어나는 경우가 흔할 수 있다.

➡️  상자의 크기를 잘 잡아햐 한다 !

- load factor(공실률): 자바 는 약 0.75, 파이썬 0.66, 루비 0.5

 

➡️  해싱 함수의 성능이 매우 중요함.

보통 많이 사용하는 해싱 함수

• easy -modular 연산
  • x mod m 일 때, m이 해시 테이블의 크기
  •  m은 2의 멱수 ( 거듭제곱수)에 가깝지 않은 소수가 좋다. // 꼭 그래야 하는 건 아님

 

충돌이 일어났을 경우 해결 방법

1. 개별 체이닝 - 링크드 리스트로 쭉쭉 연결하기. 일반적인 방법. 최악의 경우에 탐색 O(n)

2. 오픈 어드레싱 - probing 전략따라 다름. 선형이 제일 쉬움. 클러스터링 문제.

 

파이썬은 체이닝 시 메모리 할당하는  오버헤드가 높아 오픈 어드레싱을 사용한다.

 

CPython Open address 관련 주석 참조 https://github.com/python/cpython/blob/16901c0482734dbd389b09ca3edfcf3e22faeed7/Objects/dictobject.c#L850

 

오버헤드란?

프로그램의 실행흐름에서 나타나는 현상중 하나로 예를 들어 , 프로그램의 실행흐름 도중에 동떨어진 위치의 코드를 실행시켜야 할 때 , 추가적으로 시간,메모리,자원이 사용되는 현상입니다.

한마디로 정의하자면,  오버 헤드는 특정 기능을 수행하는데 드는 간접적인 시간, 메모리 등 자원을 말한다. 

 

예를들어,  10초 걸리는 기능이 간접적인 원인으로 20초걸린다면 오버헤드는 10초가 되는것이다.

 

---

해시 테이블 구현하기

hastable 폴더 아래

structures.py

# hashtable/structures.py

class MyHashTable:
    def __init__(self, size=100):
        """
        해시 테이블 초기화.
        :param size: 해시 테이블의 크기(기본값은 100).
        """
        self.size = size
        self.hashmap = [[] for _ in range(size)]  # 각 슬롯은 (key, value) 쌍의 리스트로 구성됩니다.

    def _hash_function(self, key):
        """
        해시 함수: 키를 해시 테이블의 인덱스로 변환.
        :param key: 해시 테이블에 저장할 키.
        :return: 해시 테이블의 인덱스.
        """
        return hash(key) % self.size

    def put(self, key, value):
        """
        해시 테이블에 키-값 쌍을 삽입합니다.
        :param key: 삽입할 키.
        :param value: 삽입할 값.
        """
        index = self._hash_function(key)
        slot = self.hashmap[index] # 해시 버킷(slot)- 연결리스트 형태

        #  체이닝(Chaining)
        for i, (k, v) in enumerate(slot):
            if k == key:
                slot[i] = (key, value)  # 이미 존재하는 키인 경우 값을 업데이트합니다.
                return

        slot.append((key, value))  # 새로운 키-값 쌍을 추가합니다.

    def get(self, key):
        """
        주어진 키에 해당하는 값을 반환합니다.
        :param key: 검색할 키.
        :return: 키에 해당하는 값 또는 -1 (키가 존재하지 않는 경우).
        """
        index = self._hash_function(key)
        slot = self.hashmap[index]

        for k, v in slot:
            if k == key:
                return v  # 키에 해당하는 값을 반환합니다.

        return -1  # 키가 존재하지 않으면 -1을 반환합니다.

    def remove(self, key):
        """
        주어진 키에 해당하는 키-값 쌍을 삭제합니다.
        :param key: 삭제할 키.
        """
        index = self._hash_function(key)
        slot = self.hashmap[index]

        for i, (k, v) in enumerate(slot):
            if k == key:
                del slot[i]  # 키-값 쌍을 삭제합니다.
                return

    def display(self):
        """
        해시 테이블의 현재 상태를 출력합니다.
        """
        for index, slot in enumerate(self.hashmap):
            print(f"Index {index}: {slot}")

해시맵(hashmap)이라는 용어는 일반적으로 해시 테이블과 같은 구조를 나타내며,

키-값 쌍을 저장하고 검색하는 데이터 구조를 의미합니다.

각 키는 해시 함수를 통해 인덱스로 변환되며, 이 인덱스를 사용하여 값에 빠르게 접근할 수 있습니다.

파이썬에서는 dict가 이러한 해시 테이블을 기반으로 구현되어 있습니다.

 

해시맵(HashMap)과 해시테이블(Hash Table)은 본질적으로 동일한 데이터 구조를 가리키는 용어로, 둘 다 키-값 쌍을 저장하고 검색하는 데 사용됩니다. 그러나 두 용어는 다른 맥락에서 사용되며 약간의 차이가 있습니다.

 

해시 테이블(Hash Table)

• 일반적 개념: 해시 테이블은 키를 해시 함수로 변환하여 인덱스로 사용하고, 이 인덱스를 통해 값을 빠르게 검색할 수 있는 데이터 구조입니다.
• 구현 방식: 해시 테이블은 다양한 언어와 라이브러리에서 구현될 수 있습니다. 충돌 해결을 위해 체이닝(Chaining) 또는 오픈 어드레싱(Open Addressing) 방식을 사용할 수 있습니다.
• 역사적 배경: 해시 테이블이라는 용어는 데이터 구조의 개념과 관련이 있습니다.

해시맵(HashMap)

• 구현체: 해시맵은 해시 테이블을 구현한 특정 클래스나 자료구조를 가리킵니다. 예를 들어, 자바의 HashMap 클래스는 해시 테이블의 한 구현체입니다.
• 언어 종속적: 해시맵이라는 용어는 주로 특정 프로그래밍 언어에서 해시 테이블을 구현한 자료구조를 지칭할 때 사용됩니다. 예를 들어, 자바의 HashMap, C++의 std::unordered_map, 파이썬의 dict 등이 있습니다.
• 추가 기능: 해시맵 구현체는 단순한 해시 테이블의 기능 외에도 다양한 부가 기능을 제공할 수 있습니다. 예를 들어, 동적 크기 조정, 순서 유지(LinkedHashMap), 동기화된 접근 등.

 

• 해시 함수 (_hash_function 메서드):
  • hash() 함수를 사용하여 키를 해시값으로 변환하고, 이를 해시 테이블 크기 self.size로 나눈 나머지를 반환합니다. 이 값은 해시 테이블의 인덱스로 사용됩니다.
• 데이터 삽입 (put 메서드):
  • index는 키의 해시값에 해당하는 인덱스입니다.
  • slot은 해당 인덱스에 위치한 리스트(해시 버킷)입니다.
  • 슬롯을 순회하면서 이미 존재하는 키가 있는지 확인하고, 있으면 값을 업데이트합니다.
  • (체이닝에서는 중복 키가 발생하지 않도록 하는 것이 일반적)
  • 키가 존재하지 않으면 새로운 (key, value) 튜플을 리스트에 추가합니다.
• 데이터 검색 (get 메서드):
  • index는 키의 해시값에 해당하는 인덱스입니다.
  • slot은 해당 인덱스에 위치한 리스트입니다.
  • 슬롯을 순회하면서 키를 찾아 값을 반환합니다.
  • 키가 존재하지 않으면 -1을 반환합니다.
• 데이터 삭제 (remove 메서드):
  • index는 키의 해시값에 해당하는 인덱스입니다.
  • slot은 해당 인덱스에 위치한 리스트입니다.
  • 슬롯을 순회하면서 키를 찾아 삭제합니다.
• 해시 테이블 상태 출력 (display 메서드):
  • 각 인덱스와 해당 슬롯의 내용을 출력합니다.

따라서 slot은 리스트 타입이고, slot 안에 저장되는 (k, v) 쌍은 튜플 타입입니다. 이 구조는 해시 테이블에서 충돌이 발생했을 때 동

일한 인덱스에 여러 개의 (key, value) 쌍을 저장할 수 있도록 합니다.

 

prac.py

from hashtable.structures import MyHashTable


def test_hashtable():
    ht = MyHashTable()

    ht.put(1, 1)
    ht.put(2, 2)
    assert ht.get(1) == 1
    assert ht.get(3) == -1

    ht.put(2, 1)
    assert ht.get(2) == 1

    ht.remove(2)
    assert ht.get(2) == -1



if __name__ == "__main__":
    test_hashtable()

 

hash() 함수

파이썬 내장 함수로, 객체의 해시값을 반환합니다.

해시값은 객체를 고유하게 식별하는 정수 값으로, 주로 딕셔너리의 키나 집합의 원소처럼 고유한 값이 필요한 데이터 구조에서 사용됩니다.

 

특징

• 동일성 보장: 같은 객체에 대해 호출된 hash() 함수는 항상 동일한 해시값을 반환합니다.
• 불변성: 해시값은 객체의 생명 주기 동안 변경되지 않습니다. 따라서 가변 객체(예: 리스트)는 해시 가능하지 않습니다.
• 효율성: 해시값은 효율적으로 계산되어야 하며, 해시 테이블에서 빠른 검색과 삽입이 가능하도록 합니다.

 

• 파이썬의 기본 불변형 객체(정수, 문자열, 튜플 등)는 기본적으로 해시 가능합니다.
• 가변 객체(리스트, 딕셔너리 등)는 기본적으로 해시 가능하지 않습니다. 이는 이 객체들이 변경될 수 있으므로, 동일한 객체에 대해 서로 다른 해시값을 가지게 될 위험이 있기 때문입니다.

 

# 정수 해시
print(hash(42))  # 42

# 부동 소수점 해시
print(hash(3.14))  # 322818021289917443

# 문자열 해시
print(hash("hello"))  # -1300344201447069985 (시드에 따라 다를 수 있음)

# 튜플 해시
print(hash((1, 2, 3)))  # 2528502973977326415

# 사용자 정의 객체 해시
class MyClass:
    def __init__(self, value):
        self.value = value

    def __hash__(self):
        return hash(self.value)

    def __eq__(self, other):
        if isinstance(other, MyClass):
            return self.value == other.value
        return False

obj1 = MyClass(42)
print(hash(obj1))  # 42 (MyClass.__hash__에 의해 반환됨)

hash() 함수는 객체의 타입에 따라 내부적으로 다양한 해시 함수를 사용합니다. 파이썬에서 기본적으로 제공하는 해시 함수는 각 객체 타입에 대해 다르게 구현되어 있습니다.

 

위 코드는 해시 테이블의 내부 작동 원리를 이해하기 위해 직접 해시 테이블을 구현한 것이고,

원래 파이썬에서는 대부분의 경우 딕셔너리를 사용하는 것이 좋습니다.

딕셔너리를 사용하면 매우 간단하게 해시 테이블을 이용한 데이터 저장 및 검색을 할 수 있습니다.

# 딕셔너리 예제
my_dict = {}

# 데이터 삽입
my_dict[1] = 'one'
my_dict[2] = 'two'
my_dict[3] = 'three'

# 데이터 검색
print(my_dict[1])  # 출력: one
print(my_dict.get(4, 'Not Found'))  # 출력: Not Found

# 데이터 삭제
del my_dict[2]
print(my_dict.get(2, 'Not Found'))  # 출력: Not Found

# 딕셔너리 상태 출력
print(my_dict)  # 출력: {1: 'one', 3: 'three'}