컴퓨터구조와 해싱문제 해결부탁 내공[35]

1 (1) 16개의 메모리 셀을 가지고 있다고 하므로 메모리 주소는 0~15까지 할당이 되겠군요.
레지스터에 관한 얘기가 없으니 대충 AX(산술 레지스터)는 있다고 가정을 해보죠.
덧셈과 저장만이 가능하다면
ADD A B
STR A
정도의 명령어만 있으면 될 거 같구요.
ADD는 A와 B의 값을 더해서 AX(산술 레지스터)에 저장을 하는 명령어라고 정의하고,
STR A는 AX의 값을 A번지에 저장을 하는 기능이라고 정의해 보면

그럼 1 (2)는 다음과 같이 coding을 할 수 있겠죠.
ADD 0 0
STR 2
ADD 2 1
STR 0

이번엔 레지스터가 없고 메모리만 사용한다고 해보면
컴퓨터의 구조는 ALU에 덧셈기능만 딸랑 있는 경우겠죠.
저장기능이라고 해봐야 X + 0 한 결과를 저장하면 되니까요. *^_^*
ADD A B
MOV A B
정도의 명령어만 있으면 될 거 같구요.
ADD는 A와 B를 더해서 A에 저장하라는 명령어로 정의하고
MOV는 B의 값을 A에 넣어라..로 될 수 있겠죠
그럼 (2)는 다음과 같이 coding이 될 수 있겠죠
ADD 1 0 ADD 0 1

뭐 어쨌거나 문제에 레지스터가 있을 수 있는지가 없어서 대충 2가지 case로 나누어 살펴 봤습니다.

그리고 반드시 operator가 2개나 그 이하의 operand를 갖으라는 법도 없으니
ADD A B C
MOV A B
식으로 기계어를 정의하는 것도 가능할 것입니다.
물론 이 경우에는 B번지의 값과 C번지의 값을 더해서 A에 저장하는 ADD가 될 꺼구요.


(사실 문제에 대해 좀 불명확한 부분들이 있어서 이정도에서 설명을 그칠까 합니다.)




그럼 두번째 문제로 들어가서
'abc'라는 문자열이 있다고 하면
사실 hashing은 정말 정의대로만 따른다면
숫자로 만들어 주는 함수이기만 하면 되므로
f('abc') = 3
f('z') = 3
이렇게 어떤 문자열을 넣어도 3이라는 상수가 도출되는 함수도 (비록 제일 쓸모없는 해쉬 함수가 될지라도) 해쉬 함수라고 볼 수 있겠죠
위와 같은 경우 bin size(해쉬 함수의 치역)는 1이 됩니다.
딱 하나만 존재하기 때문이죠.

이번엔 맨 앞 문자가 영문자면 1을 아니면 0을 돌려주는 해쉬 함수라고 해보면
이 해쉬 함수의 bin size는 2가 되겠죠.. 0아니면 1이므로...

이렇게 bin이 제한이 있고 입력 문자열이 bin의 크기보다 큰 경우에는 비둘기집 원리에 의거하여 collision이 반드시 발생을 하게 됩니다.
(비둘기집 원리: 비둘기의 수가 비둘기집의 수보다 많으면 최소한 한 집 이상에는 2마리 이상의 비둘기가 산다 - 자세한 내용은 검색을... ^^;;)

collision을 피하기 위한 방법으로는 입력될 문자열의 수가 유한한 경우에는
PMH(perfect minimal hash) 알고리즘과 같이 단 하나의 충돌도 일어나지 않게 만들 수 있기도 합니다.

즉, bin의 size가 크면 클 수록 collision이 발생할 확률이 줄어들게 됩니다.

하지만 이러한 충돌이 일어나지 않게 hash함수를 만드는 것은 쉽지 않은 문제입니다. 이러한 문제(bin은 유한하지만 입력되는 문자열의 종류가 무한한 경우)에 대한 해결을 하기 위한 방법은 계산적으로는 불가능할지 몰라도, 이론적으로는 존재하지 않습니다.