[Algorithm] Hash(해시) 란

Hash 란?

해시란 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것이다.

키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 갯수에 따라 동적으로 크기가 증가하는 associate array이다.

키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 한다. 이때 사용하는 함수(알고리즘)를 해시함수라고 한다.

해시 값 자체를 index로 사용하기 때문에 평균 시간복잡도가 O(1)로 매우 빠르다.

 

Hash 함수란?

위에서 설명한 것과 같이 키에 대한 해시값을 만드는 함수(알고리즘)이라고 한다.

계산이 복잡하지않고 키값에 대한 중복이 없고 해시값을 고르게 만들어 내는 함수가 좋은 함수이다.

 

특징

• 입력값이 일부만 변경되어도 전혀 다른 해시값을 출력한다.[눈사태 효과]
• 입력값 상관없이 고정된 길이의 해시값을 출력한다.
• 복호화 불가능하다.[단방향 암호화 기법의 특징]
• 복잡하지 않은 알고리즘으로 구현되기 때문에 상대적으로 CPU, 메모리 같은 시스템 자원을 덜 소모한다.
• 같은 입력값에 대해서는 같은 출력값을 보장한다.

좋은 해시 함수의 조건은 Simple uniform hash 함수를 만드는 것이다.

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

충돌(Collision)

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

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

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

 

충돌 해결을 위한 방법

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

참고

https://runa-nam.tistory.com/84

해시(Hash) 란?

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

[자료구조/알고리즘] 해시(Hash) 란?