Hash.md

해시 Hash

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

임의의 값이 해시함수를 통과하여 얻어진 값을 해시 값, 해시 코드라고 한다.

임의의 값의 해시값을 임의의 값을 저장한 배열의 인덱스로 사용하는 것을 해시 테이블이라고 한다.

해시 테이블을 사용하면 임의의 값을 배열에서 찾을 때, 찾고자하는 값을 해시함수에 입력하여 해시값을 얻는다.
이 해시값을 인덱스로 사용하여 배열에 접근하면 검색에 드는 시간복잡도가 O(1)가 되므로 아주 빠른 검색을 할 수 있다.
선형 탐색으로 찾았다면 O(n)이 걸렸을 것

해시 함수

• 암호학적 해시함수

  해시 값으로부터 원래의 입력값과의 관계를 찾기 어려운 성질을 가지는 경우

  암호학적 해시함수는 제 1 역상 저항성, 제 2 역상 저항성, 충돌 저항성을 갖추어야 한다.

  • 제 1 역상 저항성은 어떤 해시값을 생성하는 입력값을 찾는 것이 어려워야 한다는 것
  • 제 2 역상 저항성은 어떤 입력값에 대한 해시값을 변경하지 않으면서 입력값을 변경하는 것이 어려워야 한다는 것
  • 충돌 저항성은 같은 해시값을 생성하는 서로 다른 입력값을 찾는 것이 어려워야 한다는 것이다.

  ex. MD5, SHA계열 해시함수

• 비암호학적 해시함수

  ex. CRC32 등

해시 충돌

서로 다른 데이터를 해시함수에 입력했을 때

같은 해시값이 얻어지는 경우가 발생할 수 있다.

이를 해시충돌 이라고 한다.

해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 한,

비둘기집 원리 에 의해 해시 충돌은 항상 존재한다.

해시 충돌 해결 방법

• 체이닝

  체이닝은 같은 해시값을 가진 입력이 여러개일 경우

  해시값의 인덱스에 딸린 값을 연결리스트로 만들어서 여러개의 입력값을 저장하는 것이다.

  이렇게 되면 입력값을 찾을 때는 해당 해시값에 대응되는 연결리스트를 선형 탐색하여 찾아야 한다.

• open addressing

  이 방법은 충돌이 발생하면 충돌이 발생한 해당 해시값이 아니라 다른 위치에 값을 저장하는 방식이다.

• 이중 해싱

  이중 해시는 다음과 같은 형태의 해시 함수를 사용한다. 충돌이 없을 때는 h1으로 위치를 탐색하고, 충돌이 있으면 h2 mod m 만큼 이동하면서 탐색한다.

  (근데 이 식을 이해 못하겟음)