해시 테이블 (Hash Table)

해시 테이블 (Hash Table)

• hash 함수를 통해 key를 해시 코드로 변환하고, 이 해시코드로 인덱스를 계산해 value에 접근한다.
• hash function : 해시 코드로 변환하는 함수 

  

Hash Function

1. 나눗셈 법

• h(k) = k mod m
• 입력받은 key의 각 문자를 유니코드로 변환 후 HashMap의 size로 나눈 나머지 값으로 사용한다.
• m은 HashMap의 크기이며 소수를 사용한다. (2의 제곱수와 거리가 먼 소수)

2. 곱셈 법

• h(k) = (kA mod 1) * m
• k는 숫자로 된 키, 0 < A < 1
• m은 중요하지 않으며 보통 2의 제곱 수로 정한다.
• 나눗셈 법보다는 느리고 2진수 연산에 최적화된 컴퓨터 구조를 고려한 해시함수이다.

3. Universal Hashing

• 다수의 해시 함수를 만들고 이 해시함수의 집합에서 무작위로 해시함수를 선택해 해시값을 만드는 기법
• 무작위로 뽑은 해시함수가 주어졌을 때 임의의 키 값을 임의의 해시값에 매핑할 확률을 1/m으로 만드는 것이 목적이다.

4. MD5 (Message - Digest Algorithm)

• 임의의 길이의 값을 입력받아 128 비트의 고정 길이 해시값을 출력하는 알고리즘
• 같은 입력값이면 항상 같은 출력값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮다.
• 단방향 암호화이기 때문에 해시값을 복호화는 할 수 없다.

5. SHA (Secure Hash Algorithm)

• 미국 국립표준기술연구소에서 표준으로 채택한 암호학적 해시 함수
• 해시 길이에 따라 SHA-256, SHA-384, SHA-512 비트를 선택해 사용할 수 있으며, 해시 길이가 길수록 안전하다

 

좋은 해시 함수란 ?

• 계산 속도가 빠른 함수
• 충돌 발생 빈도가 낮은 함수

 

Chaining

• 데이터가 많으면 충돌이 발생하게 되는데, 충돌을 해결하는 방법이다.

1. Open Address (개방 주소법)

• 해시 충돌이 발생하면 다른 버킷을 사용하는 방식이다.
• Linear Probing
  • 충돌이 발생했을 때, 순차적으로 탐색해 비어있는 버킷을 찾는다.
• Quadratic Probing
  • 충돌이 발생하면 해시 저장 순서 폭을 제곱으로 저장한다. 처음 충돌이 발생한 경우 1만큼 이동하고, 그 다음 충돌이 발생하면 2^2, 3^3 .. 씩 옮기는 방식이다.
• Double hashing Probing
  • 하나의 해시 함수에서 충돌이 발생하면 2차 해시 함수를 이용해 새로운 주소를 할당한다.
  • 많은 연산량이 요구된다.
• 해시 버킷이 많이 채워져 있을수록 충돌이 많이 발생하기 때문에 속도가 느리다.

2. Separate Chaining (분리 연결 법)

• 한 버킷 당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는 방법
• 해시 충돌이 자주 발생하지 않도록 보조 해시 함수를 활용해 충돌 발생 빈도를 줄일 수 있다.
• Open Addressing보다 빠르다.
• Java의 HashMap은 Seperate Chaining 방식을 사용한다.
• 연결 리스트 사용
  • 충돌이 발생하면 그 인덱스가 가리키는 연결리스트에 노드를 추가하여 값을 추가한다.
• Tree 사용

시간복잡도

• 일반적으로 충돌을 최소화하도록 잘 구현된 경우 : O(1)
• 충돌이 자주 발생하는 경우(최악의 경우) : O(N)
• 균형 이진 탐색 트리를 사용한 경우 : O(logN)
  • 이 방법은 배열의 크기를 미리 할당해 놓지 않아도 되기 때문에 잠재적으로 적은 공간을 사용하고, 키의 집합을 특정 순서로 차례대로 접근할 수 있다.