Hash functions in data structure

applications of cryptographic hash functions ppt and hash functions and hash tables and cryptographic hash functions examples
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Hash functions Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Hash functions 2 Outline In this talk, we will discuss – Finding 32-bit hash values using: • Predetermined hash values – Auto-incremented hash values – Address-based hash values • Arithmetic hash values – Example: stringsHash functions 3 9.2 Definitions What is a hash of an object? From Merriam-Webster: a restatement of something that is already known The ultimate goal is to map onto an integer range 0, 1, 2, ..., M – 1Hash functions 4 9.2.1 The hash process Object We will look at the first problem – Hashing an object into a 32-bit integer 32-bit integer – Subsequent topics will examine the next Modulus, mid-square, steps multiplicative, Fibonacci Map to an index 0, ..., M – 1 Deal with collisions Chained hash tables Open addressing Linear probing Quadratic probing Double hashingHash functions 5 9.2.2 Properties Necessary properties of such a hash function h are: 1a. Should be fast: ideally Q(1) 1b. The hash value must be deterministic • It must always return the same 32-bit integer each time 1c. Equal objects hash to equal values • x = y ⇒ h(x) = h(y) 1d. If two objects are randomly chosen, there should be only a one-in- 32 2 chance that they have the same hash valueHash functions 6 9.2.3 Types of hash functions We will look at two classes of hash functions – Predetermined hash functions (explicit) – Arithmetic hash functions (implicit)Hash functions 7 9.2.4 Predetermined hash functions The easiest solution is to give each object a unique number class Class_name private: 31 31 unsigned int hash_value; // int: –2 , ..., 2– 1 32 // unsigned int: 0, ..., 2– 1 public: Class_name(); unsigned int hash() const; Class_name::Class_name() ; hash_value = ???; unsigned int Class_name::hash() const return hash_value; Hash functions 8 9.2.4 Predetermined hash functions For example, an auto-incremented static member variable class Class_name private: unsigned int hash_value; static unsigned int hash_count; public: Class_name(); unsigned int hash() const; Class_name::Class_name() ; hash_value = hash_count; ++hash_count; unsigned int Class_name::hash_count = 0; unsigned int Class_name::hash() const return hash_value; Hash functions 9 9.2.4 Predetermined hash functions Examples: All UW co-op student have two hash values: – UW Student ID Number – Social Insurance Number Any 9-digit-decimal integer yields a 32-bit integer 9 lg( 10 ) = 29.897Hash functions 10 9.2.4 Predetermined hash functions If we only need the hash value while the object exists in memory, use the address: unsigned int Class_name::hash() const return reinterpret_castunsigned int( this ); This fails if an object may be stored in secondary memory – It will have a different address the next time it is loadedHash functions 11 9.2.4.1 Predetermined hash functions Predetermined hash values give each object a unique hash value This is not always appropriate: – Objects which are conceptually equal: Rational x(1, 2); Rational y(3, 6); – Strings with the same characters: string str1 = "Hello world"; string str2 = "Hello world"; These hash values must depend on the member variables – Usually this uses arithmetic functionsHash functions 12 9.2.5 Arithmetic Hash Values An arithmetic hash value is a deterministic function that is calculated from the relevant member variables of an object We will look at arithmetic hash functions for: – Rational numbers, and – StringsHash functions 13 9.2.5.1 Rational number class What if we just add the numerator and denominator? class Rational private: int numer, denom; public: Rational( int, int ); ; unsigned int Rational::hash() const return static_castunsigned int( numer ) + static_castunsigned int( denom ); Hash functions 14 9.2.5.1 Rational number class We could improve on this: multiply the denominator by a large prime: class Rational private: int numer, denom; public: Rational( int, int ); ; unsigned int Rational::hash() const return static_castunsigned int( numer ) + 429496751static_castunsigned int( denom ); Hash functions 15 9.2.5.1 Rational number class For example, the output of int main() cout Rational( 0, 1 ).hash() endl; cout Rational( 1, 2 ).hash() endl; cout Rational( 2, 3 ).hash() endl; cout Rational( 99, 100 ).hash() endl; return 0; is 429496751 858993503 1288490255 2239 http://xkcd.com/571/ Recall that arithmetic operations wrap on overflowHash functions 16 9.2.5.1 Rational number class This hash function does not generate unique values – The following pairs have the same hash values: 0/1 1327433019/800977868 1/2 534326814/1480277007 2/3 820039962/1486995867 – Finding rational numbers with matching hash values is very difficult: – Finding these required the generation of 1 500 000 000 random rational numbers – It is fast: Q(1) – It does produce an even distributionHash functions 17 9.2.5.1 Rational number class Problem: – The rational numbers 1/2 and 2/4 have different values – The output of int main() cout Rational( 1, 2 ).hash(); cout Rational( 2, 4 ).hash(); return 0; is 858993503 1717987006Hash functions 18 9.2.5.1 Rational number class Solution: divide through by the greatest common divisor Rational::Rational( int a, int b ):numer(a), denom(b) int divisor = gcd( numer, denom ); numer /= divisor; denom /= divisor; int gcd( int a, int b) while( true ) if ( a == 0 ) return (b = 0) ? b : -b; b %= a; if ( b == 0 ) return (a = 0) ? a : -a; a %= b; Hash functions 19 9.2.5.1 Rational number class Problem: 11 – The rational numbers and have different values 22 – The output of int main() cout Rational( 1, 2 ).hash(); cout Rational( -1, -2 ).hash(); return 0; is 858993503 3435973793Hash functions 20 9.2.5.1 Rational number class Solution: define a normal form – Require that the denominator is positive Rational::Rational( int a, int b ):numer(a), denom(b) int divisor = gcd( numer, denom ); divisor = (denom = 0) ? divisor : -divisor; numer /= divisor; denom /= divisor;