


12  Hash Tables.pdf
12__Hash_Tables.pdf
Showing 46 out of 10
12  Hash Tables.pdfDictionaries and Hash Tables ...
12__Hash_Tables.pdfDictionaries and Hash Tables ∅ ∅
12  Hash Tables.pdfDictionaries a...
12__Hash_Tables.pdfDictionaries and Hash Tables ∅ ∅
Page 4
Dictionaries and Hash Tables
7
Hash Code Maps
Memory address
:
We reinterpret the memory
address of the key object as
an integer (default hash code
of all Java objects)
Good in general, except for
numeric and string keys
Integer cast
:
We reinterpret the bits of the
key as an integer
Suitable for keys of length less
than or equal to the number
of bits of the integer type
(e.g., byte, short, int and float
in Java)
Component sum
:
We partition the bits of
the key into components
of fixed length (e.g., 16 or
32 bits) and we sum the
components (ignoring
overflows)
Suitable for numeric keys
of fixed length greater
than or equal to the
number of bits of the
integer type (e.g., long
and double in Java)
Dictionaries and Hash Tables
8
Hash Code Maps (cont.)
Polynomial accumulation
:
We partition the bits of the key
into a sequence of components
of fixed length (e.g., 8, 16 or
32 bits)
a
0
a
1
…
a
n
−
1
We evaluate the polynomial
p
(
z
)
=
a
0
+
a
1
z
+
a
2
z
2
+
…
…
+
a
n
−
1
z
n
−
1
at a fixed value
z
, ignoring
overflows
Especially suitable for strings
(e.g., the choice
z
=
33
gives at
most 6 collisions on a set of
50,000 English words)
Polynomial
p
(
z
)
can be
evaluated in
O
(
n
)
time
using Horner’s rule:
The following
polynomials are
successively computed,
each from the previous
one in
O
(1)
time
p
0
(
z
)
=
a
n
−
1
p
i
(
z
)
=
a
n
−
i
−
1
+
zp
i
−
1
(
z
)
(
i
=
1, 2, …,
n
−
1)
We have
p
(
z
)
=
p
n
−
1
(
z
)
Page 5
Dictionaries and Hash Tables
9
Hash Code Maps (cont.)
Cyclic Shift Hash
Codes
:
Instead of multiplying
with some integer we
can cyclically shift bits
Bit shifts are are very
efficient and
implement a
multiplication by 2
n
Comparison of collision
behavior for cyclic shift
variant of polynomial
hash code applied to a
list of just over 25,000
English words (table to
the right)
Shift
Total
Max
0
22739
86
1
10517
21
2
2254
6
3
448
3
4
89
2
5
4
2
6
6
2
7
14
2
8
105
2
15
1082
6
16
8760
9
Dictionaries and Hash Tables
10
Compression Maps
Division
:
h
2
(
y
)
=
y
mod
N
The size
N
of the
hash table is usually
chosen to be a prime
The reason has to do
with number theory
and is beyond the
scope of this course.
Patterns might be
repeated otherwise
Multiply, Add and Divide
(MAD)
:
h
2
(
y
)
=
[
(
ay
+
b
)
mod
p
]
mod
N
a
and
b
are nonnegative
integers randomly chosen
from
the interval
[0,
p
 1],
a
> 0
p
is a prime number with
p > N
Page 6
Dictionaries and Hash Tables
11
Collision Handling
Collisions occur when
different elements are
mapped to the same
cell
Separate chaining
:
let each cell in the table
point to a linked list of
elements that map
there
Chaining is simple,
but requires
additional memory
outside the table
∅
∅
∅
0
1
2
3
4
4512290004
9811010004
0256120001
Dictionaries and Hash Tables
12
Map Methods with Separate
Chaining used for Collisions
Delegate operations to a listbased map at each cell:
Algorithm
get(k):
Output:
The value associated with the key k in the map, or
null
if there is no
entry with key equal to k in the map
return
A[h(k)].get(k)
{delegate the get to the listbased map at A[h(k)]}
Algorithm
put(k,v):
Output:
If there is an existing entry in our map with key equal to k, then we
return its value (replacing it with v); otherwise, we return
null
t = A[h(k)].put(k,v)
{delegate the put to the listbased map at A[h(k)]}
if
t =
null then
{k is a new key
}
n = n + 1
return
t
Algorithm
remove(k):
Output:
The (removed) value associated with key k in the map, or
null
if there
is no entry with key equal to k in the map
t = A[h(k)].remove(k)
{delegate the remove to the listbased map at A[h(k)]}
if
t
≠
null then
{k was found}
n = n  1
return
t
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:
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
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