해시

해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조이다.

• 키(Key)를 활용해 데이터 탐색을 빠르게 한다.
• 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 필요하지 않다.

해시의 특성을 활용하는 분야

• 비밀번호 관리:
  • 사용자의 비밀번호를 그대로 노출해 저장하는 것은 위험하므로 해시 함수를 활용해 해싱한 비밀번호를 저장한다.
  • 비밀번호가 맞는지 확인할 때도 마찬가지이다.
    사용자가 입력한 비밀번호를 해싱해 확인한다.
• 데이터베이스 인덱싱:
  • 데이터베이스에 저장된 데이터를 효율적으로 검색할 때 해시를 활용한다.
• 블록체인:
  • 블록체인에서 해시 함수는 핵심 역할을 한다.
    각 블록은 이전 블록의 해시값을 포함하고 있으며, 이를 통해 데이터 무결성을 확인할 수 있다.

---

해시 함수

• 파이썬에는 딕셔너리라는 자료형을 제공하는데 이 자료형은 해시와 거의 동일하게 동작하므로 해시를 쉽게 사용할 수 있다.

자주 사용하는 해시 함수 알아보기

나눗셈법

• 나눗셈법(Division Method)은 키를 소수로 나눈 나머지를 활용한다.
• e.g., 7 % 2 = 1
• $h(x)=x \text{ mod } k$
  • $x$는 키, $k$는 소수이다.

---

곱셈법

• 곱셈법(Multiplication Method)은 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 않는다.
• $h(x) = (((x*A) \text{ mod 1}) * m)$
• $m$은 최대 버킷의 개수, $A$는 황금비(Golden Ratio Number)이다.
  • 황금비는 무한소수로 대략 1.6180339887...이다.

---

문자열 해싱

• 문자열 해싱은 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱한다.
• $hash(s)=(s[0] + s[1] * p + s[2] * p^2 + \cdots + s[n-1] * p^{n-1}) \text{ mod } m$