파이썬 해시법

해시법

해시법이란 '데이터를 저장할 위치 = 인덱스'를 간단한 연산으로 구하는 것을 의미한다.

아래의 표를 보며 해시법의 단어들을 자세히 설명해보겠습니다.

 

 

키			5	6	14	21	25	34
해시값(6으로 나눈 나머지)			5	0	2	3	1	4

이렇게 키의 값을 배열의 크기(길이)나 특정 기준으로 나눈 것을 해시값이라고 합니다.

해시값은 데이터에 접근할 때 기준 인덱스가 됩니다. 

 

 

위에서 구한 해시값을 인덱스로 하여 원소를 새로 저장한 배열을 해시 테이블이라고하며, 아래와 같습니다.

6

25

14

21

34

5

 

-키를 해시값으로 변환하는 과정(나누는 과정)을 해시 함수라고 합니다.

 

_해시 테이블에서 만들어진 원소(=배열 한 칸)를 버킷이라고 합니다.

 

 

_만약 위의 해시 테이블에 18이라는 키값을 추가하고 싶을 때

18의 나머지는 0 즉 해시값이 0이므로, 0에는 이미 6이라는 값이 들어있습니다.

 

이때 저장할 버킷이 중복되는 현상을 충돌이라고 합니다.

 

 

해시법에서 충돌을 해결하는 방법은 총 2가지가 있습니다.

 

1. 체인법 : 해시값이 같은 원소를 연결리스트로 관리하는 것

2. 오픈 주소법 : 빈 버킷을 찾을 때 까지 해시를 반복하는 것

 

 

---

 

 

먼저 체인법에 대해서 알아보겠습니다.

 

_체인법이란 해시값이 같은 데이터를 체인 모양의 연결 리스트로 연결하는 방법을 말하며, 오픈 해시법이라고도 합니다.

 

 

#해시법에서 해시값을 각 버킷에 저장할 때는 해시값 인덱스에 바로 저장하는 것이 아닌 인덱스를 해시값으로 하는 연결 리스트의 앞쪽 노드를 참조하는 것입니다.

체인법을 파이썬으로 구현하기 위해서는 먼저 Node 클래스와 ChainedHash 클래스를 만들어야 합니다.

 

먼저 Node 클래스는 개별 버킷을 나타내며 키에 해시 함수를 적용하여 해시값을 구합니다.

 

_Node 클래스

from typing import Any, Sequence

class Node:
    # 해시를 구성하는 노드

    def __init__(self, key: Any, value: Any, next: Node) -> None:
        """ 초기화 """

        self.key = key     # 키
        self.value = value # 해시값
        self.next = next   # 뒤쪽 노드를 참조

 

_ChainedHash 클래스

from typing import Any, Sequence

class ChainedHash:
    # 해시를 구성하는 노드

    def __init__(self, capacity: int) -> None:
        """ 초기화 """

        self.capacity = capacity                # 해시 테이블의 길이 지정
        self.table = [None] * self.capacity     # 해시 테이블(리스트) 선언


    def hash_value(self, key: Any) -> int:
        """ 해시 값을 구하는 해시 함수 """

        if isinstance(key, int):
            return key % self.capacity

 

 

---

 

키로 원소 검색하기

_ 파이썬 코드

    def search(self, key: Any) -> Any:
        """ 키가 key인 원소를 발견하면 값을 반환 """
        hash = self.hash_value(key) # 해시 함수로 만든 해시 값
        p = self.table[hash]        # 해시 값의 인덱스를 p로 지정

        while p is not None:
            if p.key == key:        
                return p.value      # 검색 성공 
            p = p.next              # 뒤쪽 노드로 이동

        return None # 끝까지 찾지 못하였으므로 실패 반환

 

코드 프로세스

1. 해시 함수를 사용하여 키를 해시값으로 변환합니다.

2. 해시값을 인덱스로하는 버킷에 주목(=변수로 지정)합니다.

3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 스캔하며, 키와 같은 값이 발견되면 검색에 성공하고, 원소의

맨 끝까지 스캔했음에도 같은 값이 발견되지않는다면 검색에 실패합니다.

 

 

 

---

 

원소를 추가하기

_ 파이썬 코드

    def add(self, key: Any, value: Any) -> bool:
        """ 키가 key이고 값이 value인 원소를 추가 """

        hash = self.hash_value(key) # 해시 함수로 만든 해시 값
        p = self.table[hash]        # 해시 값의 인덱스를 p로 지정

        while p is not None:
            if p.key == key:        
                return False        # 검색 성공 
            p = p.next              # 뒤쪽 노드로 이동

        temp = Node(key, value, self.table[hash]) # temp라는 노드 만들기
        self.table[hash] = temp                   # 만든 노드 해시값에 참조 시키기
        return True                               # 추가 성공

 

코드 프로세스

1. 해시 함수를 사용하여 키를 해시값으로 변환합니다.

2. 해시값을 인덱스로 하는 버킷에 주목합니다.

3. 버킷이 참조하는 연결리스트를 맨 앞부터 차례로 선형검색합니다.

키와 같은 값이 발견되면 이미 키가 등록되어있는 경우이기에 추가에 실패합니다.만약 원소 끝까지 발견 되지 않으면 해시값인 리스트의 맨 앞에 노드를 추가합니다

 

 

 

---

 

원소를 삭제하기

_ 파이썬 코드

    def remove(self, key: Any) -> bool:
        """ 키가 key인 원소를 삭제 """

        hash = self.hash_value(key) # 해시 함수로 만든 해시 값
        p = self.table[hash]        # 해시 값의 인덱스를 p로 지정
        pp = None                   # 바로 앞의 노드를 주목

        while p is not None:
            if p.key == key:        # 키를 발견하면 아래를 실행
                if pp is None:        
                    self.table[hash] = p.next   # 뒤쪽 노드가 삭제할 값을 무시하고 해시값에 참조하게 합니다.
                else:
                    pp.next = p.next # 뒤쪽 노드가 가리키는 곳을 앞의 노드가 참조하게 한다.
                return True
            pp = p        
            p = p.next               # 뒤쪽 노드를 주목
        
        return False                 # 삭제 실패

 

 

코드 프로세스

1. 해시 함수를 사용하여 키를 해시값으로 변환합니다.

2. 해시값을 인덱스로 하는 버킷에 주목합니다.

3. 버킷이 참조하는 연결 리스트를 맨 앞부터 차례로 선형 검색합니다. 키와 같은 값이 발견되면 그 노드를 리스트에서 삭제합니다.

그렇지 않으면 삭제에 실패합니다.

 

 

삭제를 이해하기 쉽게 하는 이미지 설명

 

# 한마디로 삭제라는 단어보다 무시라는 단어 즉 참조하는 곳을 바꿔주면서 없애고싶은 원소를 외톨이로 만들어버린다

이렇게 이해하시면 편할 것 같습니다!!!