[내일배움캠프 19일차] 해시 함수, heap

해싱

해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것.

 

왼쪽으로부터 오른쪽 값을 만들어내는 가장 간단한 로직.

h(x) = x mod m

쉽게 말해 나눗셈 연산.

h(x)가 생성된 결과, m은 테이블의 크기.

m을 정하는 것이 중요, 2의 제곱수에 가깝지 않은 소수를 선택하는 것이 좋음.

---

개별 체이닝

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

해시 테이블이라고 하면 거의 이 방식을 말함.

---

오픈 어드레싱

충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식.

자신의 해시값과 일치하는 주소에 저장된다는 보장이 없음.

윤아가 2번을 먼저 할당받는다면 서현은 해싱 값은 2 이지만 한칸 올라가 3에 저장됨.

---

Magic method

def __len__(self):
    # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
    return len(self.items) - 1

이런 식으로 __에 둘러쌓인 메서드를 Magic method라고 함.

class BinaryMaxHeap:
    def __init__(self):
        # 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
        self.items = [None]

    def __len__(self):
        # len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
        return len(self.items) - 1

    def _percolate_up(self):
        # percolate: 스며들다.
        cur = len(self)

원래는 len이라는 내장 메소드를 이용해 길이를 구하지만, 힙에서는 0번째 인덱스에 None이 할당되므로 보통의 길이보다 -1한 값을 길이로 사용해야 한다.

그래서 Magic method로 -1한 __len__을 선언하고 아래에서 필요한 경우 len을 사용하여 덮어쓰는 것.

---

오늘의 회고

금요일이라 집중이 잘 안된다.
생각했던 것보다 진도 덜나감.
다음주에 열심히 하자