Week 4 of Data structures - Hash functions
이번 강의에서는 Hash function에 대해 더 깊이들어가보고 두가지 예시를 통해 알아보았다.
우선 이전 강의에서도 들었던 Phone Book에 대한 예시이다.
전화번호부에 두개의 Map이 존재할 수 있는데 1번은 번호 --> 이름, 2번은 이름 --> 번호 의 순으로 찾게 되는 과정이다.
우선 번호를 통해 이름을 찾기 위한 Map을 구성하려면 Direct addressing을 했던 방식을 도입하여 위와 같이 7자리 수의 번호를 0~10^7자리의 숫자로 변환이 가능할 것이다.
따라서 위와 같은 형식으로 Map이 짜여지며 숫자에 맞게 이름을 찾을 수 있게 된다.
하지만 알다시피 저 숫자 자체만으로도 굉장히 큰 수 인데다가 지역번호와 국가번호까지 추가가 된다면 할당해야하는 메모리는 기하급수적으로 늘어날 것이다. 이를 해결하기 위해 Chaining을 다시금 적용해 본다.
이전에 Chaining을 진행한 절차와 거의 동일하게 진행하는 수순을 거치며 예시를 보면,
위와 같은 형태로 Chaining이 될 수 있다.
n개의 전화번호, m개의 기수(index), 가장 긴 체인의 길이인 c의 파라메터를 가지며 메모리 사용 복잡도는 O(n+m)이고 작동 시간 복잡도는 O(c+1)이다. 알파는 n/m이며 load factor라고 불리는데 잠시 뒤 사용처가 나온다.
좋은 예시로는 위와 같이 chain이 고르게 분포하고 있고 길이인 c가 작을 수록 적절하다.
반면 위와 같은 경우 c가 클수록 복잡도가 상승하기에 좋지 않다.
그럼 hash function을 어떻게 구섷아는지에 대한 질문을 던질 수 가 있는데 처음 3개의 숫자만 hash map으로 구성한다면 보통 지역번호이기에 굉장히 중첩되는, 즉 c가 커지는 현상을 초래할 수 있어 나쁜 예가 된다.
마지막 번호 3개로 지정한다면 우리나라는 아니지만 000과 같이 끝자리가 같은 경우가 많아 이 또한 적절하지 못하다고 한다.
그렇다면 랜덤하게 3개만 뽑아오는 것은 정규분포에 걸맞는 hash 값들을 뽑아낼 수 있겠지만 같은 값을 넣어도 다른 hash 값이 출력된다면 이는 재현성에 문제가 있다. 따라서 hash function은 결정적(재현가능)이어야 한다.
그래서 위와 같은 조건들을 만족하는 hash function들을 좋은 예로 들 수 있겠다.
부명제로 일반적인 hash function이 없음을 설명하고 적절하지 못한 입력이 많은 충돌을 일으킴을 알려준다.
간략한 사례로 hash key가 3개만 존재할 때 위와 같이 hash key가 1일 경우 적어도 33%의 입력들이 충돌할 가능성을 가지게 됨을 보여준다.
그렇다면 좋은 hash function을 구현하기 위해 Quick sort 방식을 응용하고자 한다.
일단 Universal family의 정의를 보고,
맨 마지막에 해당하는 수식이 충돌을 최소로 일어나는 수식임을 알려주며,
중간에 랜덤화하는 과정이 어떤 과정으로 일어나는지 설명하였다.
Running time에 대해 설명하는 시트이며 h가 universal family로부터 랜덤하게 선택되었다면 가장 긴 체인의 복잡도는 O(1+a)임을 알려준다. 아까 보았던 load factor가 여기서 사용된다.
이론적으로 load factor의 크기는 0.5~1사이의 값을 가진다.
그리고 n개가 미리 정해저있지 않는다면 아주 큰 hash table로 시작하는 것보다 dynamic하게 크기를 조절하는 형태로 가져가며 그 조건을 a의 값으로 조정하며 rehash의 과정을 거친다고 한다.
만약 load factor가 0.9를 넘길 때마다 rehash과정을 거쳐 hash table의 크기를 재조정할 때의 pseudo code이다.
rehash의 running time은 O(n)이며 amortized running time은 O(1)이 될 것이다.
실제 사례를 들어 보여주며 3번째에서 p값이 10 000 019와 같이 정하는 이유는 소수로 그 값을 결정하기 때문이다.
hashing integers 부명제를 보면 조건들을 확인할 수 있고,
위와 같은 퀴즈도 같은 맥락에서 성립함을 알 수 있다. (각 a, b값들은 독립적이기 때문에)
이제 Full 예시를 보면 명확히 이해가 가능하다.
1. a = 34, b = 2 --> hp(34, 2)
2. x = 148-25-67 -->1 482 567
3. p = 10 000 019
4. (a*x + b) mod p = 407185
5. 407185 mod 1000 = 185
6. h(x) = 185
이를 일반화 하면 다시금 위와 같이 정리를 할 수 있겠다.
이번에는 반대로 이름으로 번호를 찾는 hash map을 구성해본다.
문자열을 hashing할 때에는 마찬가지로 특정 자리수로만 hash code를 선정하기에 리스크가 따른다. 위처럼 두번째 글자가 모두 같으면 첫번째 자리 글자를 쓰지않는 다는 조건에서는 이들의 hash code가 모두 같기 때문이다.
따라서 ASCII코드나 Unicode와 같은 정수화시킨 값을 활용한다.
이를 polynomial hashing이라고 하며 이에 대한 수식은 위와 같다.
PolyHash의 기능은 문자열의 뒷자리부터 일정한 연산을해가며 첫자리까지 모두 연산을 마쳐 hash code를 결정하는 API이다.
중간의 퀴즈는 보면서 약간 의구심을 가지고 있었던 부분인데 3번째 연산 식이 (S[1] + (S[2] mod p)x) mod p와 같이 되는 이유는 해설에 나와있다.
위에서 PolyHash의 기능은 자바에서 hash code 메쏘드로 내재되어있다고 한다.
두개의 다른 문자열의 길이가 최대 L+1일 때 충돌이 일어나는 경우의 수는 최대 L/p라고 부명제에서 알려준다. 이에 대한 증명을 추가 영상에서 한다고 하지만 시간이 없으므로 패스..
기수 고정에 대한 내용을 얘기하는데 어디에 필요한 것인지 아직은 와닿지 않는다.
그래서 퀴즈도 넘어갔다.
다시금 Polynomial Hashing으로 돌아와서 만약 p > mL을 만족하면 두개의 다른 문자열의 충돌 가능성은 O(1/m)이라고 한다.
Running time의 경우 c의 복잡도는 O(1+a)이고 PolyHash의 복잡도는 O(lSl)가 될 것이다.
결론에서 hashing 과정을 integer --> string, string --> integer로 변환하는 것을 상기시켰다.
이번 강의에서는 Hash function에 대해 더 깊이들어가보고 두가지 예시를 통해 알아보았다.
우선 이전 강의에서도 들었던 Phone Book에 대한 예시이다.
전화번호부에 두개의 Map이 존재할 수 있는데 1번은 번호 --> 이름, 2번은 이름 --> 번호 의 순으로 찾게 되는 과정이다.
우선 번호를 통해 이름을 찾기 위한 Map을 구성하려면 Direct addressing을 했던 방식을 도입하여 위와 같이 7자리 수의 번호를 0~10^7자리의 숫자로 변환이 가능할 것이다.
따라서 위와 같은 형식으로 Map이 짜여지며 숫자에 맞게 이름을 찾을 수 있게 된다.
하지만 알다시피 저 숫자 자체만으로도 굉장히 큰 수 인데다가 지역번호와 국가번호까지 추가가 된다면 할당해야하는 메모리는 기하급수적으로 늘어날 것이다. 이를 해결하기 위해 Chaining을 다시금 적용해 본다.
이전에 Chaining을 진행한 절차와 거의 동일하게 진행하는 수순을 거치며 예시를 보면,
위와 같은 형태로 Chaining이 될 수 있다.
n개의 전화번호, m개의 기수(index), 가장 긴 체인의 길이인 c의 파라메터를 가지며 메모리 사용 복잡도는 O(n+m)이고 작동 시간 복잡도는 O(c+1)이다. 알파는 n/m이며 load factor라고 불리는데 잠시 뒤 사용처가 나온다.
좋은 예시로는 위와 같이 chain이 고르게 분포하고 있고 길이인 c가 작을 수록 적절하다.
반면 위와 같은 경우 c가 클수록 복잡도가 상승하기에 좋지 않다.
그럼 hash function을 어떻게 구섷아는지에 대한 질문을 던질 수 가 있는데 처음 3개의 숫자만 hash map으로 구성한다면 보통 지역번호이기에 굉장히 중첩되는, 즉 c가 커지는 현상을 초래할 수 있어 나쁜 예가 된다.
마지막 번호 3개로 지정한다면 우리나라는 아니지만 000과 같이 끝자리가 같은 경우가 많아 이 또한 적절하지 못하다고 한다.
그렇다면 랜덤하게 3개만 뽑아오는 것은 정규분포에 걸맞는 hash 값들을 뽑아낼 수 있겠지만 같은 값을 넣어도 다른 hash 값이 출력된다면 이는 재현성에 문제가 있다. 따라서 hash function은 결정적(재현가능)이어야 한다.
그래서 위와 같은 조건들을 만족하는 hash function들을 좋은 예로 들 수 있겠다.
부명제로 일반적인 hash function이 없음을 설명하고 적절하지 못한 입력이 많은 충돌을 일으킴을 알려준다.
간략한 사례로 hash key가 3개만 존재할 때 위와 같이 hash key가 1일 경우 적어도 33%의 입력들이 충돌할 가능성을 가지게 됨을 보여준다.
그렇다면 좋은 hash function을 구현하기 위해 Quick sort 방식을 응용하고자 한다.
일단 Universal family의 정의를 보고,
맨 마지막에 해당하는 수식이 충돌을 최소로 일어나는 수식임을 알려주며,
중간에 랜덤화하는 과정이 어떤 과정으로 일어나는지 설명하였다.
Running time에 대해 설명하는 시트이며 h가 universal family로부터 랜덤하게 선택되었다면 가장 긴 체인의 복잡도는 O(1+a)임을 알려준다. 아까 보았던 load factor가 여기서 사용된다.
이론적으로 load factor의 크기는 0.5~1사이의 값을 가진다.
그리고 n개가 미리 정해저있지 않는다면 아주 큰 hash table로 시작하는 것보다 dynamic하게 크기를 조절하는 형태로 가져가며 그 조건을 a의 값으로 조정하며 rehash의 과정을 거친다고 한다.
만약 load factor가 0.9를 넘길 때마다 rehash과정을 거쳐 hash table의 크기를 재조정할 때의 pseudo code이다.
rehash의 running time은 O(n)이며 amortized running time은 O(1)이 될 것이다.
실제 사례를 들어 보여주며 3번째에서 p값이 10 000 019와 같이 정하는 이유는 소수로 그 값을 결정하기 때문이다.
hashing integers 부명제를 보면 조건들을 확인할 수 있고,
위와 같은 퀴즈도 같은 맥락에서 성립함을 알 수 있다. (각 a, b값들은 독립적이기 때문에)
이제 Full 예시를 보면 명확히 이해가 가능하다.
1. a = 34, b = 2 --> hp(34, 2)
2. x = 148-25-67 -->1 482 567
3. p = 10 000 019
4. (a*x + b) mod p = 407185
5. 407185 mod 1000 = 185
6. h(x) = 185
이를 일반화 하면 다시금 위와 같이 정리를 할 수 있겠다.
이번에는 반대로 이름으로 번호를 찾는 hash map을 구성해본다.
문자열을 hashing할 때에는 마찬가지로 특정 자리수로만 hash code를 선정하기에 리스크가 따른다. 위처럼 두번째 글자가 모두 같으면 첫번째 자리 글자를 쓰지않는 다는 조건에서는 이들의 hash code가 모두 같기 때문이다.
따라서 ASCII코드나 Unicode와 같은 정수화시킨 값을 활용한다.
이를 polynomial hashing이라고 하며 이에 대한 수식은 위와 같다.
PolyHash의 기능은 문자열의 뒷자리부터 일정한 연산을해가며 첫자리까지 모두 연산을 마쳐 hash code를 결정하는 API이다.
중간의 퀴즈는 보면서 약간 의구심을 가지고 있었던 부분인데 3번째 연산 식이 (S[1] + (S[2] mod p)x) mod p와 같이 되는 이유는 해설에 나와있다.
위에서 PolyHash의 기능은 자바에서 hash code 메쏘드로 내재되어있다고 한다.
두개의 다른 문자열의 길이가 최대 L+1일 때 충돌이 일어나는 경우의 수는 최대 L/p라고 부명제에서 알려준다. 이에 대한 증명을 추가 영상에서 한다고 하지만 시간이 없으므로 패스..
기수 고정에 대한 내용을 얘기하는데 어디에 필요한 것인지 아직은 와닿지 않는다.
그래서 퀴즈도 넘어갔다.
다시금 Polynomial Hashing으로 돌아와서 만약 p > mL을 만족하면 두개의 다른 문자열의 충돌 가능성은 O(1/m)이라고 한다.
Running time의 경우 c의 복잡도는 O(1+a)이고 PolyHash의 복잡도는 O(lSl)가 될 것이다.
결론에서 hashing 과정을 integer --> string, string --> integer로 변환하는 것을 상기시켰다.
솔직히 오늘은 블로그작성하는거 귀찮았지ㅋㅋ
답글삭제