programmer life guidance 101

> Hashing - 02 좋은 해시 함수란? 현실에서는 키들이 랜덤하지 않음 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해시 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해시함수값이 불규칙적이 되도록 하는게 바람직하다. 해시함수값이 키의 특정 부분에 의해서만 결정되지 않아야 함 해시 함수 Division 기법 h(k) = k mod m 예: m = 20 and k = 91 ==> h(k) = 11 장점: 한번의 mod연산으로 계산, 따라서 빠름 단점: 어떤 m값에 대해서는 해시 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음, 가령 m = 2^p 이면 키의 하위 p비트가 해시 함수값이 됨 Multiplication 기법 ..

> Hashing - 01 Hash Table 탐색과 삽입, 삭제를 지원하는 자료구조를 dynamic set이라고 부른다. 4장에서는 검색트리를 가지고 dynamic set을 구현했고, 또다른 한가지 구현 방법이 Hashing을 이용하는 것이다. 해시 테이블은 dynamic set을 구현하는 효과적인 방법의 하나이다. "적절한 가정"하에서 평균 탐색, 삽입, 삭제시간 O(1) 보통 최악의 경우 O(n) 해시 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장 h : U -> {0, 1, 2, … , m-1} 여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합 키 k가 h(k)로 해싱되었다고 말한다. 즉, h() 해시 함수는 각 키에 대한 해시함수값을 그 키를 저장할 배열 ..