程序代写代做代考 algorithm scheme data structure PowerPoint Presentation

PowerPoint Presentation

Data Structures: A Pseudocode Approach with C, Second Edition
*

List Searches

In this section we study searches that work with arrays. The two basic searches for arrays are the sequential search and the binary search.

Sequential Search
Variations on Sequential Searches
Binary Search
Analyzing Search Algorithms

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

One of the
most common
and
most time consuming
operations
in computer science is
searching,
the process used to find the location of a target
among a list of objects.

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
Algorithm
sequentialSearch( list, last, num, locn )

Pre: list, last, num
Post: locn
Return: True/False

i = 0
loop( i < last AND num ≠ list[i] ) i = i + 1 end loop locn = i return( num EQUAL TO list[i] ) end guess Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Algorithm sentinelSearch( list, last, num, locn ) Pre: list, last, num Post: locn Return: True/False list[last + 1] = num i = 0 loop( num ≠ list[i] ) i = i + 1 end loop locn = i return( i ≤ last ) end guess Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Algorithm binarySearch(list, last, num, locn ) Pre: list, last, num Post: locn Return: True/False first = 0 loop( first ≤ last ){ mid = ( first + last ) DIV 2 if( num > list[mid] )
first = mid + 1
else
if( num < list[mid] ) last = mid – 1 else first = last + 1 end if end if end loop locn = mid return( num EQUAL TO list[mid]) end guess Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Hashed List Searches The goal of a hashed search is to find the target data in only one test (in most cases). Basic Concepts Hashing Methods One Hashing Algorithm Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Example Class size: 10 Student ID Grade ======== ===== 7 A 9 B 2 C 8 A 5 A 3 B 0 C Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #1 0 1 2 3 4 5 6 7 8 9 Data stored as received (7,A) (9,B) (2,C) (8,A) (5,A) (3,B) (0,C) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #1 0 1 2 3 4 5 6 7 8 9 Linear (sequential) search! (7,A) (9,B) (2,C) (8,A) (5,A) (3,B) (0,C) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Example Class size: 10 Student ID Grade ======== ===== 7 A 9 B 2 C 8 A 5 A 3 B 0 C Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Input: (7,A) Data stored on index (7,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Input: (9,A) (7,A) (9,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Input: (2,C) (2,C) (7,A) (9,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Input: (8,A) (2,C) (7,A) (8,A) (9,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Input: (5,A) (2,C) (5,A) (7,A) (8,A) (9,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Input: (3,B) (2,C) (3,B) (5,A) (7,A) (8,A) (9,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Input: (0,C) (0,C) (2,C) (3,B) (5,A) (7,A) (8,A) (9,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Solution #2 0 1 2 3 4 5 6 7 8 9 Constant (hash) search! (0,C) (2,C) (3,B) (5,A) (7,A) (8,A) (9,A) Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * The verb “to hash” means to chop something up or to make a mess out of it. Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 13-3 Hashed List Searches The goal of a hashed search is to find the target data in only one test. After discussing some basic hashed list concepts, we discuss eight hashing methods. At the end of the section, we develop a hashing algorithm that uses several of the methods discussed in the section. Basic Concepts Hashing Methods One Hashing Algorithm Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Home Address = Key Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Subtraction Hashing 10001 1 10002 2 10003 3 10004 4 10005 5 10006 6 Key Home Address = Key – 10000 Home Address = Key - Constant Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Home Address = Key MODULO size Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Digit Extraction 379452 394 121267 112 378845 388 160252 102 045128 051 Key Home Address Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Mid-square Key = 9452 9452 * 9452 = 89340304 Home Address = 3403 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Mid-square Variation: Key = 379452 379 * 379 = 143641 Home Address = 364 Key = 045128 045 * 045 = 002025 Home Address = 202 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Home Address = (a * key + b) MOD size Pseudorandom Generation a, b, size – prime numbers (for maximum efficiency) a = 17 b = 7 size = 307 Key = 121267 Home Address = (17 * 121267 + 7 ) MOD 307 = 41 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Donald Knuth A hash function transforms a key into a unique number – such functions aren’t easy to discover. Functions that avoid duplicate values are surprisingly rare, even with a fairly large table. Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * “A good hash function should satisfy two requirements: Its computation should be very fast (somewhat machine-dependent). It should minimize collisions (data dependent).” D. Knuth Interview Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Von Mises Birthday paradox - 1930s: If 23 or more people are present in a room, chances are good that two of them will have the same month and day of birth. In other words, if we select a random function that maps 23 keys into a table of 365, the probability that no two keys map into the same location is less than one-half. Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Winter 2013 37 students Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec 10 27 21 13 15 9 16 8 4 22 1 12 11 28 20 20 24 19 7 23 7 18 23 21 20 19 12 24 20 22 26 22 26 24 29 29 29 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Spring 2014 39 students Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec 14 19 7 2 8 16 4 2 16 4 10 8 15 20 14 6 9 18 9 4 27 10 12 14 10 23 18 16 8 27 23 16 21 10 27 26 13 28 21 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Fall 2014 XX students Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Collision Resolution We discuss three structural approaches and four specific collision resolution algorithms.. Open Addressing Linked List Collision Resolution Bucket Hashing Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Examples (A) Hash Method: Modulo-division Collision resolution: No-name: use another array to store all synonyms Hash array size: 10 22, 30, 47, 62, 18, 27, 37, 82, 97 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 22 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 47 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 47 62 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 47 18 62 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 47 18 62 27 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 47 18 62 27 37 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 47 18 62 27 37 82 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * 0 1 2 3 4 5 6 7 8 9 22, 30, 47, 62, 18, 27, 37, 82, 97 0 1 2 3 4 5 Hash table Overflow table 30 22 47 18 62 27 37 82 97 Data Structures: A Pseudocode Approach with C, Second Edition Data Structures: A Pseudocode Approach with C, Second Edition * Key Address 22 22 % 10 => 2
30 30 % 10 => 0
47 47 % 10 => 7
62 62 % 10 => 2 collision
18 18 % 10 => 8
27 27 % 10 => 7 collision
37 37 % 10 => 7 collision
82 82 % 10 => 2 collision
97 97 % 10 => 7 collision

Collisions: 5 Load Factor: 4/10 => 40%

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
Examples

(B) Hash Method: Modulo-division

Collision resolution: Buckets

Hash array size: 10

22, 30, 47, 62, 18, 27, 37, 82, 97

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
(B) Hash method: Modulo-division
Collision resolution: Buckets
Hash array size: 10
22, 30, 47, 62, 18, 27, 37, 82, 97
Key Address
22 22 % 10 => 2
30 30 % 10 => 0
62 62 % 10 => 2 Collision!
18 18 % 10 => 8
27 27 % 10 => 7 Collision!
37 37 % 10 => 7 Collision!
82 82 % 10 => 2 Collision!
97 97 % 10 => 7 Collision!
Collisions: 5 Load Factor: 4/10 => 40%

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B
Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

0
0 1 2 3

0
0 1 2 3
22
30
47
62
18
27
37
82
97

0
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

B
Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

0
0 1 2 3

1
0 1 2 3

0
0 1 2 3

0
0 1 2 3
22
30
47
62
18
27
37
82
97

0
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

B
Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

1
0 1 2 3

0
0 1 2 3

1
0 1 2 3

0
0 1 2 3

0
0 1 2 3
22
30
47
62
18
27
37
82
97

0
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B

Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

1
0 1 2 3

0
0 1 2 3

1
0 1 2 3

0
0 1 2 3

1
0 1 2 3
22
30
47
62
18
27
37
82
97

0
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B

Bucket 8
Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

1
0 1 2 3

0
0 1 2 3
62

2
0 1 2 3

0
0 1 2 3

1
0 1 2 3
22
30
47
62
18
27
37
82
97

0
0 1 2 3

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B

Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

1
0 1 2 3

0
0 1 2 3
62

2
0 1 2 3

0
0 1 2 3

1
0 1 2 3
22
30
47
62
18
27
37
82
97

1
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B

Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

1
0 1 2 3

0
0 1 2 3
62

2
0 1 2 3

0
0 1 2 3

0 1 2 3
27

2
0 1 2 3
22
30
47
62
18
27
37
82
97

1
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B

Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

1
0 1 2 3

0
0 1 2 3
62

2
0 1 2 3

0
0 1 2 3

0 1 2 3
27
37

3
0 1 2 3
22
30
47
62
18
27
37
82
97

1
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B

Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7

1
0 1 2 3

0
0 1 2 3
62
82

3
0 1 2 3

0
0 1 2 3

0 1 2 3
27
37

3
0 1 2 3
22
30
47
62
18
27
37
82
97

1
0 1 2 3
Bucket 8

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
B
22
30
47
62
18
27
37
82
97

Bucket 0
Bucket 1
Bucket 2
Bucket 3
Bucket 4
Bucket 5
Bucket 6
Bucket 7
Bucket 8

1
0 1 2 3

0
0 1 2 3
62
82

3
0 1 2 3

0
0 1 2 3

0 1 2 3
27
37
97
47

4
0 1 2 3

1
0 1 2 3

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
Examples

Collision resolution: Linked Lists

Hash array size: 10

22, 30, 47, 62, 18, 27, 37, 82, 97

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

0 1 2 3 4 5 6 7 8 9

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

0 1 2 3 4 5 6 7 8 9

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

0 1 2 3 4 5 6 7 8 9

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

0 1 2 3 4 5 6 7 8 9
62

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

18
47

0 1 2 3 4 5 6 7 8 9
62

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

18
47

0 1 2 3 4 5 6 7 8 9
62
27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

18
47

0 1 2 3 4 5 6 7 8 9
62
27
37

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

18
47

0 1 2 3 4 5 6 7 8 9
62
82
27
37

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97

18
47

0 1 2 3 4 5 6 7 8 9
62
82
27
37
97

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
(C) Hash method: Modulo-division
Collision resolution: Linked Lists
Hash array size: 10
22, 30, 47, 62, 18, 27, 37, 82, 97
Key Address
22 22 % 10 => 2
30 30 % 10 => 0
47 47 % 10 => 7
62 62 % 10 => 2 collision
18 18 % 10 => 8
27 27 % 10 => 7 collision
37 37 % 10 => 7 collision
82 82 % 10 => 2 collision
97 97 % 10 => 7 collision
Collisions: 5 Load Factor: 4/10 => 40%

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
(D) Hash method: Modulo-division
Collision resolution: Linked Lists
Hash array size: 11
22, 30, 47, 62, 18, 27, 37, 82, 97
Key Address
22 22 % 11 => 0
30 30 % 11 => 8
47 47 % 11 => 3
62 62 % 11 => 7
18 18 % 11 => 7 collision
27 27 % 11 => 5
37 37 % 11 => 4
82 82 % 11 => 5 collision
97 97 % 11 => 9
Collisions: 2 Load Factor: 7/11 => 63.6%

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9 10
82
18
22, 30, 47, 62, 18, 27, 37, 82, 97
22 47 37 27 62 30 97

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
Examples

(E) Hash Method: Modulo-division

Collision resolution: Linear Probe

Hash array size: 10

22, 30, 47, 62, 18, 27, 37, 82, 97

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 0
Load Factor: 1/10 => 10%
Address = 22 % 10 = 2
22

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 0
Load Factor: 2/10 => 20%
Address = 30 % 10 = 0
30 22

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 0
Load Factor: 3/10 => 30%
Address = 47 % 10 = 7
30 22 47

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 0 + 1 = 1
Load Factor: 4/10 => 40%
Address = 62 % 10 = 2
Collision!
Address = 2 + 1 = 3
30 22 62 47

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 1
Load Factor: 5/10 => 50%
Address = 18 % 10 = 8
30 22 62 47 18

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 1 + 1 = 2
Load Factor: 5/10 => 50%
Address = 27 % 10 = 7
Collision!
30 22 62 47 18

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 2 + 1 = 3
Load Factor: 5/10 => 50%
Address = 27 % 10 = 7
Address = 7 + 1 = 8
Collision!
30 22 62 47 18

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 3
Load Factor: 6/10 => 60%
Address = 27 % 10 = 7
Address = 7 + 1 = 8
Address = 8 + 1 = 9
30 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 3 + 1 = 4
Load Factor: 6/10 => 60%
Address = 37 % 10 = 7
Collision!
30 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 4 + 1 = 5
Load Factor: 6/10 => 60%
Address = 37 % 10 = 7
Address = 7 + 1 = 8
Collision!
30 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 5 + 1 = 6
Load Factor: 6/10 => 60%
Address = 37 % 10 = 7
Address = 7 + 1 = 8
Address = 8 + 1 = 9
30 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 6 + 1 = 7
Load Factor: 6/10 => 60%
Address = 37 % 10 = 7
Address = 7 + 1 = 8
Address = 8 + 1 = 9
Address = (9 + 1)%10 = 0
30 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 7
Load Factor: 7/10 => 70%
Address = 37 % 10 = 7
Address = 7 + 1 = 8
Address = 8 + 1 = 9
Address = (9 + 1)%10 = 0
Address = (0 + 1)%10 = 1
30 37 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 7 + 1 = 8
Load Factor: 7/10 => 70%
Address = 82 % 10 = 2
30 37 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 8 + 1 = 9
Load Factor: 7/10 => 70%
Address = 82 % 10 = 2
Address = (2 + 1)%10 = 3
30 37 22 62 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 9
Load Factor: 8/10 => 80%
Address = 82 %10 = 2
Address = (2 + 1)%10 = 3
Address = (3 + 1)%10 = 4
30 37 22 62 82 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9
22, 30, 47, 62, 18, 27, 37, 82, 97

Collision count: 9 + 8 = 17
Load Factor: 9/10 => 90%
Address = 97 %10 = 7
Address = (7 + 1)%10 = 8
Address = (8 + 1)%10 = 9
Address = (9 + 1)%10 = 0
Address = (0 + 1)%10 = 1
Address = (1 + 1)%10 = 2
Address = (2 + 1)%10 = 3
Address = (3 + 1)%10 = 4
Address = (4 + 1)%10 = 5
30 37 22 62 82 97 47 18 27

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
Examples

(F) Hash Method: Modulo-division

Collision resolution: Linear Probe

Hash array size: 11

22, 30, 47, 62, 18, 27, 37, 82, 97

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
22, 30, 47, 62, 18, 27, 37, 82, 97
Key Address
22 22 % 11 => 0
30 30 % 11 => 8
47 47 % 11 => 3
62 62 % 11 => 7
18 18 % 11 => 7 Collision!
(7 + 1) % 10 => 8 Collision!
(8 + 1) % 10 => 9
27 27 % 11 => 5
37 37 % 11 => 4
82 82 % 11 => 5 Collision!
(5 + 1) % 11 => 6
97 97 % 11 => 9 Collision!
(9 + 1) % 11 => 10
Collisions: 4 Load Factor: 9/11 => 81.8%

Data Structures: A Pseudocode Approach with C, Second Edition

Data Structures: A Pseudocode Approach with C, Second Edition
*
0 1 2 3 4 5 6 7 8 9 10
22, 30, 47, 62, 18, 27, 37, 82, 97
22 47 37 27 82 62 30 18 97