12 - Hash Tables.pdf-Dictionaries and Ha...
12_-_Hash_Tables.pdf-Dictionaries and Hash Tables ∅ ∅
Showing 4-6 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 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
451-229-0004
981-101-0004
025-612-0001
Dictionaries and Hash Tables
12
Map Methods with Separate
Chaining used for Collisions
Delegate operations to a list-based 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 list-based 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 list-based 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 list-based 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:
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

Students also viewed documents