[자료구조 & 알고리즘] Hash 함수와 충돌 Map, Set, Table 구현체

Hash

• 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것.
• 해시함수를 구현하여 데이터값을 해시값으로 매핑시킨다.
• 내부적으로 array를 사용해 데이터를 저장. 데이터 고유의 인덱스로 key의 고유 숫자 값이 저장됨.
• 특정 데이터만의 고유한 위치이기 때문에 삽입 연산 시 다른 데이터 사이에 끼어들어나 삭제시 다른 데이터로 채울 필요가 없음. 즉 추가적인 비용이 없도록 만들어진 구조.

 

---

 

Hash Table

해시 테이블은 <Key, Value>로 데이터를 저장하는 자료 구조 중 하나이다. Key값에 해시 함수를 적용해 index를 생성하고, index를 활용하여 값을 저장, 검색 할 수 있다. Key값을 해싱하여 검색, 저장하므로 평균 시간 복잡도는 O(1)이다. (항상 O(1)이 아닌 것은 collision 해소 때문)

하지만 data가 많아지면 다른 데이터가 같은 해시 값을 가져 충돌하는 collision현상이 일어난다.

 

---

 

Hash Collision

해시 충돌은 해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 말한다. 따라서 서로 다른 Key값이 동일한 index로 매핑 될 경우, 해시 충돌이 발생하여 해시 테이블의 성능을 저하시킨다.

위 그림에서 John Smith와 Sandra Dee라는 키의 해시가 서로 충돌을 일으킨다.

---

충돌 해결 방법

 

• 분리 연결법 ( 체이닝 - separate chaining )Java 7 은 분리 연결법으로 HashMap을 구현하고 있다.
  • Linked List
  • 각각의 버킷을 linked list로 만들어 충돌이 발생하면 해당 버킷의 list에 추가하는 방식. 연결리스트를 사용하므로 삽입과 삭제가 간단하나 작은 데이터들을 저장할 때 연결리스트 자체의 오버헤드가 부담이 된다. Open Address 방식에 비해 테이블 확장을 늦출 수 있다.
  • Tree ( Red-Black Tree] )기준은 하나의 버킷에 할당된 data의 갯수가 6개, 8개를 기준. 변경하는데 소요되는 비용을 줄이기 위함.
  • 만약 버킷에 6개가 들어있다가 1개가 추가되면? 기준이 6, 7이라면 링크드리스트에서 트리로 자료구조를 변경해야함. 그러나 바로 하나가 삭제되면 다시 자료구조를 변경해야함. 즉 Switching cost가 과다하게 발생하기 때문에 2라는 여유를 잡아둔 것이다.
  • linked list 대신 tree를 사용하며, 하나의 버킷에 할당된 데이터(key-value)쌍의 수가 많을 때 사용한다. 데이터가 적으면 Linked List가 맞음 (tree는 기본적으로 메모리 사용량이 크기 때문.)
• 보조 해시 함수(supplement hash function)을 함께 사용하여 충돌가능성을 낮추고 Worst Case에 가까워지는 경우를 줄인다.
• 동일한 버킷의 데이터에 대해 추가 메모리와 자료구조를 사용하여 다음 데이터의 주소를 저장하는 것이다. 보통 linked list와 tree를 사용하여 구현한다. 일반적으로 개방주소법보다 빠르다. (개방주소법은 밀도가 높아질수록 Worst Case 발생 빈도가 높아지기 때문.)

• 개방 주소법 (open address )
  • Linear Probing (선형 탐사)
  • 충돌이 난 지점부터 정해진 고정폭으로 순차적 탐색하며 비어있는 버킷을 찾는다.
  • Quadratic Probing (제곱 탐사)
  • 2차 함수를 사용하여 비어있는 버킷을 찾는다.
  • Double Hashing Probing
  • 충돌이 발생하면 2차 해시 함수를 사용하여 새로운 주소를 할당한다. - 연산량이 위의 두가지보다 많이 요구된다.
• 해시함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용. 기존의 해시 테이블의 비어있는 공간을 활용하는 방법이다. 최악은 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치로 돌아올 수 있다. 비어있는 공간을 찾는 방법은 크게 3가지 방법이 있다.

 

비교

• 두 방식 모두 Worst Case에서 O(M). 하지만 개방주소법은 연속된 공간이기때문에 분리연결법에 비해 캐시 효율이 높다. 때문에 데이터가 적다면 개방주소법의 성능이 좋다. 하지만 분리연결법은 버킷을 계속 사용하지 않기때문에 테이블 확장을 늦출 수 있다는 장점이 있다.

충돌이 일어나도 해시 테이블을 쓰는 이유는?

하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면 작은 메모리로도 프로세스 관리가 가능하기 때문.

• 빠른 데이터 검색.
• hash-table O(1), 이진탐색트리 O(logN)

 

 

Resizing

해시 테이블은 Key, Value쌍이 늘어날수록 해시 충돌 확률이 올라가며 성능이 떨어진다. 충돌을 줄여 성능 손실 문제를 해결하기 위해 임계점을 지나면 버킷의 수를 두배로 늘린다. 기준 임계점은 빈공간 대비 75%(0.75=load factor)가 사용될 때이다.

java의 버킷 개수 기본값은 16. 임계점 후 2배씩 최대 2^30까지 확장.

