[Algorithm] 해시

해시란?

• 해시(Hash)는 입력 데이터를 고정된 길이의 데이터로 변환된 값
• 해시 함수에 의해 얻게 되며, 다른 말로는 해시값, 해시코드, 체크섬이라고 함
• 간단하게 말하자면, 데이터의 KEY 값이 해시 함수를 통해서 변환된 간단한 정수
• 이렇게 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하거나 검색할 때 활용

---

해시 함수란?

해시 함수는 데이터를 고정된 크기의 고유한 값으로 변환시키는 함수.

해시는 보안, 검색, 데이터베이스 등 다양한 분야에서 사용되며, 주로 데이터의 무결성 검증이나 데이터의 일치 여부를 확인하기 위해 사용.

해시 함수는 입력값의 길이가 달라도 항상 일정한 길이의 값을 출력하고 이때 출력값은 고유한 값이므로 같은 입력값에 대해서는 항상 같은 해시값이 출력됨.

해시 함수의 일반적 특징

1. 입력값이 조금만 변해도 출력값이 완전히 달라짐.
2. 출력값을 통해 입력값을 유추하기 어려움
3. 동일한 입력값에 대해서는 항상 동일한 출력값을 반환.

이러한 특징들로 인해 해시는 보안 문제에서 많이 사용되며, 비밀번호의 암호화나 인증 과정에서도 사용.

하지만 해시 함수는 입력값이 같은 경우 항상 같은 출력값을 반환하기 때문에, 해시값을 미리 계산해 놓은 해시테이블에서는 충돌이 발생할 수 있어 충돌을 방지하기 위해서 충돌을 최소화할 수 있는 해시함수를 사용해야 함.

• sha256

• 지응/ 지웅의 결과값이 매우 다름을 확인할 수 있음

---

해시 테이블이란?

Hash table(hash map)이란 해시함수를 사용해서 변환한 값을 index로 삼아 key와 value를 저장하는 자료구조를 말한다.

다시 말해 해시 테이블은 어떤 특정 값을 받아서 해시 함수에 입력하고, 함수의 출력값을 인덱스로 삼아 데이터를 저장한다.

파이썬의 dictionary, 루비의 Hash, 자바의 Map이 해시 테이블의 대표적인 예다.

해시 테이블의 특징을 나열해보자.

• 기본 연산으로는 search, insert, delete가 있다.
• 순차적으로 데이터를 저장하지 않는다.
• key를 통해서 value를 얻을 수 있다. => 이진탐색트리나 배열에 비해서 속도가 획기적으로 빠름
• 커다란 데이터를 해시해서 짧은 길이로 축약할 수 있기 때문에 데이터를 비교할 때 효율적이다.
• value는 중복 가능하지만 key는 유니크해야 한다.
• 수정 가능하다. (=> mutable)
• 보통 배열로 미리 hash table 사이즈만큼 생성 후에 사용한다.

해시 테이블은 key-value가 1:1 매핑되어 있기 때문에 검색, 삽입, 삭제 과정에서 모두 평균적으로 O(1)의 시간복잡도를 갖는다.

---

해시 충돌(Hash Collision)

위에서 살펴본 함수에도 단점이 존재하는데, 해시 함수는 입력 값의 길이가 어떻든 고정된 길이의 값을 출력하기 때문에 입력값이 다르더라도 같은 결괏값이 나오는 경우가 있습니다. 이것을 해시 충돌(Hash Collision)이라고 표현하며, 해시 충돌이 적은 함수가 좋은 해시함수라고 불립니다.

위 이미지를 보면 "ARGOS"와 "MINIBEEF"라는 key값이 해시 함수를 거쳤는데 둘 다 15라는 동일한 값을 출력했습니다. 이를 해시 충돌이라고 하는데 좀 더 상세하게 알아보기 위해서 먼저 적재율(load factor)의 개념을 알아야 합니다.

적재율(load factor)이란 해시 테이블의 크기에 대한 키의 개수의 비율을 뜻합니다. 즉 키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 때 적재율은 K/N이 됩니다.

해시 충돌이 발생하지 않을 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1)에 실행되지만, 충돌이 발생하는 경우에는 탐색과 삭제 연산이 키의 개수인 O(K)만큼이 걸리게 됩니다.

위와 같이 HashMap은 키 집합인 정의역과, 값 집합인 공역의 대응에 해시 함수를 이용하기에 해시 충돌이 하나도 일어나지 않는 해시 함수를 만드는 것은 비둘기집 원리에 의해 불가능합니다. 따라서 해시 충돌에 대해 안전하다는 해시 함수는 '충돌이 거의 일어나지 않는다'라는 의미를 뜻합니다.

