[자료구조 및 알고리즘] Ch05. 해시(Hash)

December 26, 2022

해시(Hash)

🔊 패스트캠퍼스 "한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online." 강의를 보고 공부하면서 정리한 노트 게시물입니다.

Ch05-01. 해시

KEY - VALUE 형식
KEY는 중복되지 않는 값으로 설정해야함.

VALUE는 KEY를 기준으로 관리되기 때문

해싱 Hashing

데이터를 빠르게 저장하고 가져오는 기법 중 하나
키에 특정 연산을 적용하여 테이블의 주소를 계산

해시 테이블

(Key, Value) 쌍을 저장
순서 X

main > java > Main.java

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        map.put("Hello", "World");
        map.put("ABC", "DEF");
        map.put("Computer", "Science");

        System.out.println(map.get("Hello"));
        System.out.println(map.get("ABC"));
        System.out.println(map.get("Computer"));
    }
}

Hashing - Key

키를 기준으로 값을 매핑
고유한 값
- 중복 X
- 사람 이름? 아이디?

Hashing - Hash Function

임의의 데이터(키)를 특정 값(해시값)으로 매핑시키는 함수

String의 hashCode()

해시 함수를 통해 데이터의 위치가 관리되기 때문에, 리스트처럼 데이터를 전체 스캔을 하면서 찾을 필요가 없다. 따라서, Hash Function을 통한 데이터의 접근은 시간 복잡도 $O(1)$을 갖게 된다.

(위와 같이 각 문자열의 해시 값을 출력해봄)
좋은 해시 함수
- 키 값을 고르게 분포 시킴
- 빠른 계산
- 충돌 최소화


String의 `hashCode()`

해시 충돌 Hash Collision

키 값이 다른데, 해시 함수의 결과값이 동일한 경우

main > java > hashtable > MyLinkedHashTable.java

충돌이 발생했을 경우 chaining 방식을 이용해서 충돌을 해결하도록 할 것이다.
  
- 해시 충돌이 발생했을 경우 LinkedList를 이용한 chaining 방식으로 해결하도록 (가장 기본적인 방법)
- 데이터는 Node라는 이름의 key-value 쌍을 이뤄서 저장하도록 할 것이다.
  
(해시 맵과 해시 테이블은 같은 개념)

package hashtable;
  
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
  
public class MyLinkedHashTable<K, V> implements IHashTable<K, V> {
    private static final int DEFAULT_BUCKET_SIZE = 1024;
  
    private List<Node>[] buckets;   // hashTable -> chaining
    private int size;
    private int bucketSize;
  
    // 2. 생성자
    public MyLinkedHashTable() {
        this.buckets = new List[DEFAULT_BUCKET_SIZE];  // 2의 10제곱
        this.bucketSize = DEFAULT_BUCKET_SIZE;
        this.size = 0;
        // for문을 돌면서 버킷 칸을 다시 초기화 해줘야함
        for (int i = 0; i < bucketSize; i++) {
            this.buckets[i] = new LinkedList<>();
        } // 이렇게 for문으로 버킷을 각 칸마다 초기화 해주지 않으면,
        // 디폴트로 null이 들어가기 때문에, 데이터를 넣을 수가 없어서 초기화해줘야함
    }
  
    // 3. 사용자가 원하는 크기의 생성자를 만들 수도 있도록
    public MyLinkedHashTable(int bucketSize) {
        this.buckets = new List[bucketSize];
        this.bucketSize = bucketSize;
        this.size = 0;
        for(int i = 0; i < bucketSize; i++) {
            this.buckets[i] = new LinkedList<>();
        }
    }
  
    // 5. 추가 연산
    @Override
    public void put(K key, V value) {
        int idx = this.hash(key); // hash function을 이용해서 가져온 idx로 버킷에 접근하면,
        List<Node> bucket = this.buckets[idx]; // 우리가 데이터를 넣어야할 LinkedList가 있는 버킷 위치가 나옴
        for (Node node : bucket) {
            // (중복된 key일 경우 새로 들어온 value로 덮어 쓰도록 처리)
            if (node.key.equals(key)) {
                node.data = value;
                return;
            }
        }
        Node node = new Node(key, value); // 그리고, 노드를 새로 생성을 해서,
        bucket.add(node); // 버킷에다가 데이터를 넣어주면 됨
        this.size++;
    }
  
