해시

해시 (Hash)

해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 빠르다. 검색과 저장이 빠른 이유는 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, 해시 알고리즘을 통해 key값이 배열의 인덱스로 변환된다. 따라서 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 된다. 하지만 충돌(Collison)이 일어나는 경우 O(N)의 시간복잡도를 가지게 된다. 충돌은 따로 밑에서 설명하겠습니다.

키(key) : 고유한 값이며, 해시 함수의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 최종 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있다.
해시함수(Hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키(key)를 일정한 길이를 가지는 해시(hash)로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 해시 충돌(Hash Collision)이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
해시(Hash) : 해시 함수(Hash Function)의 결과물이며, 저장소(bucket, slot)에서 값(value)과 매칭되어 저장된다.
값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색, 접근이 가능해야 한다.

출처 : https://velog.io/@cyranocoding/Hash-Hashing-Hash-Table해시-해싱-해시테이블-자료구조의-이해-6ijyonph6o

용도

정보의 무결성 확인

바이러스가 포함되어 있는 파일을 다운받거나 자신이 받은 암호화의 결과에 결손이 의심된다면 공개된 해시값과 검사합(Checksum)을 비교하여 검증할 수 있다.
- 체크섬이란 해시 합계라고 하며 단일 파일에 데이터의 암호화 해시 함수라고 말하는 알고리즘을 실행한 결과이다. 파일 버전에서 생성한 체크섬과 파일 소스에서 제공한 체크섬을 비교하면 파일 사본에 오류가 발생하지 않도록 할 수 있다.
- 체크섬을 원본 파일과 사본이 동일한지 비교하는 과정으로 이해했고 비트로 계산하는 과정은 아직 이해가 되지 않았다.
해시 값을 데이터의 지문처럼 활용하는 경우다.
암호 저장

회원이 비밀번호를 디비에 원문 그대로 저장하면 DB가 노출이 된다면 사용자의 정보가 모두 노출되게된다. 이때 해시함수를 이용하여 비밀번호를 해시 함수로 암호화하여 디비에 해시값을 저장하고 비교한다.

서비스가 해킹이 되어 회원들의 DB가 유출이 되더라도 해커는 역상저항성으로 인해 회원들의 진짜 암호를 알아낼 수 없다.
- 역상저항성이란 주어진 임의의 출력값 y에 대해 y = h(x)를 만족하는 입력값 x 을 찾는 것이 계산적으로 불가능하다.
해시테이블에서의 활용

데이터 목록에서 특정 데이터를 조회할 때, 키 값으로 탐색 범위를 줄일 수 있음