결론적으로 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우에는 비둘기집 원리에 의해 해시 충돌은 항상 존재하며, 해시 테이블의 충돌을 해결하기 위해서는 해시 충돌을 완화하는 방향으로 문제를 해결해야 합니다.

---

해시 충돌 완화 방법

해시 충돌을 완화하는 방법에는 크게 Open Addressing과 Separating Chaining 방법이 있습니다.

• 개방 주소법(open addressing): 해시 테이블 크기는 고정하면서 저장할 위치를 찾는다.
• 분리 연결법 (separate chaining): 해시 테이블의 크기를 유연하게 만든다.

각각의 방법에 대해 한번 알아보겠습니다.

1. 개방 주소법(open-address)

open addressing은 한 버킷 당 들어갈 수 있는 엔트리는 하나이지만 해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방법입니다. 즉, open addressing의 주요 목적은 저장할 엔트리를 위한 다음의 slot을 찾는 것인데 예시로 다음과 같습니다.

그림을 살펴보면, John Smith와 Sandara Dee 152번으로 동일한 값이 나옵니다. 해시 충돌이 일어난 경우인데, Sandara Dee는 152번에 덮어 씌워지지 않고, 다음 빈 버킷인 153번에 들어간 것을 확인할 수 있습니다. 다음 key인 Ted Baker는 153이라는 값이 나왔지만 이미 Sandra Dee가 저장되어 있기에 충돌이 발생해서 다음 빈 버킷인 154번에 저장되었습니다.

예시는 무조건 한 칸씩 찾는 방법을 예로 들었지만 비어있는 칸을 찾아가기 위해서 아래와 같은 다양한 방법들이 존재합니다.

(1) Linear probing(선형 탐사법)

(2) Quadratic probing(제곱 탐사법)

(3) Dobule hashing(이중 해싱)

(1) Linear Probing(선형 탐사법)

말 그대로 가장 간단하게 선형으로 순차적 검색을 하는 방법입니다.

해시 함수로 나온 해시 값(index)에 이미 다른 값이 저장되어 있다면, 해당 해시값에서 고정된 폭만큼 옮겨 다음 빈칸을 찾아가는 방법입니다.

위 이미지를 보면 52라는 값을 해싱하여 해시값 2에 접근했지만 이미 존재하여 충돌이 났음을 알 수 있습니다. 따라서 임의의 고정된 크기인 한 칸씩 옮겨서 빈칸을 찾아가며 최종적으로 6에 저장되는 것을 확인할 수 있습니다.

• 이 경우에는 간단하지만 특정 해시 값의 주변이 모두 채워져 있는 일차 군집화(primary clustering) 문제가 발생할 수 있습니다. 위 이미지만 해도 2~6까지 데이터가 모여있는 것을 확인할 수 있는데, 모든 키가 2라는 값으로 해시값이 나올 경우 군집화 된 값들을 순차적으로 방문할 텐데 해시 성능이 크게 저하될 수 있습니다.
• Linear Probing(선형 탐사법)은 해시 충돌이 해시 값 전체에 균등하게 발생할 때 유용한 방법

(2) Quadratic probing(제곱 탐사법)

제곱 탐사법은 위의 선형 탐사법과 동일한데, 탐사 폭이 고정된 값이 아니라 제곱으로 늘어나는 점에 있어 차이가 있습니다. 즉, 빈 버킷의 slot을 찾기 위해 고정된 값이 아닌 2^1, 2^2, 2^3.... 의 방식으로 이동해서 빈칸을 찾습니다.

• 제곱 탐사법을 이용한 경우 데이터의 밀집도가 선형 탐사법보다 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 가능성 낮음
• 하지만 선형 탐사법보다는 캐시의 성능이 떨어져서 속도의 문제가 발생
  • 배열의 크기가 커지게 되면서 L1, L2 캐시 적중률(hit ratio)이 낮아지기 때문

(3) Dobule hashing(이중 해싱)

이중해싱법 또는 재해싱은 항목을 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법입니다. 이 방법은 항목들을 이전 방법들보다 해시 테이블에 보다 균일하게 분포시킬 수 있으므로 효과적인 방법이라 할 수 있습니다.

하나는 처음의 key를 저장할 index를 찾기 위한 것이고, 나머지 하나는 충돌 발생 시 저장할 index를 찾기 위한 것이며, 충돌 발생 시 저장할 index를 찾기 위한 해시 함수는 첫 번째 해시 함수와 달라야 합니다.

이중 해싱법은 충돌의 발생 가능성은 가장 적음

• 하지만 캐시의 성능은 Linear Probing, Quadratic Probing과 비교했을 때 가장 좋지 않으며, 추가적인 해시 연산이 들어가기에 가장 많은 연산량을 요구

