[자료구조/알고리즘] - 해시 테이블

janjanee·2021년 4월 30일
0

자료구조/알고리즘

목록 보기
10/10

[자료구조/알고리즘] - 해시 테이블


해시 함수

임의의 데이터를 받아서 특정 해시값을 반환하는 함수



출처 : https://www.varonis.com/blog/the-definitive-guide-to-cryptographic-hash-functions-part-1/

해시 함수 특징

  • 일관성이 있어야 한다.
    • "dog"을 넣었을 때 반환되는 값은 항상 "06d80eb0..." 이어야 한다.
  • 다른 데이터가 들어오면 다른 해시값이 나와야 한다.
    • 어떤 데이터가 들어와도 동일한 값이 반환된다면 좋은 해시 함수가 아니다.

해시 테이블

Key 값을 입력 받아 해시 함수로부터 반환된 Hash Code를 배열의 Index로 환산해서 데이터에 접근하는 방식

특징

  • 어떤 것과 다른 것 사이의 관계를 모형화 할 수 있다.
  • 키(key)값(value)를 가진다.
  • 해시 맵(hash maps), 맵(maps), 딕셔너리(dictionaries), 연관 배열(associative arrays)이라는
    이름으로도 알려져 있다.
  • 해시 함수와 배열을 결합.

예시

  • 상품(key)의 가격(value)을 저장하고 싶다!

  • 해시테이블에 해시 함수 반환값을 Index로 잡고, 각 항목의 가격을 추가한다.

  • "APPLE"의 가격을 알고 싶다면

    "APPLE"을 해시 함수에 넣으면 Index: 5를 반환하고 해당 인덱스의 값이 가격이다.

    → 시간복잡도 : O(1)

충돌

해시 함수는 서로 다른 데이터일 때, 서로 다른 해시값을 반환한다고 하였으나,

사실 정확하게 이렇게 할 수 있는 해시 함수를 만드는 것은 거의 불가능(비둘기집 원리)하다.

비둘기집 원리 : 5마리 비둘기가 있고 비둘기 집이 4개라면 아무리 균등하게 비둘기를 집에 넣더라도
최소한 한 집에는 비둘기가 2마리 이상 들어감.
→ 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우

  • 첫 글자에 따라 해시값을 반환하는 해시 함수를 만들었다.
    • ex) "A"로 시작하면 0, "B"로 시작하면 1, "C"로 시작하면 2 를 반환
  • "APPLE"과 "BANANA"의 가격을 각각 0과 1 Index에 잘 저장했다.
  • 그리고 "AVOCADO"를 넣으려고 한다. "A"로 시작해서 0 Index에 넣어야 하는데
    이미 "APPLE"이 공간을 차지하고 있다!?→ 충돌 (collsion)

충돌을 해결하기 위해 여러 방법이 있는데 가장 간단한 방법은 같은 버킷여러 개의 키리스트로 만든다.

  • "APPLE"과 "AVOCADO"가 같은 버킷에 리스트로 할당되었다.

극단적인 예를 들어보자.

가지고 있는 상품이 모두 "A"로 시작한다고 가정하면 아래와 같은 문제가 발생한다.

  • 해시 테이블이 한 버킷만 빼고 모두 비어있다. 그 한 버킷에는 거대한 연결 리스트가 존재.
  • 결국 해시 테이블이 느려지게 된다. → O(n)

결론

  • 해시함수를 잘못 만들면 충돌 현상이 발생한다.

  • 충돌현상을 방지하기 위해 좋은 해시함수를 만들어야 한다.

    → 각 버킷에 고르게 분포할 수 있도록

  • 낮은 사용률

    • 사용률(load factor)해시 테이블에 있는 항목의 수 / 해시 테이블에 있는 공간의 수
      • (항목의 수: 2 / 배열의 크기: 5) → 사용률: 0.4
    • 사용률이 1보다 크다는 것은 배열 공간의 수 보다 항목의 수가 더 많다는 것
    • 보통 사용률이 0.7 보다 커지면 리사이징한다.

충돌 해결

