C++Builder Programming Forum
C++Builder  |  Delphi  |  FireMonkey  |  C/C++  |  Free Pascal  |  Firebird
볼랜드포럼 BorlandForum
 경고! 게시물 작성자의 사전 허락없는 메일주소 추출행위 절대 금지
C++빌더 포럼
Q & A
FAQ
팁&트릭
강좌/문서
자료실
컴포넌트/라이브러리
메신저 프로젝트
볼랜드포럼 홈
헤드라인 뉴스
IT 뉴스
공지사항
자유게시판
해피 브레이크
공동 프로젝트
구인/구직
회원 장터
건의사항
운영진 게시판
회원 메뉴
북마크
볼랜드포럼 광고 모집

C++빌더 강좌/문서
C++Builder Programming Tutorial&Docments
[190] String Hash 기본
둘리.CSIEDA [dooly386] 21247 읽음    2009-03-22 18:52
프로그래밍을 하다보면 string 을 많이 사용합니다. 이런 string 을 특별한 정수 코드로 만들어 사용할 필요성이 있습니다. 그러나 길이가 가변적인 string 들을 코드화 했을경우 전혀 다른 숫자가 나와야 합니다.

이런경우 hash 를 사용하게 되는데, 이러한 방식의 연장선상에 있는 것이 각종 암호화 하는 기법이 되겠죠.

즉 string 에의하여 만들어진 정수 코드값에서 거꾸로 string 을 추출 할 수 없습니다. 단 해당 코드에 대한 string
값을 테이블에 넣어두면 찾을 수 있겠죠.

이러한 hashing 기법을 사용하면 , 역시 string 으로 구성된 파일을 압축할 수도 있습니다. 앞축 파일 앞에 코드 테이블을 넣어 놓고요.  그러나 단어의 빈도수를 생각하지 않는 방식이라 압축율은 그다지 보장을 못하지만요..

일반적으로 String Hash 에 사용하는 알고리즘은 다음과 같습니다.

h = s[0]*31^(n-1) + s[1]*31^(n-2) ..............+s[n-1];

위의 수식에서

h = 정수값으로 hash 값

n = string length

32 = 최대 보장 string 길이 , 즉 최대 32자 까지 서로 다른 hash 를 보장 한다는 것이죠.

s[?] = 문자열의 문자.

즉 32를 자신이 원하는 숫자로 바꾸면 그 자리숫자까지 처리 가능합니다. 물론 자꾸 커지면 정수의 범위를 넘어설
수도 있다는것에 주의해야 합니다.

위의 식을 C 로 작성한다면 다음과 같죠.

int h = 0;
for (int i = 0; i < n; i++) 
{
    h = 31*h + s[i];
}


대부분 다 알고 계시는 기본적인 것이지만 혹시 모르시는 분이 있을까봐 적어 봅니다.
이경문 [gilgil]   2009-03-25 17:21 X
n < 32 인 모든 string의 hash value값이 다르다는 건가요?
제 상식으로는 이해가 되지 않는데요.
상기 코드를 보면
hash value range는 4바이트이고
string 길이는 32바이트라면
결국 birthday paradox에 의해 중첩된 hash value가 생겨날 수 밖에 없는 것인데...

그리고 hash가 압축에 사용되어 진다는 얘기는 뭔가요?
hash자체가 encoding만 가능하지, decoding은 안된다는 것을 전제로 하는데...
이해가 잘 안되네요, 제가 잘 몰라서요...
이경문 [gilgil]   2009-03-26 00:13 X
그리고 일반적으로 hash에서 31이 사용되는 이유는 31 숫자 자체가 prime number이고
따라서, 컴퓨터에서 사용되는 일반적인 range 숫자(256,, 65536....)와도 서로소가 됩니다.
prime number를 사용하지 않으면 hash function collision이 빈번히 일어 날 수 있기 때문입니다.
Lyn [tohnokanna]   2009-04-15 19:22 X
32자 까지만 해시 된다(즉 앞 32자가 같으면 뒤가 달라도 같은 해시가 나온다) 라는것을 설명하고 싶으신게 아니셧던가 싶네요
Lyn [tohnokanna]   2009-04-15 19:24 X
그리고 뭐.. 해시를 압축에 사용 할 수 있기야 하죠..
해시값 + 실제값 테이블 만들어 두고 데이터를 전부 해시로 치환하면...
물론 아무리생각해도 용량이 더 커질 것 같습니다만...

+ -

관련 글 리스트
190 String Hash 기본 둘리.CSIEDA 21247 2009/03/22
Google
Copyright © 1999-2015, borlandforum.com. All right reserved.