    // 6. 데이터를 가져오는 연산
    @Override
    public V get(K key) {
        int idx = this.hash(key);
        List<Node> bucket = this.buckets[idx]; // hash function을 이용해서 가져온 index값으로 버킷에 조회,  List<Node> bucket을 가져옴
        for (Node node : bucket) { // 여러 개의 데이터가 있을 수 있기 때문에
            // key가 동일하다면, (우리가 가져와야 할 값이기 때문에)
            if (node.key.equals(key)) {
                return node.data; // node.data를 가져오고
            }
        }
        return null; // 끝까지 순환했는데도 데이터를 가져오지 못했다면 return null
    }
  
    // 7. 지우는 연산
    @Override
    public boolean delete(K key) {
        int idx = this.hash(key);
        List<Node> bucket = this.buckets[idx];
        // Iterator는 데이터 집합에서 값을 하나씩 꺼내오면서 순환할 수 있도록 도와주는 객체
        for (Iterator<Node> iter = bucket.iterator(); iter.hasNext(); ) { // iterator가 데이터가 남아 있지 않을 때까지 실행을 시킴
            Node node = iter.next(); // 데이터를 하나씩 가져오는 것
            if (node.key.equals(key)) { // 가져오면서 입력받은 키와 동일하다면
                iter.remove();
                this.size--;
                return true; // 정상적 종료가 됐다면
            }
        }
        return false; // 정상적 종료가 되지 않았다면
    }
  
    // 8. key를 입력으로 받아서 key의 데이터가 해시 테이블에 존재하는지, 아닌지 판별
    @Override
    public boolean contains(K key) {
        int idx = this.hash(key);
        List<Node> bucket = this.buckets[idx]; // 그 key값에 해당하는 버킷을 가져오고
        for (Node node : bucket) {
            // node의 key가 입력받은 key와 동일하다면,
            if (node.key.equals(key)) {
                return true; // 해당 데이터는 존재하다고 판별
            }
        }
        return false; // for이 종료될 때까지 찾지 못한 경우
    }
  
    @Override
    public int size() {
        return this.size;
    }
  
    // 4. hash function : 반환하는 값은 나오는 인덱스 값을 반환하도록
    private int hash(K key) { // key로 들어오는게 어떤 타입일지는 모름 generic이기 때문 (언어의 로우 레벨에서는 타입을 하나씩 타 들어가서 하기 때문에, 이거랑 다를 수 있음)
        int hash = 0;
  
        // 문자열 한 글자씩 순환을 하면서, 이 순환된 값을 아스키 int값으로 가져와서,
        for (Character ch : key.toString().toCharArray()) {
            hash += (int) ch; // 해시에다가 각 값을 더해줌 (hash값에 더함)
        } // 해시 값을 더하면, 버킷 사이즈보다 값이 커질 수가 있으니
        return hash % this.bucketSize; // 이 연산을 해서 어떤 값이 나오던 간에 무조건 버킷사이즈보다 작은 값이 나오도록 바꿔줌
    } // 여러가지 방법들이 있지만, 이 방법이 로우 레벨의 자바나 파이썬 런타임에서 많이 쓰는 방식이기 때문
  
    // 1.
    private class Node {
        K key;
        V data;
  
        Node(K key, V data) {
            this.key = key;
            this.data = data;
        }
    }
}

Ch05-02. 해시 충돌

키 값이 다른데, 해시 함수의 결과값이 동일한 경우

해시 충돌을 아예 피할 수 있으면 좋겠지만, 해시 충돌은 절대 피할 수 없다.

필연적으로 발생할 수 밖에 없는데, 컴퓨터 사이언스에서는 이 이유를 비둘기 집 원리로 설명한다.

