[알고리즘 지식 공부] 해시, 해시 함수란?

서론

안녕하세요. 개발자 제라스입니다~ 👋🏻🤖👋🏻

요즘 부스트캠프가 끝나고서 알고리즘 공부에 푹 빠져있는데요.

작년 12월에 열린 MADC에서 럭키드로우 상품으로 받은 책을 통해 Python으로 코테 공부를 하고 있습니다ㅎㅎ

하나하나 풀어나가는게 예전에 Java로 코테 풀 때 그 느낌이라 너무 재밌더라구요.

 

그러다 중간중간 알고리즘 관련 지식들이 등장하는데 정리를 해보고자 한번 정리 컨텐츠를 시작해보려고 합니다.

오늘부터 차근차근 정리할 게 생길 때마다 정리하려고 하는데 첫 포스팅은 '해시(Hash)'입니다.

 

그럼 한번 또 시작해봅시다~

해시가 뭔데요?

솔직히 IT쪽 뿐만 아니라 여러 분야에서 해시 얘기는 정말 많이 들어봤죠?

그만 듣고 싶을 정도잖아요. 맞잖아? 맞잖아? 맞잖아? 맞잖아? 맞잖아? 맞잖아? 맞잖아?

이게 뭐냐...?

간단히 얘기하면 어떤 두 데이터가 짝지어져 있다고 합시다.

예를 들면 "a": "apple", "c": "melon" 이렇게요

이때 우리는 "a"라는 문자(key)를 해쉬 함수에 넣어서 다른 인덱스로 변환을 해요.

그러고나서 이 값으로 value값인 "apple"을 찾는 거죠.

 

요즘 많이 듣는 말인데 MZ 특 한줄 요약 좋아함.

즉, 해쉬는 간단히 key와 value가 짝지어져 있을 때 key를 index값(다른 말로는 해시값)으로 변환시켜서 value를 찾을 수 있도록 합니다.

 

이런 해시는 가장 큰 특징으로 단방향으로 작동한다는 점이 있습니다.

즉, 해시 함수에 키를 넣어서 새로 해시값을 얻었다고 합시다.

근데 반대로 이 해시값을 가지고서는 함수에 넣은 키를 찾을 수는 없습니다.

그렇게 구조가 짜여진게 해시 함수입니다.

-> 이런 특징이 거꾸로 유추해내기 어렵다는 점에서 네트워크 보안 쪽에서 해시를 많이 쓰게 됩니다.

 

다른 특징으로는 인덱스처럼 임의 접근이 가능합니다.

우리 index값으로 해당 index에 들은 값을 가져오죠? 이런 걸 임의 접근이라고 해요.

즉, index 5에 있는 값을 찾기 위해 index 0 부터 순차 접근하는게 아니라 바로 index 5로 달려가서 값을 가져온다는 거죠.

이렇게 가져오는 방식을 해시도 적용되는 이유는 키 값을 index값(해시값)으로 변환해서 접근하기 때문입니다.

비슷하다잇~~

 

또 다른 특징으로는 키를 해시값으로 변환하기 위해서는 적절한 변환 과정을 거쳐야 한다는 점입니다.

이 변환 과정은 뒤에서 살펴 봅시당~!

 

이러한 것들 때문에 해시는 주로 비밀번호 관리, DB 인덱싱, 블록체인에서 많이 쓰인다고 하네요!

 

해시 함수는 그럼 어떻게 짜는 것이오??

 

일단 해시 함수를 통해서 어떤 값을 변환해서 나오는 값은 해시 테이블의 크기를 넘어서면 안됩니다.

출처: 위키백과

위 그림을 보시면 해시함수를 거쳐서 나온 값은 해시 테이블의 하나의 데이터 혹은 다른 말로는 버켓(bucket)에 대응해야 합니다.

그러니 함수를 거친 값이 해시 테이블의 크기보다 큰 값이 되면 해시 테이블에서 그 값을 index로 하면 범위가 넘어서버리는 것이죠.

 

