해시(Hash) 함수

의의 길이를 갖는 어떤 데이터를 고정된 길이의 데이터로 매핑시키는 함수
해시 테이블 자료구조에서 사용됨
빠른 데이터 검색을 위한 것으로 많이 쓰임
key를 해시함수에 넣어 Hash를 구하고 이것은 저장위치로서 데이터를 꺼내올 수 있음
➡️ 이때 서로다른 key가 가지고 있는 해시값이 같을 수가 있다. 이것을 해시충돌 이라고 한다.

해시: 색인 또는 인덱스
hash function: key->hash로 만들어 주는 함수
해시테이블: hash를 주소로 삼아 데이터를 저장하는 자료구조

해시 충돌(Hash Collision)

어떤 해시 함수가 서로 다른 두 입력에 대해 동일한 출력 값을 나타내는 경우
보통 해시 함수는 다수의 데이터가 있을 때
이들을 구별하고 특정 데이터의 검색을 빠르게 하기 위해 사용됨
해시 충돌이 많이 일어나는 해시 함수일수록 그 질이 낮다고 평가됨
(해시 충돌이 잦을 경우 서로 다른 데이터를 구분하고 검색하는 비용이 증가하기 때문)

체이닝은 저장소에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법
- 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.
- 해시테이블이 채워질수록, 조회시 성능저하가 덜 발생한다.

해시충돌이 일어나면 다른 저장소에 데이터를 삽입하는 방식
- 선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입
- 제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
- 이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함!
- …

해시 암호는 기본적으로 단방향 암호이기때문에 복호화되지 않는다.
사용자의 비밀번호를 해시 암호화를 이용해 인증하는 서비스가 있을 때에는 해시 값을 비교한다.

하지만 이 방법을 사용했을 때에도 해커들에게 정보를 빼앗길 가능성이 있다.
실제로 해커들이 DB를 크랙하고 관리자 계정의 해시를 깬다던가하는 사례가 많이 존재한다.

(참고)

공부한 내용을 여러글과 책 읽은 내용을 바탕으로 정리하고 있습니다.
좋은 글로 저의 공부에 도움을 주시는 분들께 감사드립니다.