### 비둘기 집 원리

$N + 1$개의 물건을 $N$개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다

Birthday Problem

임의의 사람 $N$명이 모였을 때 그 중에 생일이 같은 2명이 존재할 확률
생일의 가능한 가짓수는 366개

2월 29일 포함
366명이 모여야 생일이 같은 경우가 있을까?
실제로는 23명만 나와도 50.7%의 확률로 존재
50명인 경우, 97%

Chaining

특정 키에 hash function으로 넣은 해시 값을 index화 해서 데이터를 저장함.

그런데, 다른 키를 넣었는데도 또, 똑같은 해시 값이 나왔다면 똑같은 인덱스 위치를 가리키게 될 것이다. 그리고 이 때, 이미 저장하고 있는 데이터가 있다면, 데이터가 저장된 버킷이 마치 LinkedList처럼 다음 노드를 가리키게 해서, 그 노드에 새로운 데이터를 저장을 하도록 만든다.

그리고, 또 다른 키에서 또 동일한 해시 값이 나온다면, 버킷에 또 새로운 노드를 연결해서 데이터를 삽입하게 될 것이다.

이 모습이 마치 체인이 연결된 것 같다고 해서, Chaining 방법이라고 부르는 것이다.

그래서, 해시 테이블 전체 모양을 보면, 위 그림과 같은 형태로 도식화 할 수 있다.

이런 Chaining 방식으로 해시 충돌을 회피하게 될 경우에는 결국, Hash Function으로 index의 위치를 찾는데 $O(1)$의 시간 복잡도가 걸린다고 해도, index의 위치에서 값을 가져올 때 해당 값을 찾기 위해 또 리스트를 하나씩 탐색하는 과정을 거쳐야 한다.

이 스캔 과정은 리스트에서 설명했다시피 뒤에 노드가 길어질수록 탐색 시간도 같이 늘어나는 $O(N)$의 시간 복잡도를 갖는다.

그렇기 때문에, 최악의 경우 해시 테이블임에도 $O(N)$의 시간 복잡도가 나올 수 있게 되는 것이다.

이렇게 리스트로 Chaining을 구현하는 것이 전통적인 Chaining 연결 방식이지만, 최근 자바에서는 리스트 대신 트리 자료구조를 써서 시간 복잡도를 조금 더 단축시키기도 했다.

Open Addressing

충돌 발생시 다른 버킷에 데이터를 저장
선형 탐색
- 해시 충돌 시 $n$칸을 건너뛴 다음 버킷에 저장
  
  예를 들어, 위 그림처럼 10번 ~ 19번까지 인덱스가 있을 때, 10, 14, 18번 인덱스에 데이터가 들어있는 상황이다.
  
  근데 다른 키를 넣었을 때, 10번 인덱스와 동일한 인덱스를 가리키는 해시 값이 나왔지만, 10번 인덱스에는 이미 다른 데이터가 들어있으니까 이 버킷을 건너뛴 다음 11번 인덱스에 값을 저장하게 된다.
- 계산 단순
- 검색 시간이 많이 소요
  
  만약에, 위 그림 설명 상황에서 11번 버킷에 데이터가 또 있는 상황이라면 1칸 더 건너 뛰어서 12번 인덱스로 들어가야 한다, 근데 또 12번에 있다면 13번..
  
  이런 방식으로 버킷의 위치를 탐색하다보면, 결국 시간 복잡도가 $O(N)$까지 늘어날 수 있기 때문에 검색 시간이 많이 소요될 수 있다.
  
  더 큰 문제는…
