Transcript Data structure

MINISTRY OF EDUCATION & HIGHER EDUCATION
COLLEGE OF SCIENCE AND TECHNOLOGY
KHANYOUNIS- PALESTINE
DATA STRUCTURE
Information Technology , 3’rd Semester
Using C#
Lecture 17:
An Overview of Hashing
Presented By: Mahmoud Rafeek Alfarra
Outline
What is Hashing?
 What is Hash tables?
 What is a hash function?
 Example: hash function using string
 Emank X Mezank !!

What is Hashing?
3




Hashing is a very common technique for
storing data in such a way the data can be
inserted and retrieved very quickly.
Hashing uses a data structure called a hash
table.
Hash tables, sometimes also called dictionaries.
HTs are data structures that store values
along with identification keys for easy
access.
Presented & Prepared by: Mahmoud R. Alfarra
What is Hash tables?
4



Hash tables, sometimes also called dictionaries.
HTs are data structures that store values along
with identification keys for easy access.
A hash table data structure is designed around
an array.
Presented & Prepared by: Mahmoud R. Alfarra
What is Hash tables?
5
Keys
Given a student ID find the record (entry)
Presented & Prepared by: Mahmoud R. Alfarra
What is Hash tables?
6
Each data item is stored in the array based on
some piece of the data, called the key.
To store an element in the hash table, the key
is mapped into a number in the range of 0 to
the hash table size using a function called a
hash function.
Presented & Prepared by: Mahmoud R. Alfarra
What is a hash function?
7
 The ideal goal of the hash function is to store each
key in its own cell in the array.
 However, because there are an unlimited number
of possible keys and a finite number of array cells,
a more realistic goal of the hash function is to
attempt to distribute the keys as evenly as possible
among the cells of the array.
Presented & Prepared by: Mahmoud R. Alfarra
What is a hash function?
8
 Choosing a hash function depends on the data
type of the key you are using.
 If your key is an integer, the simplest function is to
return the key modulo the size of the array.
f(k) = k%size
f(4) = 4%10 = 4
Presented & Prepared by: Mahmoud R. Alfarra
What is a hash function?
9
 A hash table supports
 fast retrieval O(1)
 fast deletion O(1)
 fast insertion O(1)
Presented & Prepared by: Mahmoud R. Alfarra
Hash method works something like this
Convert a String key into an integer that will be in the
range of 0 through the maximum capacity-1
Assume the array capacity is 9997
hash(key)
AAAAAAAA
zzzzzzzz
hash(key)
Domain: "!" .. "zzzzzzzz"
8482
1273
Range: 0 ... 9996
Hash method
What if the ASCII value of individual chars of the string
key added up to a number from ("A") 65 to possibly
488 ("zzzz") 4 chars max
 If the array has size = 309, mod the sum

390 % TABLE_SIZE = 81
394 % TABLE_SIZE = 85
404 % TABLE_SIZE = 95

These array indices store these keys
81
85
95
abba
abcd
able
Example: hash function using string
12
 Could use String keys each ASCII character equals
some unique integer
 "able" = 97 + 98 + 108 + 101 == 404
Presented & Prepared by: Mahmoud R. Alfarra
A hash table after three insertions
using the too simple hash code method
insert
objects with
these three
keys:
"abba"
"abcd"
"abce"
0
...
80
81
82
83
84
85
86
...
308
Keys
"abba"
"abcd"
"abce"
Collision occurs while inserting "baab"
can't insert
"baab" where
it hashes to
same slot as
"abba"
Linear probe
forward by 1,
inserting it
at the next
available slot
0
...
80
81
82
83
84
85
86
...
308
"abba"
"baab"
"abcd"
"abce"
"baab"
Try [81]
Put in [82]
Wrap around when collision occurs at end
Insert
"KLMP"
"IKLT"
both of
which have
a hash
value of
308
0
...
80
81
82
83
84
85
86
...
308
"IKLT"
"abba"
"baab"
"abcd"
"abce"
"KLMP"
Find object with key "baab
"baab" still
hashes to 81,
but since [81]
does not hold
it, linear probe
to [82]
At this point,
you could
return a
reference to it
or remove it
0
...
80
81
82
83
84
85
86
...
308
"IKLT"
"abba"
"baab"
"abcd"
"abce"
"KLMP"
‫!! ‪Emank X Mezank‬‬
‫قال النبي صلى اهلل عليه وسلم‪:‬‬
‫قولوا ال إله إال اهلل‬
‫تُفلحـوا‬
Next Lecture
Graphs