[자료구조] 해시[Hash]

해시함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

해시함수는 단방향 암호화 기법으로 해시를 만든다.

(단방향 암호화 기법은 암호화는 가능하지만 복호화는 불가능한 알고리즘이다.)

 

추가적인 개념에 대해서도 알아보자.

 

 

https://study-grow.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-hash-%EA%B5%AC%ED%98%84-python

 

 

• 키[Key] : 매핑 전 데이터의 값 
• 해싱[Hashing] : 매핑하는 과정 
• 해시값[Hashing Value] : 매핑 후 데이터의 값 
• 해시 테이블[Hash Table] : 해시값에 의해 직접 접극이 가능한 데이터 구조
• 슬롯[Slot] : 한 개의 데이터를 저장할 수 있는 공간

 

해시함수의 장점은 아래와 같다.

1. 접근/탐색 속도가 빠르다 

2. 키에 대한 데이터의 중복확인이 쉽다. (같은 입력값에 대해서는 같은 출력값을 보장하기 때문이다.)

 

파이썬에서는 딕셔너리[Dictionary]라는 자료구조를 통해 해시를 제공한다.

딕셔너리와 리스트[List]의 시간복잡도를 비교해보자.

 

 

https://yunaaaas.tistory.com/46

 

 

원소가 많아질수록 딕셔너리가 삽입, 삭제, 탐색에서 속도가 빠른 것을 확인할 수 있다.

 

하지만 빠른 처리속도는 단점이 될 수 있다. 무차별 대입 공격을 받을 수 있기 때문이다.

(하지만 해결 방법은 있다. 다음에 알아보자.)

 

그리고 해시 함수의 다른 단점은 여러 키에 해당하는 주소가 동일할 경우 충돌이 일어난다.

해시의 동작 원리를 보면 이해할 수 있다.

 

 

먼저, 'apple'라는 문자열을 가지고 해시값을 만들어보자.

 

 

'apple'로 해시값 만들기

 

 

SHA-1은 해시값의 크기를 160으로 고정하는 알고리즘이다.

hashlib는 SHA 함수를 가지고 있는 라이브러리이다.

결과는 'apple'이라는 문자열을 SHA-1로 해시값을 출력한 것이다.

 

SHA-1 외에도 SHA-256이 있다.

이는 해시값의 크기가 256으로 더 안전한 알고리즘이다.

sha1() 대신에 sha256()을 사용하면 된다.

 

 

이제 해시 테이릅을 구현해보자.

 

 

class HashTable:
    def __init__(self):
        self.hash_table = list([0 for i in range(8)])

    def hash_function(self, key):
        return key % 8

    def insert(self, key, value):
        hash_value = self.hash_function(hash(key))
        self.hash_table[hash_value] = value

    def read(self, key):
        hash_value = self.hash_function(hash(key))
        return self.hash_table[hash_value]

    def print(self):
        print(self.hash_table)

 

 

해시 함수는 key % 8로 설정했다.

해시 테이블의 공간은 8자리이다.

 

insert 함수를 이용해 key와 value를 넣고

read 함수를 통해 key를 이용해 value를 찾을 수 있다.

 

 

아래를 실행해보자.

 

H = HashTable()
H.insert('사과', 'apple')
H.insert('오렌지', 'orange')

 

 

[0, 0, 0, 0, 0, 'apple', 0, 'orange'] 이런 결과를 얻을 수 있다.

 

그러나 충돌이 일어나면, 아래 결과처럼 될 수 있다. 해시 함수의 결괏값이 겹쳐서 발행한 일이다.

[0, 'orange', 0, 0, 0, 0, 0, 0]

 

하지만 충돌을 방지할 방법은 있다. 충돌 해결 알고리즘에 대해 알아보자.

 

1. Chaining 기법

2. Linear Probing 기법

3. 공간 확장 기법

 

 

 

아래 블로그를 참고하여 작성했습니다.

 

 

https://davinci-ai.tistory.com/19

파이썬으로 구현하는 자료구조 요약 정리 - 해쉬 테이블(Hash Table)