Hash Function

In data structure Hash, hash function is used to convert a string(or any other type) into an integer smaller than hash size and bigger or equal to zero. The objective of designing a hash function is to "hash"the key as unreasonable as possible. A good hash function can avoid collision as less as possible. A widely used hash function algorithm is using a magic number 33, consider any string as a 33 based big integer like follow:
hashcode("abcd") = (ascii(a) * 333 + ascii(b) * 332 + ascii(c) *33 + ascii(d)) % HASH_SIZE 
                              = (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE
                              = 3595978 % HASH_SIZE
here HASH_SIZE is the capacity of the hash table (you can assume a hash table is like an array with index 0 ~ HASH_SIZE-1).
Given a string as a key and the size of hash table, return the hash value of this key.f
Lintcode의 한 문제는 기술적 함량이 없고 공식에 따라hash값을 구하는 것이다.그러나 이런straight forward의 방법은 마지막에 시간을 초과했기 때문에 사실 잉여 연산은 최적화를 할 수 있다. 즉, 마지막에 잉여 연산을 하지 않고 매 단계의 연산에서 잉여를 취할 수 있다.코드는 다음과 같습니다.

class Solution:
    """
    @param key: A String you should hash
    @param HASH_SIZE: An integer
    @return an integer
    """
    def hashCode(self, key, HASH_SIZE):
        if not key:
            return 0
        hashcode = 0
        for s in key:
            hashcode = (hashcode*33 + ord(s))%HASH_SIZE
        return hashcode

이런 조작의 정확성은 증명할 수 있다. 즉, (a+b)%c=(a%c+b)%c는 성질(1)에서 내놓을 수 있다.
(a + b) % p = (a % p + b % p) % p (1)
(a - b) % p = (a % p - b % p) % p (2)
(a * b) % p = (a % p * b % p) % p (3)
(a^b) % p = ((a % p)^b) % p (4)
추론:
만약에 a≡b(%p)라면 임의의 c에 대해 (a+c)≡(b+c)(%p)가 있다.(10)
만약에 a≡b(%p)라면 임의의 c에 대해 (a*c)≡(b*c)(%p)가 있다.(11)
만약 a≡b(%p), c≡d(%p), (a+c)≡(b+d)(%p), (a-c)≡(b-d)(%p),
(a * c) ≡ (b * d) (%p),(a/c) ≡ (b/d) (%p); (12)
 
페마의 정리: 만약에 p가 소수이고 a가 정수이며 p에 의해 제거될 수 없다면: a^(p-1)modp = 1modp
추론: 만약에 p가 소수이고 a가 정수이며 p에 의해 제거될 수 없다면: a^pmodp=amodp
다음으로 전송:https://www.cnblogs.com/sherylwang/p/5589223.html