- 데이터들이 특정 위치에만 밀집(clustering)
  
  데이터들이 특정 위치에만 밀집하게되는 경우가 생길 수 있다.
  
  좋은 Hash Function은 키를 고르게 분포시킨다고 했는데, 데이터들이 밀집되지 않고 고르게 분포시키는게 왜 중요하냐면, 밀집 될수록, 충돌로 데이터의 위치를 재탐색해야할 일이 많아지기 때문이다. 이것은 결국 성능의 저하를 의미하게 되고, 데이터가 밀집되는 것은 결코 좋은 현상이 아니다.
  
  예를 들어서, 이렇게 10번 인덱스에는 값이 있기 때문에, 11, 12번 위치의 인덱스까지 해시 충돌로 인해서 Open Addressing방식으로 다시 검색된 위치에 데이터가 들어있는 버킷이다.
  
  이렇게 데이터가 들어가있는 상황에서 또 다른 키 값을 넣었을 때, 이번에는 인덱스의 위치가 12가 나오게 되는데 이렇게 되면, 12번 버킷에는 또 데이터가 들어있기 때문에 13번 위치에 데이터를 저장을 할 수 밖에 없다.
  
  그러면, 위 그림처럼 12번을 건너뛴 13번 위치에 데이터를 저장을 해야될 것이다. 그럼 지금 이 그림 상에서는 10번부터 14번까지의 키가 나온다면 전부 다 선형 탐색으로 다시 위치를 찾아줘야하는 인덱스가 되는 것이다.
  
  이렇게 데이터가 밀집되는 현상을 clustering이라고 한다.
  
  그래서, 이 clustering 현상을 피하기 위해서 ‘제곱 탐색’이라는 방법도 나왔다.
제곱 탐색
- $N^2$칸(1, 4, 9, 16, …)을 건너뛴 버킷에 데이터를 저장
- 데이터들이 특정 위치에 밀집하는 문제를 해결
  
  데이터가 촘촘히 밀집되는게 아니라, 데이터 간의 간격이 넓어지기 때문에 이전과 같은 clustering 현상을 피할 수 있을 것이다.
- 하지만 처음 해시 값이 같다면 여전히 …
  
  처음 Hash Function을 통해 나온 Hash값이 동일하다면 마찬가지로, 건너뛴 칸의 개수도 똑같기 때문에, 똑같이 $N$번의 탐색을 할 수 있다는 문제가 여전히 발생을 하게 된다.
  
  그래서 나온 방법은 ‘이중 해시’라는 방법이다.
이중 해시
- 해시 값에 다른 해시 함수를 한번 더 적용
- Hashfunction1(): 최초의 해시 값을 구함
- Hashfunction2(): 충돌 발생시 이동 폭을 구함
  
  2번째 해시 함수는 충돌이 발생했을 때 돌리는 해시 함수이다.
  
  충돌이 발생했을 때, 몇 칸을 이동할지를 이 Hash Function을 통해서 구하게 된다.
- 최초 해시 값이 같더라도 이동 폭이 다르기 때문에 clustering 문제 해결 가능

이 방법은 버킷을 탐색하는데 있어서 규칙성을 아예 없애버린 방법

🔊 캡쳐 이미지는 패스트캠퍼스(Fast Campus) 소유이므로, 무단 불펌하지 말아주세요!

맨 위로 이동하기

Share on

Twitter Facebook LinkedIn

Devvoo

[자료구조 및 알고리즘] Ch05. 해시(Hash)

해시(Hash)

🔊 패스트캠퍼스 "한 번에 끝내는 컴퓨터 공학 전공필수 & 인공지능 심화 초격차 패키지 Online." 강의를 보고 공부하면서 정리한 노트 게시물입니다.

Ch05-01. 해시

해싱 Hashing

해시 테이블

Hashing - Key

Hashing - Hash Function

해시 충돌 Hash Collision

Ch05-02. 해시 충돌

Birthday Problem

Chaining

Open Addressing

🔊 캡쳐 이미지는 패스트캠퍼스(Fast Campus) 소유이므로, 무단 불펌하지 말아주세요!

Share on

Leave a comment

You may also enjoy

2024년, 오랜만에 올리는 포스팅

[컴퓨터 네트워크] Ch01. 컴퓨터 네트워크와 인터넷

[자료구조 및 알고리즘] Ch06. 정렬(sort)

[자료구조 및 알고리즘] Ch02. 리스트(List)