해시함수란?

• 해당원소의 해시값을 해시함수를 이용하여 계산

• 해시값을 주소로 하는 위치에 원소를 저장

• 저장후에 검색을 할때도 원소의 해시값을 계산해 바로 해당 위치로 이동

• 해시 테이블은 원소를 저장할 위치를 상수시간에 계산할 수 있다.

좋은 해시함수의 조건

해시 과정이 복잡해서는 안된다

해시값이 골고루 저장되어야 한다

해시 충돌 해결법

체이닝

• 같은 주소로 해싱되는 원소를 모두 하나의 연결리스트에 매달아서 관리

• 원소를 검색할 때 해당 연결리스트의 원소들을 차례로 지나가면서 탐색

개방 주소 방법

• 체이닝과 달리 어떻게든 주어진 테이블 공간에서 해결
• 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없다
• 선형조사, 이차원조사, 더블 해싱 방법들이 있음

해시 함수의 특징

• 같은 입력값에 대해서 같은 출력값이 보장된다

• 서로 다른 입력값으로부터 동일한 출력값이 나올 가능성이 희박하므로
  입력값에 대한 무결성이 보장된다

• 일방향성을 갖는다

SHA

256의 의미: 해싱을 하면 2의 256승 중 한개가 반환된다

해시의 응용

1. 무결성 검사

2. 클라우드 스토리지에서 동일한 파일 식별 및 수정된 파일 검출

3. 데이터베이스에 비밀번호를 저장할때

4. 블록체인 및 git