Constructing Hash Functions

Hash Functions for Numeric Keys

Several common methods are available for constructing hash functions for numeric keys:

Direct Addressing

Use a linear function of the key as the hash address.

h(key) = a * key + b

For example, population counts by birth year use h(key) = key - 1990:

Address	Birth year	Population
0	1990	1285 × 10,000
1	1991	1281 × 10,000
2	1992	1280 × 10,000
$\dots$	$\dots$	$\dots$
10	2000	1250 × 10,000
$\dots$	$\dots$	$\dots$
21	2011	1180 × 10,000

Direct addressing

QUESTION

With h(key) = key − 1990, what address represents 2006?

Division Method

The hash function is h(key) = key % p, where p is usually prime.

For example, h(key) = key % 17:

Address	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Key	34	18	2	20			23	7	42		27	11		30		15

Division method

QUESTION

For h(key) = key % 17, what happens to 34 and 51?

Digit Analysis

Analyze how digits vary at different positions in numeric keys, and choose relatively random positions as the hash address.

For example, use the last four digits of an 11-digit phone number: h(key) = key % 10000.

As another example, choose relatively random positions in an 18-digit identity number:

Positions and groups in an 18-digit identity number
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
3	3	0	1	0	6	1	9	9	0	1	0	0	8	0	4	1	9
Province		City		District		Year				Month		Day		Sequence			Check

Digit analysis

Folding

Split the key into groups with the same number of digits, then add them together.

For example, split the integer 56793542 into groups of three digits:

Operation	Value
	542
	793
+	056
=	1391

h(56793542) = 391

QUESTION

Split 56793542 into 056, 793, and 542. Sum them and take the last three digits. What is the address?

Mid-Square Method

Square the key and take several middle digits.

For example, the integer 56793542:

Operation	Value
	56793542
*	56793542
=	3225506412905764

h(56793542) = 641

Hash Functions for String Keys

Several common methods are available for constructing hash functions for string keys:

ASCII Sum

h(key) = \left(\sum key[i] \right)\bmod N

However, some strings produce severe collisions, such as a3, b2, c1, or eat and tea.

QUESTION

Why do eat and tea collide under an ASCII-sum hash?

Shifting

Apply positional weights to the first three characters.

h(key) = \left(key[0] \times 27^2 + key[1] \times 27 + key[2] \right)\bmod N

Some strings still collide, such as string, strong, street, and structure.

An effective improvement is to include all n characters of the key:

h(key) = \left( \sum_{i=0}^{n-1} key[n-i-1] \times 32^i \right)\bmod N

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

Use only folding for the sequence 724186035, 186035724, 905417236. Split each key into three-digit groups from the right, sum the groups, and take the last three digits: h(key) = group sum % 1000.

Show each key’s groups, sum, and final address.
Identify which keys collide and explain why.

Constructing Hash Functions

Hash Functions for Numeric Keys

Several common methods are available for constructing hash functions for numeric keys:

Direct Addressing

Use a linear function of the key as the hash address.

h(key) = a * key + b

For example, population counts by birth year use h(key) = key - 1990:

Address	Birth year	Population
0	1990	1285 × 10,000
1	1991	1281 × 10,000
2	1992	1280 × 10,000
$\dots$	$\dots$	$\dots$
10	2000	1250 × 10,000
$\dots$	$\dots$	$\dots$
21	2011	1180 × 10,000

Direct addressing

QUESTION

With h(key) = key − 1990, what address represents 2006?

Division Method

The hash function is h(key) = key % p, where p is usually prime.

For example, h(key) = key % 17:

Address	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Key	34	18	2	20			23	7	42		27	11		30		15

Division method

QUESTION

For h(key) = key % 17, what happens to 34 and 51?

Digit Analysis

Analyze how digits vary at different positions in numeric keys, and choose relatively random positions as the hash address.

For example, use the last four digits of an 11-digit phone number: h(key) = key % 10000.

As another example, choose relatively random positions in an 18-digit identity number:

Positions and groups in an 18-digit identity number
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
3	3	0	1	0	6	1	9	9	0	1	0	0	8	0	4	1	9
Province		City		District		Year				Month		Day		Sequence			Check

Digit analysis

Folding

Split the key into groups with the same number of digits, then add them together.

For example, split the integer 56793542 into groups of three digits:

Operation	Value
	542
	793
+	056
=	1391

h(56793542) = 391

QUESTION

Split 56793542 into 056, 793, and 542. Sum them and take the last three digits. What is the address?

Mid-Square Method

Square the key and take several middle digits.

For example, the integer 56793542:

Operation	Value
	56793542
*	56793542
=	3225506412905764

h(56793542) = 641

Hash Functions for String Keys

Several common methods are available for constructing hash functions for string keys:

ASCII Sum

h(key) = \left(\sum key[i] \right)\bmod N

However, some strings produce severe collisions, such as a3, b2, c1, or eat and tea.

QUESTION

Why do eat and tea collide under an ASCII-sum hash?

Shifting

Apply positional weights to the first three characters.

h(key) = \left(key[0] \times 27^2 + key[1] \times 27 + key[2] \right)\bmod N

Some strings still collide, such as string, strong, street, and structure.

An effective improvement is to include all n characters of the key:

h(key) = \left( \sum_{i=0}^{n-1} key[n-i-1] \times 32^i \right)\bmod N

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

Use only folding for the sequence 724186035, 186035724, 905417236. Split each key into three-digit groups from the right, sum the groups, and take the last three digits: h(key) = group sum % 1000.

Show each key’s groups, sum, and final address.
Identify which keys collide and explain why.

Constructing Hash Functions

Constructing Hash Functions

Hash Functions for Numeric Keys

Direct Addressing

KNOWLEDGE QUIZ

Division Method

KNOWLEDGE QUIZ

Digit Analysis

Folding

KNOWLEDGE QUIZ

Mid-Square Method

Hash Functions for String Keys

ASCII Sum

KNOWLEDGE QUIZ

Shifting

String hashing: calculate and compare

Folding: hash a new set of keys

Constructing Hash Functions

Constructing Hash Functions

Hash Functions for Numeric Keys

Direct Addressing

KNOWLEDGE QUIZ

Division Method

KNOWLEDGE QUIZ

Digit Analysis

Folding

KNOWLEDGE QUIZ

Mid-Square Method

Hash Functions for String Keys

ASCII Sum

KNOWLEDGE QUIZ

Shifting

String hashing: calculate and compare

Folding: hash a new set of keys