해시(hash)

자료구조 및 알고리즘

M9M9 2020. 9. 6. 00:27

해시란 다양한 길이를 가진 데이터(key)를 고정된 길이를 가진 암호화된 데이터(value)로 변환시키는 것이다.

암호화된 데이터는 단방향 암호화로 이루어진 특성을 가지고 있으며, 이러한 특성으로 인해 패스워드 설정, 블록체인 등에 사용한다.

또한, 해시는 해시 테이블(hash table)이라는 곳에 key와 value가 한 쌍으로 저장된다. 그리고 key값이 해시 함수를 통해 변환된 후, 다른 작업을 거쳐 배열의 인덱스로 변환된다.

그래서 이 배열의 인덱스를 이용해서 value를 찾을 수 있으므로 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 된다.

결론은 해시를 사용하면 장점은

1. key에 대한 암호화

2. 검색과 저장을 빠르게 할 수 있다!

위의 두 사진처럼 임의의 길이의 데이터를 입력해도 고정된 길이의 암호화된 데이터를 반환한다.

※결정론적:

결정론적 알고리즘(deterministic algorithm)은 예측한 그대로 동작하는 알고리즘이다. 어떤 특정한 입력이 들어오면 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 내놓는다.

해시 충돌이란 해시 함수가 서로 다른 두개의 입력값(key값)에 대해 동일한 출력 값(hash)을 내는 상황을 의미한다.

이러한 해시 충돌은 해시 함수를 이용한 자료구조나 알고리즘의 효율성을 떨어뜨린다. 그러므로 해시 함수는 해시 충돌을 최소화되게끔 만들어야 한다.

(해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력 값을 생성하는 경우에는 해시 충돌이 항상 존재한다고 한다.)

해시 테이블은 연관 배열 구조를 이용하여 키(key)에 결과 값(value)을 저장하는 자료구조이다.

※연관 배열:

연관 배열은 자료구조의 하나로, 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.

해시 테이블 - 위키백과, 우리 모두의 백과사전

위키백과, 우리 모두의 백과사전.

ko.wikipedia.org

해시(Hash)란 무엇인가?

해시 (Hash) 해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행됩니다! 아주 빠르게 진행될 수 있는 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가)

siyoon210.tistory.com

Hash, Hashing, Hash Table(해시, 해싱 해시테이블) 자료구조의 이해

0_HJVxQPQ-eW0Exx7M.jpeg DATA들이 사용하기 쉽게 정리되어 있다. 자료구조는 도대체 무엇일까? 자료구조(Data-Structure)는 데이터들의 모임, 관계, 함수, 명령 등의 집합을 의미한다. 더 쉽게 표현하자면, 1)

velog.io