개방 주소법(open-address) 정리

탐사 방식에 따라 open-addressing 해시의 성능이 달라지지만, 가장 치명적인 영향을 미치는 요소는 바로 해쉬 테이블의 적재율인 load factor(전체 슬롯에서 사용 중인 슬롯 비율)입니다. Load Factor가 100%로 증가할수록 데이터를 찾거나 삽입하기 위해 필요한 탐사 횟수는 비약적으로 증가합니다. 일단 테이블이 꽉 차게 되면 probing이 실패하여 끝나버리기도 하는데, 아래 표는 Load Factor에 따른 평균 성공 탐색수와 실패수를 보여줍니다.(http://egloos.zum.com/sweeper/v/925740)

open - addressing 성능 정리

위 표를 잘 보면 아무리 좋은 해시 함수를 쓰더라도 일반적으로 Load Factor는 80% 이내까지만 좋은 성능을 보여주는 것을 알 수 있습니다. 특히 Linear probing 방식이 Load Factor가 높을수록 가장 급격하게 성능 저하가 발생하는 것을 확인할 수 있습니다.

따라서 Load Factor가 임계점을 넘어 큰 경우의 성능은 double hashing > quadratic > linear의 순서로 나타낼 수 있습니다.

2. 분리 연결법 (separate chaining)

• 한 버킷(슬롯) 당 들어갈 수 있는 엔트리의 수에 제한을 두지 않음
• 이때 버킷에는 링크드 리스트(linked list)나 트리(tree)를 사용

• 동일한 값들은 리스트로 연결되어 저장
• 따라서 해시 충돌이 일어나더라도 리스트로 노드가 연결되기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다
• 하지만 open addressing 방법과 비교했을 때 추가적인 메모리 공간이 필요하며, 테이블의 적재율(Load Factor)에 따라 선형적으로 성능이 저하
• 따라서 적재율이 작을 경우 즉, 데이터가 적은 경우에는 open addressing 방식이 평균적으로 더 빠름

💡 Java 8 HashMap에서는 링크드 리스트로 저장하다가 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리(Red-Black Tree)로 변경 다시 삭제되어서 6개 이하가 될 경우엔 트리를 링크드 리스트로 변경

---

Java 코드

// 기본적인 해시 테이블 구현
public class Hash {

    // Hash table
    public Slot[] hashTable; // 배열 형태로 선언

    // Hash 객체를 생성할 때 table 사이즈 지정
    public Hash(Integer size) {
        this.hashTable = new Slot[size];
    }

    // Slot에는 value를 가짐
    public class Slot {

        String value;

        Slot(String value) {
            this.value = value;
        }
    }

    //Hash function
    public int hashFunction(String key) {
        return (int)(key.charAt(0)) % this.hashTable.length; // 나머지
    }

    // 입력 받은 key를 해시 함수로 인덱스화 하고, 해당 인덱스에 value 저장
   public boolean saveData(String key, String value) {

        // key는 해시 함수를 거쳐서 해시 값(해시, 해시 주소)을 반환 -> 여기선 배열의 index와 동일
        Integer address = this.hashFunction(key);

        if(this.hashTable[address] != null) { // 해당 주소에 이미 데이터가 있을 경우
            this.hashTable[address].value = value;
        } else {
            this.hashTable[address] = new Slot(value);
        }

        return true;
    }

    // key에 해당하는 값을 반환
    public String getData(String key) {

        // key는 해시 함수를 거쳐서 해시 값(해시, 해시 주소)을 반환
        Integer address = this.hashFunction(key);

        if(this.hashTable[address] != null) {
            return this.hashTable[address].value;
        } else {
            return null;
        }
   }

   public static void main(String[] args) {

        Hash myHash = new Hash(20);

        myHash.saveData("Lee","30000");
        myHash.saveData("James","15000");
        myHash.saveData("Denny","5000");

        System.out.println(myHash.getData("Lee"));
        System.out.println(myHash.getData("James"));
        System.out.println(myHash.getData("Denny"));

    }

출력

30000
15000
5000

 

 

출처

SHA256 해시 - 온라인 SHA256 해시 생성기 (convertstring.com)

자료구조 | 해시 테이블 hash table (velog.io)

해시 자료구조와, 해시 충돌 그리고 Java의 HashMap 동작 방법 (tistory.com)

https://kang-james.tistory.com/entry/자료구조-해시HASH-알아보기

 

 

+ 오늘의 노래

 

Daily Look (Feat. Silly Boot)

아티스트

Hash Swan

앨범

Shangri-La

발매일

1970.01.01