해시

해시(Hash)

개념 및 특징

• 입력 데이터를 고정된 길이의 데이터로 변환한 값 => 데이터의 key 값을 변환 
• 키(Key)와 데이터(Value)의 매핑 구조
• 해시 함수(Hash Function)를 통해 키의 데이터를 배열에 저장할 수 있는 주소(인덱스)를 계산
• 데이터의 탐색 속도가 빨라짐

해시 함수(Hash Function)란?

• 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 같은 입력값에 대해서 같은 출력값이 생성된다. 
• 입력값의 범위보다 출력값의 범위가 좁은 경우가 많기 때문에 입력값이 다르더라도 동일한 값이 출력될 가능성이 있다. => 충돌(Collision)
• 충돌이 발생하는 경우, 배열이 생성되며 선형검색이 이루어진다.

해시 테이블(Hash table)이란?

• 해시함수를 사용해서 변환한 값을 index로 삼아 (key, Value)로 데이터를 저장하는 자료구조 
• 내부적으로 배열(Bucket)을 사용해 데이터를 저장하기 때문에 검색속도가 빠르다.

이미지 출처 https://mangkyu.tistory.com/102

• 시간 복잡도
  • key-value가 매핑되어 있기 때문에 검색, 삽입, 삭제 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 갖는다
  • 충돌이 일어날 경우 인덱스로 값을 탐색할 후 연결 리스트를 순차 탐색 후 삽입 또는 삭제해야 해서 결국 O(N)의 시간 복잡도를 갖는다. 
• 장단점
  • 관계를 모형화할 수 있다.
  • 해시값을 알아도 key를 예측하기 어렵다.
  • 충돌이 없으면 빠른 탐색이 가능하다.
  • 데이터를 저장하기 전에 미리 공간이 확보되어야 하므로 공간 효율성이 떨어진다.

충돌 발생시 해결방법 

1. 체이닝(Chaining)
   • 연결리스트로 노드를 계속 추가해나간다. 
   • 하나의 bucket에 여러개의 자료들이 연결될수록 시간 복잡도가 증가한다.
   • 연결리스트를 위해 추가적인 메모리가 필요하다. 

체이닝

2. 개방 주소법(Open Addressing)

• 충돌이 발생하면 주변에 비어있는 hash를 찾아 저장하는 방법
  1. 선형 탐사(Linear Probing)
     • 충돌이 발생한 hash를 기준으로 고정폭 만큼 건너뛰면서 빈 공간 찾기
     • 데이터 밀집 현상인 clustering 발생 가능
  2. 제곱 탐사(Quadratic Probing)
     • n^2의 폭만큼 건너뛰면서 빈 공간 찾기
     • 이 또한 clustering 발생 가능
  3. 이중 해싱(Double Hashing)
     • 충돌이 발생하면 또 다른 hash function 사용
     • 처음 hash function은 최초의 hash를 얻을 때 사용, 나머지 하나는 탐사의 폭을 얻기 위해 사용
     • 여러 공간에 골고루 저장될 확률이 높아져 1, 2 방법의 clustering 문제 해결 가능 
• 별도의 메모리 공간이 필요하지 않아 hash table 내에서 충돌에 대한 처리가 가능하다.
• 데이터가 늘어나는 만큼 bucket에 공간을 미리 확보해야한다.
• 충돌이 많이 발생할수록 clustering으로 인한 시간 복잡도가 증가한다. 

개방 주소법

 

참고

https://think0wise.tistory.com/66

자료구조 - Hash Table (해시 테이블)

https://ablue-1.tistory.com/68

[자료구조] 해시(Hash)란 무엇인가

https://kang-james.tistory.com/136

[자료구조] 해시(HASH) 알아보기