Page 1 1 Hashing - 1 Hash Functions Sections 5.1 and 5.2 Introduction ? Data items stored in an array of some fixed size. ? Search performed using some part of the data item – called the key. ? Hash function ?Maps keys to integers (which represent table indices) ?Hash(Key) = Integer ?Evenly distributed index values ?Even if the input data is not evenly distributed Simple Hash Functions ?Assumptions: ?K: an unsigned 32-bit integer ?M: the number of buckets (the number of entries in a hash table) ?Goal: ?If a bit is changed in K, all bits are equally likely to change for Hash(K) A Simple Hash Function… ?What if ?Hash(K) == K ?What is wrong? ?Values of K may not be evenly distributed ?But Hash(K) needs to be evenly distributed Another Simple Function ? If ?Hash(K) == K % M ? What is wrong? ? Suppose ?M = 10, ?K = 2, 20, 34, 42,76 ? Then K % M = 2, 0, 4, 2, 6,... ?Since 10 is even, all even K are hashed to even numbers ... Yet Another Simple Function ?If ?Hash(K) = K % P, with P a prime number ?Suppose ?P = 11 ?K = 10, 20, 30, 40 ?K % P = 10, 9, 8, 7 ?More uniform distribution… Page 2 1 Hashing - 1 Hash Functions Sections 5.1 and 5.2 Introduction ? Data items stored in an array of some fixed size. ? Search performed using some part of the data item – called the key. ? Hash function ?Maps keys to integers (which represent table indices) ?Hash(Key) = Integer ?Evenly distributed index values ?Even if the input data is not evenly distributed Simple Hash Functions ?Assumptions: ?K: an unsigned 32-bit integer ?M: the number of buckets (the number of entries in a hash table) ?Goal: ?If a bit is changed in K, all bits are equally likely to change for Hash(K) A Simple Hash Function… ?What if ?Hash(K) == K ?What is wrong? ?Values of K may not be evenly distributed ?But Hash(K) needs to be evenly distributed Another Simple Function ? If ?Hash(K) == K % M ? What is wrong? ? Suppose ?M = 10, ?K = 2, 20, 34, 42,76 ? Then K % M = 2, 0, 4, 2, 6,... ?Since 10 is even, all even K are hashed to even numbers ... Yet Another Simple Function ?If ?Hash(K) = K % P, with P a prime number ?Suppose ?P = 11 ?K = 10, 20, 30, 40 ?K % P = 10, 9, 8, 7 ?More uniform distribution… 2 Hashing a Sequence of Keys ?K = {K 1 , K 2 , …, K n ) ?E.g., Hash(“test”) = 98157 ?Design Principles ?Use the entire key ?Use the ordering information Use the Entire Key unsigned int Hash(const char *Key) { unsigned int hash = 0; for (unsigned int j = 0; j < K; j++) { hash = hash ^ Key[j] //bitwise xor } return hash; } ?Problem: Hash(“ab”)==Hash(“ba”) Use the Ordering Information unsigned int Hash(const char *Key) { unsigned int hash = 0; for (unsigned int j = 0; j < K; j++) { hash = hash ^ Key[j]; hash = hash ^ (j%32); } return hash; } Better Hash Function unsigned int Hash(const String& S) { unsigned int i; long unsigned int bigval = S.Element(0); // S[0] for (i = 1; i < S.Size(); ++i) bigval = ((bigval & 65535) * 18000) // low16 * magic_number + (bigval >> 16) // high16 + S[i]; bigval = ((bigval & 65535) * 18000) + (bigval >> 16); // bigval = low16 * magic_number + high16 return bigval & 65535; // return low16 }Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!