Hash (해시)

데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것

해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

Hash Function (해시 함수)

정의

• key를 고정된 길이의 Hash로 변경해주는 역할을 한다.
• 이 과정을 hashing이라고 한다.
• Input : key, Output : Hash

Hash Table (해시 테이블)

정의

• 해시 함수를 사용하여 key를 해시값으로 매핑하고, 이 해시값을 색인(인덱스) 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조 이다.

• 단순하게, key & value로 이루어진 자료구조 라고 생각하면 된다.

구성

• key
  - 고유한 값, hash function 의 Input이 된다.
  - key 값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼의 정보를 저장해야 하는 공간도 따로 마련해야 하기 때문에(key의 길이가 제각각 일 수 있다.), 고정된 길이의 해시로 변경한다.
  

• hash function
  - key를 고정된 길이의 hash 로 변경해 주는 역할을 한다.
  - 서로 다른 key가 hashing 후 같은 hash 값이 나오는 경우가 있다. 이를 해시 충돌이라고 부른다. 해시 충돌 발생확률이 적을 수록 좋다.
  - 해시 충돌이 균등하게 발생하도록 하는것도 중요하다. 모든 키가 같은 해시값이 나오게 되면, 데이터 저장시 비효율성도 커지고 보안지 취약해져서 좋지 안다.

• value
  - 저장소(버킷, 슬롯)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장되어진다.

• has table
  - 해시 함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소 또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조 이다.
  - 데이터가 저장되는 곳을 버킷, 슬롯 이라고 한다.

장점

• 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있다.
  (key-value 가 1:1 로 매핑되어 있기 때문에)

단점

• 해시 충돌이 발생
• 순서 / 관계 가 있는 배열에는 어울리지 않는다.
• 공간 효율성이 떨어진다.
  (데이터가 저장되기 전에 저장공간을 미리 만들어놔야 한다.)
• hash function의 의존도가 높다.
  (해시 함수가 복잡하다면, hash를 만들어 내는데 오래 걸릴 것 이다.)

해시 충돌 해결 방법

체이닝

• 연결 리스트로 노드를 계속 추가해 나가는 방식

• 제한 없이 계속 연결 가능, but 메모리 문제

Open Addressing

• 해시 함수로 얻은 주소가 아닌, 다른 주소에 데이터를 저장할 수 있도록 허용하는 방식

• 해당 키 값에 저장되어 있으면 다음 주소에 저장

선형 탐사

• 정해진 고정 폭으로 옮겨 해시값의 중복을 피함

제곱 탐사

• 정해진 고정 폭을 제곱수로 옮겨 해시값의 중복을 피함