|
|
|
12 - Hash Tables.pdf
12_-_Hash_Tables.pdf
Showing 7-9 out of 10
12 - Hash Tables.pdf-Dictionaries and Hash Tables ...
12_-_Hash_Tables.pdf-Dictionaries and Hash Tables ∅ ∅
12 - Hash Tables.pdf-Dictionaries a...
12_-_Hash_Tables.pdf-Dictionaries and Hash Tables ∅ ∅
Page 7
Dictionaries and Hash Tables
13
Linear Probing
Open addressing
: the
colliding item is placed in
a different cell of the table
Linear probing
handles
collisions by placing the
colliding item in the next
(circularly) available table cell
Each table cell inspected is
referred to as a “probe”
Colliding items lump together,
causing future collisions to
cause a longer sequence of
probes
Example:
h
(
x
)
=
x
mod
13
Insert keys 18, 41,
22, 44, 59, 32, 31,
73, in this order
0
1
2
3
4
5
6
7
8
9
10
11
12
41
18
44
59
32
22
31
73
0
1
2
3
4
5
6
7
8
9
10
11
12
Dictionaries and Hash Tables
14
Linear Probing
Open addressing
: the
colliding item is placed in
a different cell of the table
Linear probing
handles
collisions by placing the
colliding item in the next
(circularly) available table cell
Each table cell inspected is
referred to as a “probe”
Colliding items lump together,
causing future collisions to
cause a longer sequence of
probes
Example:
h
(
x
)
=
x
mod
13
Insert keys 18, 41,
22, 44, 59, 32, 31,
73, in this order
0
1
2
3
4
5
6
7
8
9
10
11
12
0
1
2
3
4
5
6
7
8
9
10
11
12
41
22
59
32
31
73
Page 8
Dictionaries and Hash Tables
15
Search with Linear Probing
Consider a hash table
A
that uses linear probing
get
(
k
)
We start at cell
h
(
k
)
We probe consecutive
locations until one of the
following occurs
An item with key
k
is
found, or
An empty cell is found,
or
N
cells have been
unsuccessfully probed
Algorithm
get
(
k
)
i
←
h
(
k
)
p
←
0
repeat
c
←
A
[
i
]
if
c
=
∅
return
null
else if
c.key
()
=
k
return
c.element
()
else
i
←
(
i
+
1)
mod
N
p
←
p
+
1
until
p
=
N
return
null
Dictionaries and Hash Tables
16
Updates with Linear Probing
To handle insertions and
deletions, we introduce a
special object, called
AVAILABLE
, which replaces
deleted elements
remove
(
k
)
We search for an item with
key
k
If such an item
(
k, o
)
is
found, we replace it with the
special item
AVAILABLE
and
we return element
o
Else, we return null
put
(
k, o
)
We throw an exception if
the table is full
We start at cell
h
(
k
)
We probe consecutive
cells until one of the
following occurs
A cell
i
is found that is
either empty or stores
AVAILABLE
, or
N
cells have been
unsuccessfully probed
We store item
(
k, o
)
in
cell
i
Page 9
Dictionaries and Hash Tables
17
Double Hashing
Double hashing uses a
secondary hash function
d
(
k
)
and handles collisions
by placing an item in the
first available cell of the
series
(
i
+
j
⋅
d
(
k
)) mod
N
for
j
=
1, … ,
N
−
1
The secondary hash
function
d
(
k
)
cannot have
zero values
The table size
N
must be
a prime to allow probing
of all the cells
Common choice of
compression map for the
secondary hash function:
d
(
k
)
=
q
−
(
k
mod
q
)
where
q
<
N
q
is a prime
The possible values for
d
(
k
)
are
1, 2, … ,
q
Dictionaries and Hash Tables
18
Consider a hash table
storing integer keys
that handles collision
with double hashing
N
=
13
h
(
k
)
=
k
mod
13
d
(
k
)
=
7
−
(
k
mod
7)
Collision for cell
i
: try
cell (
i
+
j
⋅
d
(
k
)) mod
N
for
j
=
1, … ,
N
−
1
Insert keys 18, 41,
22, 44, 59, 32, 31,
73, in this order
Example of Double Hashing
k
h
(
k
)
d
(
k
)
Probes
18
5
3
5
41
2
1
2
22
9
6
9
44
5
5
5
10
59
7
4
7
32
6
3
6
31
5
4
5
9
0
73
8
4
8
0
1
2
3
4
5
6
7
8
9
10
11
12
31
41
18
32
59
73
22
44
0
1
2
3
4
5
6
7
8
9
10
11
12
Ace your assessments! Get Better Grades
Browse thousands of Study Materials & Solutions from your Favorite Schools
Concordia University
Concordia_University
School:
Data_Structures_and_Algorithms
Course:
Great resource for chem class. Had all the past labs and assignments
Leland P.
Santa Clara University
Introducing Study Plan
Using AI Tools to Help you understand and remember your course concepts better and faster than any other resource.
Find the best videos to learn every concept in that course from Youtube and Tiktok without searching.
Save All Relavent Videos & Materials and access anytime and anywhere
Prepare Smart and Guarantee better grades
Know more
Students also viewed documents
lab 18.docx
lab_18.docx
Course
Course
3
Module5QuizSTA2023.d...
Module5QuizSTA2023.docx.docx
Course
Course
10
Week 7 Test Math302....
Week_7_Test_Math302.docx.docx
Course
Course
30
Chapter 1 Assigment ...
Chapter_1_Assigment_Questions.docx.docx
Course
Course
5
Week 4 tests.docx.do...
Week_4_tests.docx.docx
Course
Course
23
Week 6 tests.docx.do...
Week_6_tests.docx.docx
Course
Course
106