또한, 해시 함수는 충돌이 날 수 있습니다.

충돌? 그게 뭔 소리야??

즉, 서로 다른 값이 해시 함수에 들어갔는데 결과값이 동일하면 둘 다 해시 테이블에서 동일한 데이터에 접근하게 되는 것이죠.

위 그림에서 John Smith와 Sandra Dee의 해싱 결과가 02로 같은 것처럼 말이에요.

 

미리 말씀드리지만 이런 충돌을 처리하는 방법도 있습니다! :-)

 

그럼 해시 함수의 종류를 한번 볼게요.

 

나눗셈법

h(x) = x mod m

어떤 값이 들어오면 m으로 나눈 나머지를 결과값으로 하는 거에요.

이러면 항상 0 ~ m-1 사이의 값들만 결과값으로 나오겠죠?

 

이때 우리는 소수를 m값으로 보통 많이 써요.

왜????

 

 

한번 생각해봅시다...!!

h(x)로 들어오는 값이 2,4,6,8,10,...,30이라고 할게요.

이때 소수값 5와 8을 볼게요.

당연히 5보다 8이 크니 나머지 종류가 다양하게 나올 것 같습니다.

하지만 실제로 보면

# 5로 나눌 때
2,4,1,3,0,2,4,1,3,0,2,4,1,3,0

# 8로 나눌 때
2,4,6,0,2,4,6,0,2,4,6,0,2,4,6

이처럼 큰 수임에도 5로 나눌때 5가지(2,4,1,3,0)보다 4가지(2,4,6,0)로 종류가 적죠?

이 이유는 2의 배수 모음(예시에선 2,4,6,8,...30)은 8의 약수이기에 더욱 잘 겹친다는 겁니다.

 

이러한 이유에서 보통 m값으로 소수값을 씁니다.

 

곱셈법

우리가 큰 해시 테이블을 만드려고 해요.

근데 이때 그만한 크기의 소수 m을 구하기 힘들잖아요.

 

그래서 우린 나눗셈법 대신 곱셈법을 쓸 수도 있습니다.

# m은 원하는 해시 테이블 크기, A는 무한소수의 황금비(1.618033988...)
h(x) = (((x*A)mod 1)*m)

여기서 보면 똑똑한 분들께서 만들어두신 황금비를 활용합니다.

또한 mod 1을 하면 0이 아니라 소숫점이 나오는데 그걸 m과 곱하는 것이죠.

이건 솔직히 저도 외우는 수 밖에 없는 것 같습니다.

 

문자열 해싱

마지막으로 위 두 경우와 달리 문자열에 대한 해싱인 문자열 해싱이 있습니다.

h(x) = (s[0]+s[1]*p+s[2]*p^2+...+s[n-1]*p^(n-1)) mod m

이런 식이 있는데 a~z의 문자를 1~26에 매칭해서 s[~]값을 뽑아내고 p는 보통 홀수인 메르센 소수로 31, m은 원하는 해시 테이블 크기

이렇게 잡습니다.

생각보다 복잡하죠? 하지만 우린 뭐를 할 수 있죠?

암기...ㅎㅎㅎ

저는 암기하겠습니다.

 

여기서 더 나아가서 만약 문자열 길이가 너무 길어지면, mod m을 마지막에만 해주니까 더하는 과정에서 값이 엄청 커질 수 있습니다.

그래서 다음처럼 문자로 값을 곱셈할 때마다 m으로 나눠주는 방식으로 개선시킬 수도 있습니다.

# 정보) mod m이 %m이랑 같습니다.
h(x) = (s[0]%m+s[1]*p%m+s[2]*p^2%m+...+s[n-1]*p^(n-1)%m) mod m

해싱 결과 충돌 처리

우리 아까 해싱을 하면 결과가 동일해서 충돌이 될 수도 있다고 했죠?

그걸 방지하는 방법도 알아봅시다.

 

체이닝

