해시(Hash) 란?

1. 개념

해시

• 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것
• 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array 이다
• 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 한다.
• 해시값 자체를 index로 사용하기 때문에 평군 시간복잡도가 O(1) 로 매우 빠르다
  → 해시 태이블의 크기에 상관없이 데이터에 빠르게 접근할 수 있다.
  → 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 실행할 수 있다.
  

해싱의 간단한 예시.

해시함수

• 위에 설명한 것과 같이 키에 대한 해시값을 만드는 함수(알고리즘)
• 계산이 복잡하지 않고 키값에 대해 중복없이 해시값을 고르게 만들어 내는 함수가 좋은 함수 (충돌이 일어나지 않을수록 좋다)
• 대표적으로 나눗셈법(Division Method)와 곱셉법(Multiplication Method)이 있다

 

좋은 해시함수의 조건은 Simple uniform hash 함수를 만드는 것으로, 조건은 다음과 같다.

1. 계산된 해쉬값들은 0부터 배열의 크기-1 사이의 범위를 '동일한 확률'로 골고루 나타날 것.
   → 충돌이 일어날 확률이 적어진다.
2. 각각의 해쉬값들은 서로 연관성을 가지지 않고 독립적으로 생성될 것.
   → 해쉬값들이 서로 연관이 있을 경우 연관성이 있으면 해당 해쉬값이 등장하는 패턴이나 순서가 존재 할 수 있고, 이는 반복적인 충돌을 일으 킬 확률이 있기 때문에 독립적으로 생성되도록 한다.

 

2. 충돌 (Collusion)

해시테이블은 '충돌'이 일어날 수 있다는 문제점이 있다.

충돌이란 키에 대한 해시값이 같은 경우, 즉 사용하고자하는 해시 버킷이 이미 사용중인 경우를 말한다.

이를 방지하기위한 방법이 있으나, 충돌을 '완전히' 방지하기는 어렵다는 점이 해시의 한계이다.

 

충돌 해결을 위한 방법들

• Chaining
  • 충돌이 일어날 경우 데이터들을 포인터를 이용해 서로 링크드 리스트(체인)형태로 연결하는 것 
  • 충돌을 허용하되, 최소화하는 방식에 가깝다.
  • key값을 포인터로 이어서 연결
  • 최악의 경우 모든 데이터가 같은 해시값을 가져 O(n)의 복잡도를 가짐
  • JDK 라이브러리에 구현된 HashMap 은 chaining 방식을 사용하며 해당 버킷의 길이에 따라 LinkedList에서 Tree로 변경될수 있다
• Open Addressing
  • 모든 데이터를 테이블에 저장하는 방법
  • 사용하려는 해시 버킷(테이블)이 이미 사용중인 경우 다른 버킷을 사용
  • 포인터를 쓰지 않아 오버헤드를 방지할 수 있고 데이터가 적을 경우 연속된 공간에 인자를 저장하기 때문에 공간 효율이 높다
  • 포인터가 필요없어 구현이 훨씬 용이해졌으며, 포인터 접근에 필요한 시간이 없어졌기 때문에 큰 성능향상이 있다.
  • 하지만 테이블의 크기가 커질수록 장점이 사라진다
  • Linear Probing
    • 충돌이 발생한다면 바로 다음 인덱스에 데이터를 저장하는 방식 다음으로 이동한 이후에도 충돌이 발생했다면 또 다시 바로 다음인덱스에 저장

• •  Quadratic Probing
    • 충돌시 i^2 만큼씩 이동

      

  • Double Hashing
    • Quadratic probing의 secondary clustering를 해결하기 위해서 사용하는 방법이다.
    • 원리는 간단한데, 해쉬 함수를 해쉬 함수 2개로 구성하는 것이다.

      

 

 

참고자료

https://hsp1116.tistory.com/35

https://power-overwhelming.tistory.com/42