본문 바로가기
[Public] 컴퓨터공학/자료구조

[자료구조] 해시 함수 (Hash) #1

by 차출발 2010. 6. 14.
반응형
해시 함수






한 동안 글을 안올리고 방황하는 시기가 있었다.

다시 마음을 가다 듬고 올릴려고 한다.




이번에 소개할 내용은 해시 함수이다.

보통 자료구조 시간에 많이 들어봤을 것이다.

해시함수 이게 무엇일가 ?



해시의 어원부터 알아보자

해시를 사전에서 찾아보면 3가지가 나온다.




1. 해시시 ( 대마의 잎으로 만든 마약 )

2. 그 일을 망쳐 놓는다

3. 잘게 자른 고기를 양파나 감자와 같은 재료와 함께 튀겨 한덩어리로 만든 요리




여기서 보면 "마약" 이건 아닐테고

"그 일을 망쳐놓는다."

이것 역시 알고리즘과 뭔 상관 ?

마지막 잘게 자른 고기를 하나로 합친다.

이게 좀 유사하겠다.




한마디로 원재료를 다른 재료와 함께

다지고 썩고 볶고 .... 등등 해서

완전히 새로운 다른 형태의 요리로 만든다는 것인데

한마디로 ...

해시를 정의 하면

" 데이터를 다른 모습으로 바꾸어 다양한 목적으로 사용하는 것을 말한다."

정의 한번 어렵구만




정의를 알면 모하나. ㅋ

이걸 왜 내가 알아야 하는 이유를 모르는데

 이유를 알아 보자.



먼저 해시가 어디에 사용되는지를 알아야 한다.

해시테이블, 암호화, 데이터 축약 등등에 사용된다.


1. 해시테이블
- 해시 같은 테이블을 주소로 이용해서 궁극의 탐색 알고리즘을 구현하는데 사용된다.
(
궁극의 이구먼 ㅋㅋ 필살기?)


2. 암호화
 
- 입력 받은 데이터를 완전히 새로운 모습으로 암호화 할때 사용된다. 
- 대표적인 예로 SHA (Secure Hash Algorithm) 이라 많이 부른다.
자세한건 찾아보시길 ㅋ


3. 데이터 축약

 - 길이가 서로 다른 데이터에 대해 일정한 길이의 출력을 만들때 사용
 커다란 데이터를 짧게 축약해서 데이터 비교시 사용되는데  대표적인 예로 카프라빈 알고리즘이 있당. ㅋ

 
왐마 ... 이 정도만 알려줘도

왜 쓰는지 이제 알것네 ㅋ

그럼 정말로 이걸 사용해?

가장 유용하게 사용되는데를

예를 들어 설명해보면


<해시를 유용하게 사용하는 예>

오늘 부터 주식거래를 하게되었엉

내가 원하는 차출발 주식에 대한 정보를 검색해야해

이게 오늘 대박을 칠수 있고 쫄딱 망할수도 있어

잘 보고 사야하는데

정보를 검색함에 있어 검색 시작하는데


순차검색으로 하면

검색 중  ing .....

오늘 주식은 살수 있는거니?




그럼 이걸 이진탐색이 되는 주식 검색기로 사용할거야 ㅋ

앗 이것 역시 ing 좀 더 빠르네

아쉬 ..  근데 

수량 : 0 주

어쩌라고 ㅠㅠ

눈물나지




그럼 한방에 접속하고 파 

그래 해시를 이용하는거야 !

~ ing  이런건 없어야 하지 않겠어 ㅋ

주식 살려면 속도가 매우 중요해 

0.0001 초에 따라 돈이 억단위로 

날라 가는데 

이거 느려서야 ㅋ


이 것만 보면 해시의 중요성을 알 수 있어 

 해시를 금융권에서는 유용하게 사용하는거야 ㅋ




그럼 해시는 어떻게 만드니 ?


해시 만드는 법은

다음 예를 보면 한방에 해결되지

당신은 7등급 호텔에 주방장이 되었어

오늘의 요리 재료 123817 가 있엉 


이 재료를 가지고 둘둘 볶고 양념하고 데쳐서

새로운 요리가 나오지

이 요리가 3819 번째 요리였어
.
.
.
당신은 다른 요리를 계속 만들어
.
.
.

요리를 고객이먹어보고

" 이거 참 맛이 거시기 하네요...

이거 멀로 만들었어요 ? "

영수증에 [3819 번째] 요리인데

물어봤엉


"아놔" 요리를 하루에 한두번해?

너는 그럼 하루에 100000번째 숨쉴때 그때 시간 물어보면 언제인지 알아?

3819 번째 먼지 내가 어떻게 알것이여

다 찾아봐야지 ㅋ



그래서 아싸리 요리할때

영수증 먹이는 방법을 을 바꿀거여


이게 첫번째 요리인데 

123817 이라는 재료이름만 가지고

해시함수를 적용하니

3819가 나왔엉

그림을 보면 쉽게 이해가 갈것 같아


그래서 이 것을 3819라 번호를 먹였어


종이에 첫번째 요리임에도 불구하고
 
영수증 [3819]라 적엇엉

이렇게 계속 진행하다.
.
.
.

손님이 물었어

나 영수증[3819]번 인데

이 요리 멀루 만들었어용?

3819 이걸 해시함수의 역순으로 내어보면

바로 123817 인데요 ㅋ

바로 말할수가 있지

그림을 보면 3819에 들어있는게 123817이라는 것을 알 수 있엉

그걸 불러주면 쉽게 이해가 갈듯 싶어




여기서 중요한건

정말로 무지하게 일반적인 이진검색 등등 보다는

무지하게 빠름을 알수가 있어

하지만 문제점 역시 많겠지

예를 들면 많은 공간을 할당해야한다는 것

하지만 속도면에서 매우 중요하니 매우 많은 공간을 버리는 거야





여기서 우리가 알아야 할 점들이 다 나와



1. 해시 함수 어떻게 설정해야 할가? 
( 해시함수에 따라서 값이 다르게 나오니 함수설정에 있어 매우 중요)

2. 매우 공간이 낭비인데 이걸 좀더 효율적으로 설정해야겠어

3. 해시함수를 통해서 항상 모든 수가 다르게 나온다는 보장이 없는데 중복된다면 어쩔건데?



이에 대한 많은 연구가 이루어졌는데

이건 다음시간에 설명하도록 하겠다.

이번장에서는 해시함수가 대충 먼지 왜 사용하는지에 대해서 알아 보았음


도움이 되었다면 리플을 남겨 주시면 힘이 됩니다 ^^