Transcript notes

CS201: Data Structures and
Discrete Mathematics I
Hash Table
Hashing
• Dictionary: in many tasks, one needs
store a collection of data and find item in it
• An important and widely useful technique
for implementing dictionaries
– Insert, delete, and search
• Constant time per operation (on average)
• Worst case time proportional to the size of
the set for each operation (just like array
and chain/list implementation)
Data collection
• Data collection is a set of records (static
or dynamic)
• Each record consists of two parts
– A key: a unique identifier of the record.
– Data item: it can be arbitrarily complex.
• The key is usually a number, but can be a
string or any other data type.
– Non-numbers are converted to numbers
when applying hashing.
Basic ideas of hashing
• Use hash function to map keys into
positions in a hash table
Ideally
• If data item or element e has key k and h
is hash function, then e is stored in
position h(k) of table
• To search for e, compute h(k) to locate
position. If no element/item, dictionary
does not contain e.
[4]
What is a Hash Table ?
• The simplest kind of
hash table is an array
of records (elements).
• This example array
has 701 cells.
[0]
[1]
[2]
[3]
[4]
[5]
[ 700]
...
An array of cells
Following the example
• We want to store a dictionary of Object
Records, no more than 701 objects
• Keys are Object ID numbers, e.g.,
506643548
• Hash function: h(k) maps k(=ID) into
distinct table positions 0-700
• Operations: insert, delete, and search
Complexity (ideal case)
• Why hashing and hash table?
– It is very efficient.
• O(D) time to initialize hash table (D
number of positions or cells in hash table)
• O(1) time to perform insert, remove,
search
Use the Hash Table
• Each record has a
special field, i.e., its
key.
• In this example, the
key is a long integer
field called Number.
[0]
[1]
[2]
[3]
[4]
[4]
506643548
[4]
[5]
[ 700]
...
Use the Hash Table
• The number is a
object's identification
number, and the rest of
the record has
information about the
object.
[0]
[1]
[2]
[3]
[4]
[4]
[4]
506643548
[5]
[ 700]
...
Use the Hash Table
• When a hash table is in
use, some spots
contain valid records,
and other spots are
"empty".
[0]
[1]
[2]
233667136
[3]
[4]
506643548
[5]
[ 700]
...
155778322
Inserting a New Record
• In order to insert a new
record, the key must
somehow be mapped
to an array index
using a hash function.
• The index is called the
hash value of the key.
[0]
[1]
[2]
233667136
[3]
[4]
506643548
580625685
[5]
[ 700]
...
155778322
Hash functions
• Popular hash functions: hashing by
division
h(k) = k mod D, where D is number of cells in
hash table
• Example: hash table with 701 cells
h(k) = k mod 701
h(80) = 80 mod 701 = 80
h(1000) = 1000 mod 701 = 299
Inserting a New Record
• Let us find the hash value
for 580625685
580625685
What is (580625685 mod 701) ?
[0]
[1]
[2]
233667136
[3]
[4]
506643548
[5]
[ 700]
...
155778322
Inserting a New Record
• Let us find the hash value
for 580625685
580625685
580625685 mod 701 = 3
[0]
[1]
[2]
233667136
[3]
3
[4]
506643548
[5]
[ 700]
...
155778322
Inserting a New Record
The hash value is used to
find the location of the new
record.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
[ 700]
...
155778322
Collisions
• Here is another new
record to insert, with a
hash value of 2.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
701466868
[5]
[ 700]
...
155778322
Collisions
• This is called a collision,
because there is already
another valid record at [2].
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
701466868
[5]
[ 700]
...
155778322
Collision Resolution Policies
• Two strategies:
– (1) Open hashing, a.k.a. separate chaining
– (2) Closed hashing, a.k.a. open addressing
• Difference has to do with whether
collisions are stored outside the table
(open hashing) or whether collisions
result in storing one of the records at
another slot in the table (closed hashing)
Closed hashing
• Associated with closed hashing is a rehash
strategy:
“If we try to place x in cell h(x) and find it
occupied, find alternative location h1(x), h2(x),
etc. Try each in order. If none empty, table is
full,”
• h(x) is called home cell
• Simplest rehash strategy is called linear hashing
hi(x) = (h(x) + i) mod D
Collisions: closed hashing
• Collision, there is already
another valid record at [2].
701466868
When a collision
occurs,
move forward until we
find an empty spot.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
[ 700]
...
155778322
Collisions: closed hashing
• Collision, there is already
another valid record at [2].
701466868
When a collision
occurs,
move forward until we
find an empty spot.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
[ 700]
...
155778322
Collisions: closed hashing
• Collision, there is already
another valid record at [2].
701466868
When a collision
occurs,
move forward until we
find an empty spot.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
[ 700]
...
155778322
Collisions: closed hashing
• Collision, there is already
another valid record at [2].
The new record goes
in the empty spot.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
701466868
[ 700]
...
155778322
Searching for a Key
• The data that's attached to
a key can be found fairly
quickly.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
701466868
[5]
701466868
[ 700]
...
155778322
Searching for a Key
• Calculate the hash value.
• Check that location of the
array for the key.
701466868
The hash value of
701466868 is 2
Not me.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
701466868
[ 700]
...
155778322
Searching for a Key
• Keep moving forward until
you find the key, or you
reach an empty spot.
701466868
The hash value of
701466868 is 2
Not me.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
701466868
[ 700]
...
155778322
Searching for a Key
• Keep moving forward until
you find the key, or you
reach an empty spot.
701466868
The hash value of
701466868 is 2
Not me.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
701466868
[ 700]
...
155778322
Searching for a Key
• Keep moving forward until
you find the key, or you
reach an empty spot.
701466868
The hash value of
701466868 is 2
Yes.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
701466868
[ 700]
...
155778322
Searching for a Key
• When the item is found,
the information can be
copied to the necessary
location.
701466868
The hash value of
701466868 is 2
Yes.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
701466868
[ 700]
...
155778322
Deleting a Record
• Records may also be
deleted from a hash table.
Please
delete me.
[0]
[1]
[2]
[3]
[4]
233667136
580625685
506643548
[5]
[ 700]
701466868
155778322
Deleting a Record
• Records may also be deleted from a
hash table.
• But the location must not be left as an
ordinary "empty spot" since that could
interfere with searches.
[0]
[1]
[2]
[3]
233667136
580625685
[4]
[5]
[ 700]
701466868
155778322
Deleting a Record
• Records may also be deleted from a hash
table.
• But the location must not be left as an ordinary
"empty spot" since that could interfere with
searches.
• The location must be marked in some special
way so that a search can tell that the spot
used to have something in it.
[0]
[1]
[2]
[3]
233667136
580625685
[4]
[5]
[ 700]
701466868
155778322
Open hashing
• Each cell in the hash table is the head of
a linked list
• All records or elements that hash to a
particular cell are placed on that cell’s
linked list
• Records within a cell can be ordered in
several ways
– by order of insertion, by key value order, or
by frequency of access order
Open hashing: same example
[0]
[1]
233667136
[2]
580625685
[3]
[4]
506643548
[5]
….
155778322
[ 700]
701466868
Summary
• Hash tables store a collection of records
with keys.
• The location of a record depends on the
hash value of the record's key.
• When a collision occurs, use a collision
resolution strategy to deal with it.
• Hash table is a very efficient way to store
and to search for data