Lintcode: Hash Function & Summary: Modular Multiplication, Addition, Power & Summary: 긴 성형 long

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) * 33^3 + ascii(b) * 33^2 + ascii(c) *33 + ascii(d)) % HASH_SIZE 



                              = (97* 33^3 + 98 * 33^2 + 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







Example

For key="abcd" and size=100, return 78



Clarification

For this problem, you are not necessary to design your own hash algorithm or consider any collision issue, you just need to implement the algorithm as described.

overflow에 대해 특히 조심해야 합니다.intermediateresult라도 overflow를 조심해야 합니다
Fast Power 그 문제와 유사하다,modularmultiplicationaddition의 증명여기
(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)

 1 class Solution {

 2     /**

 3      * @param key: A String you should hash

 4      * @param HASH_SIZE: An integer

 5      * @return an integer

 6      */

 7     public int hashCode(char[] key,int HASH_SIZE) {

 8         if (key.length == 0) return 0;

 9         int result = 0;

10         int base = 1;

11         for (int i=key.length-1; i>=0; i--) {

12             int num = (int)(key[i] - '\0');

13             result += modMultiply(num, base, HASH_SIZE);

14             result = result % HASH_SIZE;

15             base = modMultiply(base, 33, HASH_SIZE);

16         }

17         return result % HASH_SIZE;

18     }

19     

20     public int modMultiply(int a, int b, int c) {

21         long temp = (long)a * b;

22         return (int)(temp % c);

23     }

24 };

15줄이 매번 base*=33이면 base를 롱형으로 정의해도 String이 길어집니다.나는 또 Math를 써 보았다.pow(33,i), 똑같은overflow.33의 파워를 억지로 계산하면 안 된다는 뜻이다. 넘칠 것이다.아니면 Modular Multiplication으로.
(A*B)modC, 주의해야 할 것은 A, B, C는 모두 int로 정의하고 A*B는overflow를 조심해야 하기 때문에 롱으로 이 곱셈을 저장한 다음modC 다음에 결과를 int형으로 저장한다
21줄, 만약 틀렸다면: a*b는 이미 overflow

1 public int modMultiply(int a, int b, int c) {

2          long temp = a * b;

3          return (int)(temp % c);

4      }

5 };

처리 방법은 다음과 같습니다. long temp = (long)a * b;또는 a와 b는 모두 long형으로 정의하고 longtemp=a*b
 
방법2:long type을 사용하지 않고 인터넷에서 다른 사람의 방법을 이해하지 못했다

 1     public int hashCode(char[] key,int HASH_SIZE) {

 2         int result = 0;

 3         for (int i = 0; i < key.length; i++) {

 4             result = helper(result, 33, HASH_SIZE);

 5             result += key[i];

 6             result %= HASH_SIZE;

 7         }

 8         return result;

 9     }

10 

11     int helper(int num, int base, int mod) {

12         int result = 0;

13         int temp = num - mod;

14         for (int i = 0; i < base; i++) {

15             if (result + temp > 0) {

16                 result += temp;

17             } else {

18                 result += num;

19             }

20         }

21         return result;

22     }