체이닝은 만약 해싱한 결과값에 어떤 데이터가 있으면 링크드리스트로 충돌한 데이터를 연결하는 방식입니다.

이 결과 한 데이터에 대해 값을 여러개 둘 수 있지만 이게 길어지면 뒤쪽에 있는 데이터에 접근하는데 시간이 들죠.

또한, 해시 테이블 자체의 공간을 잘 활용하지 못한다는 낭비 단점이 존재합니다.

 

개방 주소법

얘는 위 체이닝과 달리 링크드리스트를 쓰지 않고 해당 값이 충돌 시 다른 버킷을 찾아 저장하는 방식입니다.

이를 통해 상대적으로 메모리를 조금 더 효율적으로 쓸 수 있는 것이죠.

 

그럼 어떤 버킷에 넣을지도 알아봐야겠죠?

왜냐하면 막 대충 아무 빈 버킷에 넣는 것도 비용 문제가 발생하니까요. 나중에 다시 찾을 수도 없는 노릇이구요...

 

먼저 선형탐사 방식입니다.

이 방식은 만약 충돌이 발생하면 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동하면서 빈 버킷을 찾는 방식입니다.

# i는 간격인데 보통 1로 합니다.
# m은 테이블의 크기이고 k는 해쉬함수를 거쳐 나온 결과값입니다.
h(k,i) = (h(k)+i)mod m

예를 들어, 탐사하는 간격을 1로 한다고 해둡시다.

만약 어떤 값이 해시함수를 거쳐서 값을 냈는데 해당 값이 테이블에 없으면 그대로 저장하겠죠?

하지만 다른 값이 있어서 충돌이 난다면 바로 그 다음 1 증가시킨 값을 봅니다. 그 값이 테이블에 없으면 그곳에 저장을 하고,

만약 그 값도 테이블에 존재한다면 또 1을 증가시켜서 봅니다.

 

이런 식으로 하나씩 한개씩 탐색하면서 빈 버킷을 찾는 방식이 선형탐사 방식입니다.

다른 방식으로는 이중 해싱 방식이 있습니다.

이 방식의 식부터 보시죠.

h(k,i) = (h1(k)+i*h2(k))mod m

만약 뽑아낸 값이 충돌이 나버리면 이런 식으로 하나의 해시함수가 아닌 이중으로 해싱을 거쳐서 값을 추출해내는 방식입니다.

또 충돌이 나면 한번 더 하는 것이죠.

이때 클러스터를 좀 더 줄이기 위해 m을 제곱수 혹은 소수로 합니다.

이렇게 하면 주어지는 키마다 점프하는 위치를 해시 함수로 다르게 하기에 클러스터 형성을 최대로 피할 수 있습니다.

마무리

이렇게 오늘은 해시가 무엇인지 그리고 충돌이 발생 시 해결법은 어떻게 되는지 알아봤습니다.

Python에서는 이 해시와 거의 동일하게 작동하는 Dictionary라는 콜렉션 자료형이 있습니다. 다음과 같이 생겼죠.

dictionary_example = {"hi": 2, "hello": 15}

물론 평소에 해시 함수를 적용하고 직접 구현할 일은 적겠지만 이 개념과 어떤 방식으로 함수가 만들어지는지 잘 알아두는 것도 중요할 것 같습니다. 이 방식을 활용해서 알고리즘을 짜야하는 일도 있을 테니까요😚😚

 

그럼 긴 글 읽어주셔서 감사드리며 다음에도 좋은 포스팅으로 돌아오겠습니다!🤖🤖 

참고

- 코딩 테스트 합격자 되기 - 파이썬 편

- 위키 백과 - 해시함수

---

아직 꼬꼬마 개발자입니다.

더 나은 설명이나 코드가 있다면 언제든 환영입니다.

적극적인 조언과 피드백 부탁드립니다!

 

그럼 오늘도 개발 가득한 하루되세요!

- Xerath -

🤖🤖🤖🤖🤖🤖🤖