1.
Linear probing:
Linear probing
is a technique for
resolving hash collisions
of values of
hash functions by
searching hash table sequentially
for a free
location.This is done
by making use
of two values
where one is
starting value and
other is interval
between successive
values.The second value
which is the
same for the all
keys repeatedly adds
to the starting
value until free table
is found or
entire table is
trasversed.In the linear probing
the interval between the
probes will be
fixed usually to l.
|
Where h(x)
is the starting
value
i is the
value added repeatedly
to the starting
value and
n is
the size of the hash table
Example:
Consider the
following keys to be inserted
in the hash table. Let the table
size be 10
and h(x)=x mod
10
16,18,9,36 and 76
·
Initially all the
locations are empty.
[0]
[1] [2] [3] [4] [5] [6] [7] [8]
[9]
|
|
|
|
|
|
|
|
|
|
·
While
inserting 16,18 and
9 there will be
no collisions.
h(x)=x mod 10
h(16)=16 mod 10=6(so insert 16 at the 6th position)
h(18)=18 mod 10=8(so insert 18 at the 8th position)
h(9)=9 mod 10=9(so insert 9 at the 9th position)
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
|
|
|
|
|
|
16
|
|
18
|
9
|
·
While
inserting 36 collision
occurs because the
state of location 6 is
OCCUPIED.
h(36)=36 mod 10=6(collision)
using linear probing the
next free location
will be calculated as,
h(x)=(h(x)+i)% mod n
=(6+1)% mod 10
=7
Therfore,the value
of 36 to be stored
at location 7 which is an
EMPTY location.
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
|
|
|
|
|
|
16
|
36
|
18
|
9
|
Now insert
76 collision occurs
because the state of
location 6 is
OCCUPIED.
h(76)=76 mod 10=6(collision)
using linear
probing the next free location will be
calculated as
h(x)=(h(x)+i)mod n
=(6+1) mod 10
=7(OCCUPIED state
so try next location)
Using linear probing ,the next free
location will be calculated as
h(x)=(h(x)+i)mod n
=(7+1) mod 10
=8(OCCUPIED
state so try next location)
Using linear
probing,next free location will be
calculated as
h(x)=(h(x)+i)mod n
=(9+1)mod 10
=0(EMPTY
state so
insert 76 at 0th
location)
[0] [1] [2] [3] [4] [5] [6] [7] [8]
[9]
|
76
|
|
|
|
|
16
|
36
|
18
|
9
|
Problem with
linear probing:
One major
problem with linear probing is primary clustering.
Primary clustering is a
process in which
a block of
data is formed in the hash table
when collision is resolved.
Example:
Consider
the table size 10
and insert 19,18,39,29,8
h(x)=x mod 10
=19 mod 10=9
=18 mod 10=8
=39
mod 10=9(collision)
=29
mod 10=9(collision)
=8
mod 10=8(collision)
|
39
|
|
29
|
|
8
|
|
|
|
|
|
|
|
|
|
|
|
18
|
|
19
|
From the above
example when further insertion of
39,29 and 8 are made ,it causes
more number of collisions,i.e each one
would probe exactly same partition as its predecessors.This is known as
primary
clustering.Clustering leads to very inefficient operations because it causes
more number of collisions .To estimate clustering each
different key should
probe the table in a
different order.
The
following algorithm denotes
insertion of an item
in the hash table using
linear probing:
Algorithm:
LP-INSERT (key ,p)
1.set i=h(key)
2.set last
=(i+m-1)%m;
3.Repeat
while (i!=last && !empty
(p(i) &&p[i].key!=key)
4.Set i=(i+1)%m;
5.Check
whether empty p[i] or
deleted p[i] then
6.Set
p[i].key=key
7.Set n=n+1
8.Else
write “table overflow
or key already
in table”.
The algorithm
searches an item in the hash
table using linear probing:
Algorithm:LP-SEARCH(k)
1.Set i=h(x),p=0
2.Repeat until P=N
3.Set c=A[i]
4.Check whether
c=NULL then write “key
not found”
5.Else check whether c.key()=k then write “key found”
6.Else
7.Set i=(i+1) mod N
8.Set P=P+1
9.End step 2 loop
Search:
To search
an element in the hash table that uses
linear probing start at h(k) and
probe consecutive location until one of the following occurs .
1.Item is found
2.An empty cell is
found
3.Entire table
has been scanned.
Example:
Perform
the given below
in the given order on an
initially empty hash
table of size
10 using linear probing with
i=1 and the
hash function h(x)=x mod 10.
Insert
(18).insert(26),insert(25),insert(8),find(15),find(48),delete(35),delete(40),find(8),insert(64),insert(47),find(35).
The required probe
sequence are given by are given by h(key)=(h(key)+i)mod10 where
i=1.
Sol: The following
table shows the result of the above operation:
|
OPERATION
|
PROBE
SEQUENCE
|
RESULT
|
|
Insert(8)
|
h(18)=18mod10=8
|
SUCCESS
|
|
Insert(26)
|
h(26)=26mod10=6
|
SUCCESS
|
|
Insert(35)
|
h(35)=35mod10=5
|
SUCCESS
|
|
Insert(8)
|
h(8)=8mod10=8
h(8)=(8+1)mod
10=9
|
COLLISION
SUCCESS
|
|
Find(15)
|
h(15)=15mod10=5
h(15)=(15+1)mod
10=6
h(15)=(16+1)mod
10=7
|
COLLISION
COLLISION
FAIL(bcz
location 7 does not contain 7 it is empty)
|
|
Find(48)
|
h(48)=48mod10=8
h(48)=(48+1)mod
10=9
h(49)=(49+1)mod
10=0
|
COLLISION
COLLISION
FAIL
(bcz location 0 does not contain 48)
|
|
Delete(35)
|
h(35)=35mod10=5
|
SUCCESS
bcz loction 5 contain 35 and the
status is OCCUPIED.The status is changed to deleted but key 35 is not
removed.
|
|
Delete (40)
|
h(40)=40
mod 10=4
|
FAIL bcz
no such key exits in location 4 and status is empty.
|
|
Find(18)
|
h(18)=18
mod 10=8
|
SUCCESS
bcz location 8 contains key 18
|
|
Insert(64)
|
h(64)=64
mod 10=4
|
SUCCESS
|
|
Insert(47)
|
h(47)=47
mod 10=7
|
SUCCESS
|
|
Find(35)
|
h(35)=35
mod 10=5
|
FAIL bcz location 5 contains
35 but it status is DELETED.
|
The following
table shows index
values and their
status.
|
Index
|
status
|
Value
|
|
0
|
E
|
|
|
1
|
E
|
|
|
2
|
E
|
|
|
3
|
E
|
|
|
4
|
O
|
64
|
|
5
|
D
|
35
|
|
6
|
E
|
26
|
|
7
|
O
|
47
|
|
8
|
O
|
18
|
|
9
|
E
|
8
|
|
10
|
E
|
|
|
11
|
E
|
|
|
12
|
E
|
|
--->E EMPTY STATUS
O ---> OCCUPIED STATUS
D ---> DELETED STATUS
2.Quadratic probing:
No comments:
Post a Comment