|
|
|
12 - Hash Tables.pdf
12_-_Hash_Tables.pdf
Showing 1-3 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 1
Dictionaries and Hash Tables
∅
∅
0
1
2
3
4
451-229-0004
981-101-0002
025-612-0001
Dictionaries and Hash Tables
2
Dictionary ADT
The dictionary ADT models a
searchable collection of key-
element items
The main operations of a
dictionary are searching,
inserting, and deleting items
Multiple items with the same key
are allowed
Applications:
address book
credit card authorization
mapping host names (e.g.,
cs16.net) to internet addresses
(e.g., 128.148.34.101)
Dictionary ADT methods:
get
(k): if the dictionary has
an item with key k, returns
the position of this element,
else, returns a null position.
put
(k, o): inserts item (k, o)
into the dictionary
remove
(k): if the dictionary
has an item with key k,
removes it from the dictionary
and returns its element.
An
error occurs if there is no
such element.
size
(),
isEmpty
()
keySet
(),
entrySet
()
Page 2
Dictionaries and Hash Tables
3
Log File
A log file is a dictionary implemented by means of an unsorted
sequence
We store the items of the dictionary in a sequence (based on a
doubly-linked lists or a circular array), in arbitrary order
Performance:
put
takes
O
(1)
time since we can insert the new item at the
beginning or at the end of the sequence
get
and
remove
take
O
(
n
)
time since in the worst case (the item is
not found) we traverse the entire sequence to look for an item with
the given key
The log file is effective only for dictionaries of small size or for
dictionaries on which insertions are the most common
operations, while searches and removals are rarely performed
(e.g., historical record of logins to a workstation)
Dictionaries and Hash Tables
4
Hash Functions and
Hash Tables
A
hash function
h
maps keys of a given type to integers
in a fixed interval
[0,
N
−
1]
Example:
h
(
x
)
=
x
mod
N
is a hash function for integer keys
The integer
h
(
x
)
is called the
hash value
of key
x
A
hash table
for a given key type consists of
Hash function
h
Array (called table) of size
N
When implementing a dictionary with a hash table, the
goal is to store item
(
k
,
o
)
at index
i
=
h
(
k
)
Page 3
Dictionaries and Hash Tables
5
Example
We design a hash table for a
dictionary storing items
(SSN, Name), where SSN
(social security number) is a
ten-digit positive integer
Our hash table uses an array
of size
N
=
10,000
and the
hash function
h
(
x
)
=
last four digits of
x
∅
∅
∅
∅
0
1
2
3
4
9997
9998
9999
…
451-229-0004
981-101-0002
200-751-9998
025-612-0001
Dictionaries and Hash Tables
6
Hash Functions
A hash function is usually
specified as the
composition of two
functions:
Hash code map
:
h
1
:
keys
→
integers
Compression map
:
h
2
: integers
→
[0,
N
−
1]
The hash code map is
applied first, and the
compression map is
applied next on the
result, i.e.,
h
(
x
) =
h
2
(
h
1
(
x
))
The goal of the hash
function is to
“disperse” the keys in
an apparently random
way
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