충돌 해결은 크게 세 가지 방법이 존재한다.

  • Separate Chaining

    • 동일한 버킷의 데이터에 대해 추가 메모리를 사용하여 다음 데이터의 주소를 저장
    • 해시테이블의 확장이 필요없고 간단하게 구현 가능
    • 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아져서 효율성 떨어짐.
  • Open Addressing

    • 비어있는 해시테이블의 공간을 활용

    • 지정한 메모리 외 추가적인 저장공간이 필요없음.

    • 삽입, 삭제 시 오버헤드가 적다.

    • 비어있는 해시를 찾는 규칙에 따라 아래의 방법으로 세분화됨.

      • Linear Probing(선형 탐색) : 고정폭 만큼 이동하여 차례대로 빈 버킷을 검색

        출처 : https://stackoverflow.com/questions/27742285/what-is-primary-and-secondary-clustering-in-hash/36526945

        • 특정 해시값 주변 버킷이 모두 채워져 있는 primary clustering(특정 영역에 원소가 몰리는 현상) 문제에 취약
        • 52~56 해시값에 데이터가 모두 저장되어 있기 때문에 삽입하려는 임의의 키 최초 해시값이 52와 같다면 탐색을 적어도 5번 해야한다.
      • Quadratic Probing(제곱 탐색) : 고정폭이 아니고 폭이 제곱수로 늘어나는 방식

        출처 : https://stackoverflow.com/questions/27742285/what-is-primary-and-secondary-clustering-in-hash/36526945

        • 처음 충돌이 발생한 경우에는 1^2만큼 그 다음 충돌이 발생하면 2^2, 3^2, ... 씩 옮긴다.
        • 여러 개의 서로 다른 키들이 동일한 초기 해시값(Initial Probe)을 갖는 문
          secondary clustering에 여전히 취약.
        • 초기 해시값이 같으면 다음 탐색 위치 또한 동일하게 때문이다.
          • 초기 해시값이 7인 데이터를 넣으려면 선형 탐색 기법보다 더 큰 폭으로
            이동을 한다해도 탐색을 4번이나 수행해야 함.
      • Double Hasing(이중 해시) : 다른 해시함수를 한번 더 적용해서 나온 해시를 통해 데이터를 저장.

        • 2개의 해시함수를 준비해서 하나는 최초의 해시값을 얻을 때, 또 다른 하나는 해시충돌이
          일어났을 때 탐색 이동폭
          을 얻기 위해 사용.
        • 최초 해시값이 같더라도 탐색 이동폭이 달라지고, 탐색 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering을 모두 완화
        • 위의 두 방법들 보다 연산 수행이 더 많음.
  • Resizing

    • 위의 두 방법으로도 효율성이 좋아지지 않으면, 버킷의 개수를 확장해야 한다.
    • 더 큰 버킷을 가지는 배열을 새로 생성 후, 새로운 배열에 기존 데이터의 해시값을 다시 계산해서
      복사(재배치)한다.

해시 테이블 vs 배열 vs 연결리스트

  • 평균적인 경우, 해시 테이블의 탐색, 삽입, 삭제는 배열과 연결리스트 장점을 모두 갖춘만큼 빠르다.
  • 최악의 경우에는 해시 테이블이 가장 느림.
  • 해시 테이블에서 최악의 상황을 발생하지 않게 하려면 충돌을 피해야 한다.

해시 테이블 구현 - Java 코드

Separate Chaining

public class ChainHash {

    /** 해시를 구성하는 노드*/
    class Node {
        private String key;
        private int value;
        private Node next;

        public Node(String key, int value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        String getKey() {
            return key;
        }

        int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

    }

    private int size;       //  해시 테이블 사이즈
    private Node[] table;   //  해시 테이블

    public ChainHash(int size) {
        table = new Node[size];
        this.size = size;
    }

    /** 해시 값 구하기 */
    public int hashValue(String key) {
        int hashcode = 0;
        for (char c : key.toCharArray()) {
            hashcode += c;
        }
        return hashcode % size;
    }

    /** key를 이용하여 value 검색*/
    public int search(String key) {
        int hash = hashValue(key);
        Node p = table[hash];

        while (p != null) {
            if (p.getKey().equals(key))
                return p.getValue();
            p = p.next;
        }

        return -1;
    }