동적확장(https://d2.naver.com/helloworld/831311)

---

 

Hash Function ( Hash method)

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터(hashcode)로 매핑하는 함수이다. 즉 고유한 인덱스값을 만들어낸다. 이는 저장되는 key의 값들을 작은 범위의 값으로 변환하기 위함이다.

해시 함수의 성능은 입력 영역에서 해시 충돌 확률로 결정되는데, 해시 충돌 확률이 높을수록 서로 다른 데이터를 구별하기 어려워지고 검색하는 비용이 증가한다. Collision이 많아질수록 시간복잡도는 O(1)에서 O(n)에 가까워진다.

좋은 해시함수는 무조건 1:1 매칭을 만드는 것이 아니라 Collision을 최소화 하는 방향으로 설계된 함수이다. 무조건적인 1:1매칭은 과다한 메모리를 소모한다.

해시 테이블에서는 크게 4가지 해시 함수가 사용된다.

• Division Method주소 = 입력값 % 테이블 크기
• 모듈러 연산을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다.
• Digit Folding Method
• 각 Key의 문자열을 ASCII 코드로 바꾼 뒤, 그 값의 합을 주소로 사용하는 방법이다.
• Multiplication MethodHash(Key) = (Key * R(0..1) % 1) * 2^n
• 숫자로 된 Key와 0과 1 사이의 실수, 보통 2의 제곱수를 사용하여 해시값을 계산한다.
• Universal Hashing
• 다수의 해시 함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만든다.

퍼즐조각 채우기 hash funcion으로 풀이

from collections import defaultdict

block_hashs = [0] * 4
block_size = 0

def solution(game_board, table):
    N = len(game_board)
    row_base = 1 << 1
    column_base = 1 << N
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    global block_hashs

    def dfs(board, x, y):
        visited[x][y] = 1
        global block_size, block_hashs
        block_size += 1
        row_exponent = [x, N - y, N - x, y]
        column_exponent = [y, x, N - y, N - x]
        for k in range(4):
            block_hashs[k] += ((row_base ** row_exponent[k]) *
                               (column_base ** column_exponent[k]))
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= nx < N and 0 <= ny < N):
                continue
            if not board[nx][ny] or visited[nx][ny]:
                continue
            dfs(board, nx, ny)

    def process_hash(hash_values):
        for i, hash_value in enumerate(hash_values):
            for hash_base in [row_base, column_base]:
                while hash_value % hash_base == 0:
                    hash_value //= hash_base
            hash_values[i] = hash_value
        return min(hash_values)

    visited = [[0] * N for _ in range(N)]
    game_board_inverted = [[1 - x for x in row] for row in game_board]
    game_board_hash = defaultdict(int)
    block_size_by_hash = {}
    for x in range(N):
        for y in range(N):
            if not game_board_inverted[x][y] or visited[x][y]:
                continue
            block_hashs = [0] * 4
            global block_size
            block_size = 0
            dfs(game_board_inverted, x, y)
            block_hash = process_hash(block_hashs)
            game_board_hash[block_hash] += 1
            block_size_by_hash[block_hash] = block_size

    visited = [[0] * N for _ in range(N)]
    answer = 0
    for x in range(N):
        for y in range(N):
            if not table[x][y] or visited[x][y]:
                continue
            block_hashs = [0] * 4
            dfs(table, x, y)
            block_hash = process_hash(block_hashs)
            if game_board_hash[block_hash] > 0:
                game_board_hash[block_hash] -= 1
                answer += block_size_by_hash[block_hash]
    return answer

---

 

Hash Table vs Hash Map vs Hash Set

3개의 자료구조는 모두 해시함수를 사용한다. 그러나 다음과 같은 차이가 있다.

맵은 set보다 메모리를 더 쓴다. 때문에 키 존재유무만 궁금하면 set을 쓰는게 맞다.

	Hash Table	Hash Map	Hash Set
동기화	o	x	x
값의 중복	o	o	x
인터페이스	Map	Map	Set

 

---

Python의 dict, set

파이썬의 hash function, table 구현: https://davinci-ai.tistory.com/19

간단한 구현: https://idm101.tistory.com/3

dictobject entry의 struct

setobject entry의 struct

언뜻 보면 비슷해 보이지만 큰 차이가 있다. dictentry에는 value를 가르키는 주소값이 추가로 저장되어 있고 setentry에는 value없이 key만 저장하고 있음을 알 수 있다. 실제로 c 코드를 보니 set에는 value가 없고 dict에는 key, value로 매핑되어 있는지 확실히 알 수 있다.

 

그럼 set에서 pop하면?

hash table을 구현해보면 알겠지만 hash table을 순회하면 첫번째 bucket부터 안의 키를 순회하고 다음 bucket으로 가는 식으로 순회한다.
이렇게 순회를 하니 pop을 한다고 가장 뒤에 있는 값까지 순회해서 내뱉는 것이 아닌 가장 처음에 나온 값을 뱉게되는 것이다.

setobject.c에서 pop method

간단히 말하면, while에서 존재하는 key가 나올 때까지 순회를 하고 나오면 해당 key를 return한다.

Reference

• cpython dict 구현체
• cpython set 구현체
• Python hash_table class

 

더 알고싶다면?

• 파이썬의 메모리 관리 기법
• c++ map, set, multi
• javascript의 Hashmap 구현
• ES6 collections
• js의 Map괴 set객체
• js의 Map괴 set객체2
• Java의 해시 충돌 회피