[자료구조] 3. Hash Table

해시 테이블

---

• key와 value로 데이터를 저장하는 자료구조
• 하나의 해시 함수를 이용해 저장한다
  • ex) h(x) = xmod13 → h(7) = 7, h(13) = 0
  1. 해당 원소의 해시값을 해시 함수를 이용해 계산한다. (= 해싱)
  2. 이 해시값을 주소로 하는 위치에 원소를 저장한다.
  3. 저장 후에 검색을 할 때도 원소의 해시값을 계산해 바로 해당 위치로 이동한다.임의의 원소를 해시 테이블에 저장하려면           → 이렇게 해시 테이블은 원소를 저장할 위치를 상수 시간에 계산할 수 있다.
• 실제 값이 저장되는 장소를 버킷 또는 슬롯이라한다.

 

---

해시 함수란?

• 임이의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 좋은 해시함수
  • 계산이 간단해야 한다.
  • 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다. → 해시충돌 발생 할 수 있음.

---

대표적인 해시함수

1. Division Method - 나머지를 이용하는 방식 (주소 = 입력값 % 테이블의 크기)
   1. 테이블 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 한다.
2. Digit Folding - 각 key의 문자열을 ASCII 코드로 바꾸고 합한 값을 주소로 사용한다.

 

---

해시 충돌이란?

• 해시 함수가 서로 다른 두 개의 입력값에 대해 같은 출력값을 내는 상황
• 해결 방법
  1. 체이닝
     • 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트로 만들어서 관리한다.
  2. 개방 주소 방법
     • 체이닝과 달리 어떻게든 주어진 테이블 공간 안에서 해결한다.
       
       

---

 

해시 충돌 해결 방법

1. 체이닝
   • 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트로 만들어 관리한다.
   • 해당 연결리스트의 원소들을 차례로 탐색한다.
2. 개방 주소 방법
   • 체이닝과 달리 어떻게든 주어진 테이블 공간 안에서 해결한다.
   • 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장되지않음

개방 주소 방법 1) 선형 조사

• 해싱 값에 이미 원소가 존재하면 빈 위치가 있을 때까지 다음 해싱 값으로 넘어간다.

개방 주소 방법 2) 이차원 조사

• 바로 뒷자리를 보는 대신 보폭을 이차 함수로 넓혀가며 본다.
• 예를 들어, i번째 해시 함수를 h(x)에서 i^2만큼 떨어진 자리로 삼는다.
• 즉, h(x), h(x)+1, h(x)+4, h(x)+9 등
• 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있다.

개방 주소 방법 3) 더블 해싱

• 두 개의 함수를 사용한다.
• 하나의 함수는 최초의 해시값을 얻을 때, 다른 하나의 함수는 해시 충돌이 일어났을 떄 이동할 폭을 얻을 때 사용한다.
• 두 원소의 첫 번째 해시값더라도 두 번째 해시값까지 같을 확률은 매우 적어 서로 다른 보폭으로 점프를 하게 된다.

 

---

해시 함수의 특징

• 같은 입력값에 대해서 같은 출력값이 보장된다.
• 서로 다른 입력값으로부터 동일한 출력값이 나올 가능성이 희박하므로 입력값에 대한 무결성이 보장된다.
• 일방향성을 갖는다. (해시값을 이용해 원소값을 얻어내는 것이 어렵다)
• 눈사태효과 (입력값이 조금만 바껴도 출력값이 완전 달라짐)

 

---

대표적 해시 알고리즘 Secure Hash Algorithm(SHA)

• 주로 사용되는 것은 SHA-2 함수군으로, 다이제스트의 길이에 따라 SHA-256, SHA-512로 나뉜다.
• SHA-0, SHA-1까지는 해시 충돌성이 존재하지만 SHA-256, SHA-512는 해시 충돌성이 사실상 0에 수렴한다.
• 256의 의미 : 해싱을 하면 2^256개의 해시값 중 하나가 나타난다.

 

---

해시의 응용

• 무결성 검사 - 파일 변조 검사
• 클라우드 스토리지에서 동일한 파일 식별 및 수정된 파일 검출
• 데이터베이스에 비밀번호를 저장할 때
• 블록체인
• Git해시 테이블