    /** 요소 추가 */
    public void add(String key, int value) {
        int hash = hashValue(key);
        Node p = table[hash];

        while (p != null) {
            if (p.getKey().equals(key)) {
                p.setValue(value);
                return;
            }
            p = p.next;
        }

        Node tmp = new Node(key, value, table[hash]);
        table[hash] = tmp;
    }

    /** 요소 삭제 */
    public void remove(String key) {
        int hash = hashValue(key);
        Node p = table[hash];
        Node pp = null;     // 바로 앞 노드

        while (p != null) {
            if (p.getKey().equals(key)) {
                if (pp == null)
                    table[hash] = p.next;
                else
                    pp.next = p.next;
                return;
            }

            pp = p;
            p = p.next;
        }
    }

    /** 전체 해시 테이블 출력 */
    public void dump() {
        for (int i = 0; i < size; i++) {
            Node p = table[i];
            System.out.printf("%02d  ", i);
            while (p != null) {
                System.out.printf("->  %s (%s)  ", p.getKey(), p.getValue());
                p = p.next;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        ChainHash ch = new ChainHash(7);

        ch.add("APPLE", 1500);
        ch.add("AVOCADO", 2000);
        ch.add("ALMOND", 800);
        ch.add("BANANA", 1000);
        ch.add("MANGO", 3000);
        ch.add("KIWI", 900);
        ch.add("POTATO", 2000);
        ch.add("TOMATO", 1300);
        ch.add("CUCUMBER", 1100);
        ch.add("MELON", 3500);
        ch.add("CHERRY", 2000);
        ch.add("PLUM", 1700);
        ch.add("PEAR", 1500);
        ch.add("GARLIC", 500);

        ch.dump();

        ch.remove("POTATO");
        ch.add("MANGO", 5000);

        System.out.println("======");

        ch.dump();
    }

}

결과

00  ->  GARLIC (500)  ->  KIWI (900)  
01  ->  MELON (3500)  
02  ->  PEAR (1500)  ->  POTATO (2000)  ->  ALMOND (800)  
03  ->  PLUM (1700)  ->  CUCUMBER (1100)  
04  ->  BANANA (1000)  
05  ->  AVOCADO (2000)  
06  ->  CHERRY (2000)  ->  TOMATO (1300)  ->  MANGO (3000)  ->  APPLE (1500)  
======
00  ->  GARLIC (500)  ->  KIWI (900)  
01  ->  MELON (3500)  
02  ->  PEAR (1500)  ->  ALMOND (800)  
03  ->  PLUM (1700)  ->  CUCUMBER (1100)  
04  ->  BANANA (1000)  
05  ->  AVOCADO (2000)  
06  ->  CHERRY (2000)  ->  TOMATO (1300)  ->  MANGO (5000)  ->  APPLE (1500)

Open Addressing - Linear Probing

public class OpenHash {

    /** 버킷 상태 */
    enum Status {
        OCCUPIED, EMPTY, DELETED
    }

    /** 버킷 */
    class Bucket {
        private String key;
        private int value;
        private Status stat;

        public Bucket() {
            stat = Status.EMPTY;
        }

        void set(String key, int value, Status stat) {
            this.key = key;
            this.value = value;
            this.stat = stat;
        }

        void setStat(Status stat) {
            this.stat = stat;
        }

        String getKey() {
            return key;
        }

        public void setValue(int value) {
            this.value = value;
        }

        int getValue() {
            return value;
        }
    }

    private int size;           //  해시 테이블 사이즈
    private Bucket[] table;     //  해시 테이블

    public OpenHash(int size) {
        table = new Bucket[size];
        for (int i = 0; i < size; i++)
            table[i] = new Bucket();
        this.size = size;
    }

    /** 해시 값 구하기 */
    public int hashValue(String key) {
        int hashcode = 0;
        for (char c : key.toCharArray()) {
            hashcode += c;
        }
        return hashcode % size;
    }

    /** 재해시 값 구하기 */
    public int rehashValue(int hash) {
        return (hash + 1) % size;
    }

    /** key를 이용하여 Bucket 검색 */
    private Bucket searchBucket(String key) {
        int hash = hashValue(key);
        Bucket p = table[hash];

        for (int i = 0; p.stat != Status.EMPTY && i < size; i++) {
            if (p.stat == Status.OCCUPIED && p.getKey().equals(key))
                return p;
            hash = rehashValue(hash);   //  재해시
            p = table[hash];
        }
        return null;
    }

    /** key를 이용하여 value 검색*/
    public int search(String key) {
        Bucket p = searchBucket(key);
        if (p != null)
            return p.getValue();
        return -1;
    }

    /** 요소 추가 */
    public Bucket add(String key, int value){
        Bucket s = searchBucket(key);
        if (s != null) {
            s.setValue(value);
            return s;
        }

        int hash = hashValue(key);
        Bucket p = table[hash];
        for (int i = 0; i < size; i++) {
            **if (p.stat == Status.EMPTY || p.stat == Status.DELETED) {**
                p.set(key, value, Status.OCCUPIED);
                return p;
            }
            **hash = rehashValue(hash);
            p = table[hash];**
        }

        return null;
    }

    /** 요소 삭제 */
    public Bucket **remove**(String key) {
        Bucket p = searchBucket(key);
        if (p == null)
            return null;

        **p.setStat(Status.DELETED);**
        return p;
    }

    /** 전체 해시 테이블 출력 */
    public void dump() {
        for (int i = 0; i < size; i++) {
            System.out.printf("%02d ", i);
            switch (table[i].stat) {
                case OCCUPIED -> System.out.printf("%s (%s) - init hash: %s \n",
                        table[i].getKey(), table[i].getValue(), hashValue(table[i].getKey()));
                case EMPTY -> System.out.println("-- EMPTY --");
                case DELETED -> System.out.println("-- DELETED --");
            }
        }
    }

    public static void main(String[] args) {
       OpenHash oh = new OpenHash(15);

        oh.add("APPLE", 1500);
        oh.add("AVOCADO", 2000);
        oh.add("ALMOND", 800);
        oh.add("BANANA", 1000);
        oh.add("MANGO", 3000);
        oh.add("KIWI", 900);
        oh.add("POTATO", 2000);
        oh.add("TOMATO", 1300);
        oh.add("CUCUMBER", 1100);
        oh.add("MELON", 3500);
        oh.add("CHERRY", 2000);
        oh.add("PLUM", 1700);
        oh.add("PEAR", 1500);
        oh.add("GARLIC", 500);

        oh.dump();

        System.out.println("==========");

        oh.remove("APPLE");
        oh.dump();

        System.out.println("==========");
        System.out.println(oh.search("MANGO"));

    }
}

결과

00 CHERRY (2000) - init hash: 11 
01 PEAR (1500) - init hash: 11
02 GARLIC (500) - init hash: 14 
03 TOMATO (1300) - init hash: 3 
04 MELON (3500) - init hash: 4 
05 PLUM (1700) - init hash: 3 
06 POTATO (2000) - init hash: 6 
07 -- EMPTY --
08 ALMOND (800) - init hash: 8 
09 KIWI (900) - init hash: 8 
10 APPLE (1500) - init hash: 10 
11 MANGO (3000) - init hash: 10
12 BANANA (1000) - init hash: 12 
13 CUCUMBER (1100) - init hash: 13 
14 AVOCADO (2000) - init hash: 14 
==========
00 CHERRY (2000) - init hash: 11 
01 PEAR (1500) - init hash: 11 
02 GARLIC (500) - init hash: 14 
03 TOMATO (1300) - init hash: 3 
04 MELON (3500) - init hash: 4 
05 PLUM (1700) - init hash: 3 
06 POTATO (2000) - init hash: 6 
07 -- EMPTY --
08 ALMOND (800) - init hash: 8 
09 KIWI (900) - init hash: 8 
10 -- DELETED --
11 MANGO (3000) - init hash: 10
12 BANANA (1000) - init hash: 12 
13 CUCUMBER (1100) - init hash: 13 
14 AVOCADO (2000) - init hash: 14 
==========
3000

References

profile
얍얍 개발 펀치

0개의 댓글