Hash Algorithm (1) 기본 개념

https://www.youtube.com/watch?v=Vi0hauJemxA 

 

본 영상을 참고 했습니다.

 

-------------------------------------------------------------------

 

0. 비잔틴 장군의 문제 

 

넷플릭스의 익스플레인 - 세계를 해설하다 시즌1을 보면 "암호화폐"에 대한 얘기가 나온다. 그 영상에서는 암호화폐의 순기능에 대해 "비잔틴 제국의 장군들이 한 성을 포위"한 상황에 빗대어 설명한다. 만약, A/B/C 세 명의 장군이 협동하여 성을 포위했다고 가정하자. 이때, A가 갑자기 배신을 한다면? B와 C는 난감할 것이다. 그런데, 암호화폐의 장부 기능은 이러한 상황을 방지한다. 어떻게?

 

장부의 "전투 계획"이 모든 장군들에게 공유 되었기 때문이다. 그리고, 이 계획이 실시간 업데이트 되는데 A / B / C 모든 장수들이 Attack이라는 계획을 공유하고 있을때, A가 갑자기 배신을 해서 Betray(맞나..?)라는 값을 가지게 되면, B와 C는 바로 눈치를 챌 것이다. 이놈 배신을 했구만

 

다시 이 비유를 암호화폐의 사례로 끌고 들어와보자. 암호화폐가 가지는 순기능이란 다음과 같다. 모든 거래 장부가 모든 사용자에게 공유 된다. 그래서, 누군가가 조작을 가하게 되면 조작을 가한 누군가는 장부 내의 모든 사람들과 "다른 값"을 가지게 되기 때문에 "조작이 불가능"하다.

 

근데 말이다. 거래가 하루에 한 두건 일어나는 것도 아닐테고 어떻게, 그 수많은 장부 기록들 중에서 "조작된 한 건"을 발견할 수 있을까? 정답은 해시 알고리즘에 있다.

 

1. 해시 알고리즘 기본 프로세스

 

해시 알고리즘의 기본적인 내부 프로세스는 다음과 같다.

 

1. Hash함수에 Key를 넣는다.
2. HashCode를 리턴한다.
3. HashCode를 Index로 사용하여 배열에 접근한다.
4. 값을 찾는다.

 

여기서 특이점은, Hash함수에 들어가는 Key값에서 .하나만 틀려도 전혀 다른 해시코드를 생성한다는 것이다.

 

2. 해시 배열이 빠른 이유

 

해시 함수로 만든 해시 코드는 "정수" 값을 가진다. 그리고, 그 정수값을 배열 크기로 나누어 남은 "나머지"를 활용하여 각 방에 index를 할당한다. 즉, 해시코드 자체가 배열의 index로 활용되기 때문에 접근 속도가 매우 빠른 것이라 할 수 있다. 

 

3. 충돌 문제

 

Hash Table은 생성 전에 "배열"을 미리 만들어 둔다고 한다. 여기서 문제는 미리 만들어 둔 배열의 각 방에 어떻게 "값"을 할당할 것인지이다. 

 

그런데 말이다. 여기서 두 가지 문제가 생길 수 있다.

 

1. 다른 키 값인데 -> 같은 해시 코드가 나오는 경우

왜냐하면, 키는 문자열이라서 무한개가 나올 수 있는데 해시는 정수라서 정수 범위 만큼만 코드가 생성되기 때문이다. 

 

2. 다른 해시 코드 값인데 -> 같은 인덱스를 가지는 경우

위 두 가지 경우를 모두 충돌(Collision)이라고 한다. 

 

기본적으로 해시 알고리즘에서 시간 복잡도는 O(1)이라고 한다. 왜냐하면, HashCode가 Index로 작용하여 바로 값을 찾기 때문이다. 하지만, 충돌이 생길 경우 O(n)까지 시간 복잡도가 증가할 수도 있다고 한다.