exercises in c language. I need a person who know c language
mr.su
Chapter30.pdf
CHAPTER - 30
HASHING
CHAPTER 30
HASHING OVERVIEW (Reading)
HASHTABLE (Reading)
HASH PROCESS
HASH TABLE AND COLLISION
HASH FUNCTION
CHOOSING A HASH FUNCTION
HASH COLLISION
COLLISION RESOLUTION BY OPEN ADDRESSING
COLLISION RESOLUTION BY SEPARATE CHAIN
ADVANTAGES AND DISADVANGES OF CHAINING
HASHING IN EXTERNAL STORAGE
DYNAMIC EXTENDIBLE HASHING
DYNAMIC HASHING
EXTENDIBLE HASHING (Reading)
DRAWBACKS OF DYNAMIC HASHING AND
EXTENDIBLE HASHING (Reading)
HASHING
HASH PROCESS
HASHING
HASH TABLE AND COLLISION Hash Collision
HASHING
HASH FUNCTION • Hashing is best suitable for small number
of records and the expected key type is
known. For best results, hashing needs to
be used for in memory applications where
the records from a lookup table searching
another main table.
• A perfect hash function is a hash function h
such that h(ki) != h(kj) for all distinct i and
j. That is, no clashes occur under a perfect
hash function.
• In general, it is difficult to find a perfect
hash function for a particular set of keys.
Further, once a few more keys are added to
the set for which perfect hash function has
been found, the hash function generally
ceases to be perfect for the expanded set.
• A function that transforms a key into a table index
is called a hash function. If h is a hash function and
key is a key, h(key) is called hash of key and its
index at which a record with the key key should be
placed. If r is a record whose key hashes into hr, hr
is called hash key of r. The values that h produces
should cover the entire set of indices in the table.
• The hash function will generally map several
different keys to the same index. If the desired
record is in the location given by the index, then the
problem is solved; otherwise a method must be
used to resolve to overcome this problem.
• We must find a good hash function that takes a key
and finds a unique location for the index. Selection
of a proper key helps to some extent but there is
always a possibility that the key can map to the
same location where already another key was
mapped.
• The best selected hash function for one situation or
one key may not be suitable for another situation
or another key. There is no best hash function for
all situations or all types of keys. Hash functions
can be selected by trials with a variety of keys for a
particular situation.
HASHING
HASH FUNCTION • Hashing is best suitable for small number
of records and the expected key type is
known. For best results, hashing needs to
be used for in memory applications where
the records from a lookup table searching
another main table.
• A perfect hash function is a hash function h
such that h(ki) != h(kj) for all distinct i and
j. That is, no clashes occur under a perfect
hash function.
• In general, it is difficult to find a perfect
hash function for a particular set of keys.
Further, once a few more keys are added to
the set for which perfect hash function has
been found, the hash function generally
ceases to be perfect for the expanded set.
• A function that transforms a key into a table index
is called a hash function. If h is a hash function and
key is a key, h(key) is called hash of key and its
index at which a record with the key key should be
placed. If r is a record whose key hashes into hr, hr
is called hash key of r. The values that h produces
should cover the entire set of indices in the table.
• The hash function will generally map several
different keys to the same index. If the desired
record is in the location given by the index, then the
problem is solved; otherwise a method must be
used to resolve to overcome this problem.
• We must find a good hash function that takes a key
and finds a unique location for the index. Selection
of a proper key helps to some extent but there is
always a possibility that the key can map to the
same location where already another key was
mapped.
• The best selected hash function for one situation or
one key may not be suitable for another situation
or another key. There is no best hash function for
all situations or all types of keys. Hash functions
can be selected by trials with a variety of keys for a
particular situation.
HASHING
HASH FUNCTION • Hashing is best suitable for small number
of records and the expected key type is
known. For best results, hashing needs to
be used for in memory applications where
the records from a lookup table searching
another main table.
• A perfect hash function is a hash function h
such that h(ki) != h(kj) for all distinct i and
j. That is, no clashes occur under a perfect
hash function.
• In general, it is difficult to find a perfect
hash function for a particular set of keys.
Further, once a few more keys are added to
the set for which perfect hash function has
been found, the hash function generally
ceases to be perfect for the expanded set.
• A function that transforms a key into a table index
is called a hash function. If h is a hash function and
key is a key, h(key) is called hash of key and its
index at which a record with the key key should be
placed. If r is a record whose key hashes into hr, hr
is called hash key of r. The values that h produces
should cover the entire set of indices in the table.
• The hash function will generally map several
different keys to the same index. If the desired
record is in the location given by the index, then the
problem is solved; otherwise a method must be
used to resolve to overcome this problem.
• We must find a good hash function that takes a key
and finds a unique location for the index. Selection
of a proper key helps to some extent but there is
always a possibility that the key can map to the
same location where already another key was
mapped.
• The best selected hash function for one situation or
one key may not be suitable for another situation
or another key. There is no best hash function for
all situations or all types of keys. Hash functions
can be selected by trials with a variety of keys for a
particular situation.
HASHING
1. Truncation: Truncation ignores a part of the key and
uses remaining part directly as the index. Truncation
is a very fast method, but it often fails to distribute
the keys evenly through the table.
2. Folding: The key is partitioned into several parts and
combines the parts in a convenient way to obtain the
index. Since all the information in the key can affect
the value of the function, folding often achieves a
better spread of indices than done by truncation
itself.
3. Modular Arithmetic: The key itself is converted to an
integer and divided by the size of the index range.
The remainder is taken as the result. This amounts to
using the C modulus operator %. The spread
achieved by taking a remainder depends very much
on the modulus. If the modulus is a power of a small
integer like 2 or 10, then many keys tend to map to
the same index, while other indices remain unused.
The best choice for modulus is often, but not always, a
prime number, which usually has the effect of
spreading the keys quite uniformly
CHOOSING A HASH FUNCTION
4. C Programs: C programs can
be formulated many ways
suitable to the size of the hash
table and the type of key used
for hashing.
typedef char *Key;
#define HASHSIZE …
int hashfunc (Key s)
{
unsigned h = 0;
while (*s)
h += *s++;
return (h % HASHSIZE);
} /* end of hashfunc */
HASHING
HASH COLLISION
• The population of keys for a hashed list is greater
than the storage area used to store the data.
Because there are many keys for each index
location in the list, there is possibility that more
than one key will hash to same location in the list.
• The set of keys that hash to the same location in
the list are called synonyms. If the actual data that
will be inserted into the list contains two or more
synonyms, there will be collisions.
• A collision is the event that occurs when a hashing
algorithm produces an address for an insertion
and that address is already occupied. The address
produced by the hashing algorithm is known as the
home address. The memory that contains all of the
home addresses is known as the prime area. When
two keys collide at a home address, the collision
needs to be resolved by placing one of the keys and
its data in another location. The collision resolution
algorithm has to determine the next location and
continue until the element is found or determine
that it is not in the list. Each calculation of an
address and test for success is known as a probe.
• There are several methods for handling
collisions, each of them independent of the
hashing algorithm. Because of the nature of
hashing algorithms, it is necessary to have some
empty elements in a list at all times. A full list is a
list in which all elements except one contains
data.
• As a rule of thumb, a hashed list should not be
allowed more than 75% full. The load factor of a
hashed list is the number of elements in the list
divided by the number of physical elements
allocated for the list expressed as a percentage.
• Suppose two keys k1 and k2 are such that h(k1)
equals h(k2). When a record with key k1 is
entered into the table, it is inserted at position
h(k1).
• But when k2 is hashed, because its hash key is
the same as that of k1, an attempt may be made
to insert the record into the same position where
the record with key k1 is stored. Clearly, two
records cannot occupy the same position. Such a
situation is called a hash collision..
HASHING COLLISION RESOLUTION BY OPEN ADDRESSING
Clustering:
As data are added to a list and collisions are
resolved, some hashing algorithms tend to
cause data to group within the list. This
tendency of data to build up unevenly across
a hashed list is known as clustering.
Clustering is a concern because it is usually
created by collisions. If the list contains a
high degree of clustering, then the number of
probes to locate an element grows and the
processing efficiency of the list is reduced.
Primary clustering occurs when data become
clustered around home address. Secondary
clustering occurs when data become grouped
along a collision path throughout the list. In
secondary clustering, the data are widely
distributed across the whole list so that the
list appears to be well distributed. If the data
all lie along a well traveled collision path,
however, the time to locate a requested
element of data can become large. Hashing
algorithms must be designed to minimize
clustering.
Open Addressing:
Open addressing resolves collisions in the home area.
When a collision occurs, the home area addresses
are searched for an open or unoccupied elements
where the new data can be placed. The search for
an unoccupied location will continue depending on
the way described by the collision resolution
algorithm. Most of the open addressing methods
suffer from the difficulty of deleting an entry form
the list. Open addressing methods of collision
resolution are quite simple and easy to implement.
Linear Probing:
The simplest method to resolve a collision is to start with
the hash address and do a sequential search
through the table for the desired key or an empty
location. The table should be a circular list to
search throughout the list for any starting address.
The major drawback of linear probing is that, as
the table becomes about half full, there is a
tendency towards clustering. Linear probes are
quite simple to implement and the data tend to
remain near the home address.
HASHING
COLLISION RESOLUTION BY OPEN ADDRESSING Quadratic Probing:
If there is a collision at hash address h, this
method probes the table at locations h + 1,
h + 4, h + 9, ….., that is, at h + i^2
(%HASHSIZE) for i = 1, 2, … That is, the
increment function is i^2. Quadratic
probing substantially reduces clustering,
but it is not obvious that it will probe all
locations in the table, and in fact it does
not. Primary clustering, although not
secondary clustering, can be eliminated
by adding value other than one to the
current address.
Key dependent increments:
Rather than having the increment depends on
the number of probes already made, it
can be some simple function of the key
itself.
increment = *key;
In this method, the increment, once
determined, remains constant.
Random Probing:
This method uses a pseudorandom number generator to obtain
the increment. The generator used should be one that
always generates the same sequence provided it starts
with the same seed. This method is excellent in avoiding
clustering but is likely to be slower than the others.
Rehashing:
Rehashing involves using a secondary hash function on the
hash key of the item. The rehash function is applied
successively until an empty position is found where the
item can be inserted. If the hash position of the item found
to be occupied during a search, the rehash function is
again used to locate the item. Once a record has been
inserted, another record that hashes to the same location
is inserted at the next available position.
In general, a rehash function, rh, accepts one array index and
produces another. If array location h(key) is already
occupied by a record with a different key, rh is applied to
the value of h(key) to find another location where the
record may be placed. If position rh(h(key)) is also
occupied, it too is rehashed to see if rh(rh(h(key))) is
available. This process continues until an empty location
is found.
HASHING COLLISION RESOLUTION BY OPEN ADDRESSING
#define TABLESIZE ….
typedef KEYTYPE …
typedef RECTYPE …
struct record {
KEYTYPE k;
RECTYPE r;
} table [TABLESIZE];
int search (KEYTYPE key, RECTYPE rec)
{
int i;
i = h(key); /* hash the key */
while (table[i].k != key && table[i].key !=
nullkey)
i = rh(i); /* rehash */
if (table[i].k == nullkey)
{
// insert the record into the empty position
table[i].k = key;
table[i].r = rec;
} /* end if */
} /* end search */
• It is difficult to delete items from a hash table
that uses rehashing for search and insertion.
Suppose that a record r1 is at position p.
• To add a record r2 whose key k2 hashes into p,
it must be inserted into the first free position
from among rh(p), rh(rh(p)), …/. Suppose that
r1 is then deleted, so that position p becomes
empty.
• A subsequent search for record r2 begins at
position h(k2), which is p. But since that
position is now empty, the search process may
erroneously conclude that record r2 is absent
from the table.
HASHING
COLLISION RESOLUTION BY SEPARATE CHAINING • If the number of records grows beyond the
number of table positions, it is impossible to
insert them without allocating a larger table and
recomputing the hash values of the keys of all
records already in the table using a new hash
function. To avoid the possibility of running out
of room, too many locations may be initially
allocated for a hash table, resulting in much
wasted space.
• Another method of resolving hash clashes is
called separate chaining. This technique involves
adding an extra link field to each table position.
• Separate chaining involves keeping a distinct
linked list for all records whose keys hash into a
particular value. Suppose that the hash routine
produces values between 0 and tablesize – 1.
Then an array bucket of header nodes of size
tablesize is declared . This array is called the
hash table. bucket[i] points to the list of all
records whose keys hash into i. In searching for a
record, the list head bucket[i] is accessed and the
list that it initiates is traversed. If the record is
not found, it is inserted at the end of the list.
struct nodetype * search (KEYTYPE key, RECTYPE rec)
{
struct nodetype *p, *q, *s;
i = h(key);
q = NULL;
p = bucket[i];
while ( p != NULL && p->k != key)
{
q = p;
p = p->next;
} /* end of while */
if (p != NULL && p->k == key)
return (p);
/* insert a new record */
s = getnode();
s->k = key;
s->r = rec;
s->next = NULL;
if (q == NULL)
bucket[i] = s;
else
q->next = s;
return (s);
} /* end of search */
HASHING COLLISION RESOLUTION BY SEPARATE CHAINING
HASHING ADVANTAGES AND DISADVANTAGES OF CHAINING Advantages:
• When the records themselves are quite large,
considerable space may be saved.
• Since the hash table is a contiguous array,
enough space must be set aside at compilation
time to avoid overflow.
• If the records themselves are in the hash table,
then if there are many empty positions, these
will consume considerable space that might be
needed elsewhere.
• Keeping only pointers in the hash table is that
it allows simple and efficient collision
handling.
• Only a link field needs to be added to each
record, and organize all the records with a
single hash address as a linked list.
• With a good hash function, few keys will give
the same hash address, so the linked lists will
be short and can be searched quickly.
• Clustering is no problem at all, because keys
with distinct hash addresses always go to
distinct lists.
• It is no longer necessary that the size of the
hash table exceed the number of records.
• If there are more records than entries in the
table, it means only that some of the linked
lists are now sure to contain more than one
record.
• Deletion becomes a quick and easy task in a
chained hash table.
• Separate chaining allows traversal of the items
in hash-key order, although not in sequential
key order. The list items need not be in
contiguous storage.
Disadvantages:
• All links require space. If the lists get longer
due to poor hash function and in conjunction
with clustering, this becomes many searches of
linear linked lists.
• The search order becomes 0(n) for each list
through the hash table. The advantage gained
through hash table would be lost.
*/
HASHING HASHING IN EXTERNAL STORAGE
• If hash table is maintained in external
storage on a disk or some other direct
access device, time rather than space is the
critical factor.
• Most systems have sufficient external
storage for growth but cannot afford the
time needed to perform an I/O operation
for every element on linked list.
• In such a situation the table in external
storage is divided into a number of blocks
called buckets.
• Each bucket consists of a useful segment of
external storage such as a page or a disk
track or track fraction.
• The buckets are usually contiguous and can
be accessed by bucket offsets from 0 to
tablesize – 1 that serve as hash values, like
indexes of an array.
• One or more contiguous storage blocks
can be used as a hash table-containing
pointer to buckets distributed not
contiguously.
• In that situation the hash table is most
likely read into memory as soon as the
file is opened and remains in memory
until the file is closed.
• When a record is requested, its key is
hashed and the hash table known as
index is used to locate the external
storage address of the appropriate
bucket.
HASHING DYNAMIC AND EXTENDIBLE HASHING
• One of the most serious drawbacks of
hashing for external storage is that it
insufficiently flexible. Unlike internal data
structures, files and databases are semi
permanent structures that are not usually
created and destroyed within the lifetime of a
single program. The contents of an external
storage structure tend to grow and shrink
unpredictably.
• Dynamic hashing and extendible hashing do
not utilize too much extra space when a file is
small but permits efficient access when it
grows larger. The basic concept under both
methods is the same. Initially, m buckets and
a hash table of size m are allocated. Assume
that m equals 2**b, and assume a hash
routine h that produces hash values that are
w > b bits in length. Let hb(key) be the
integer between 0 and m represented by the
first b bits of h(key). Then, initially, hb is
used as the hash routine, and records are
inserted into m buckets as in ordinary
external storage.
• When bucket overflows, the bucket is split in two
and its records are assigned to the two new
buckets based on the (b + 1)st bit of h(key). If the
bit is 0, the record is assigned to the first new
bucket, if the bit is 1, the record is assigned to the
second bucket. The records in each of the two
new buckets all have the same first b + 1 bits in
their hash keys, h(key). Dynamic hashing and
extendible hashing differ as to how the index is
modified when a bucket splits.
• Under dynamic hashing, each of the m original
index entries represents the root of a binary tree
each of whose leaves contains a pointer to a
bucket. Initially each tree consists of only one
node that point to one of the m initially allocated
buckets. When a bucket splits, two new leaf
nodes are created to point to the two new
buckets. The former leaf that had pointed to the
bucket being split is transformed into a non-leaf
node whose left child is the leaf pointing to the 0-
bucket and whose right child is the leaf pointing
to the 1-bucket.
HASHING DYNAMIC HASHING
• To locate a record under dynamic
hashing, compute h(key) and use the
first b bits to locate a root node in the
original index. Then use each
successive bit of h(key) is used to move
down the tree, going left it the bit is 0
and right if the bit is 1, until a leaf is
reached. Then use the pointer in the
leaf to locate the bucket that contains
the desired record, it exists.
• In extendible hashing, each bucket
contains an indication of the number
of bits of h(key) that determine which
records are in that bucket. This
number is called the bucket depth.
Initially, this number is b for all
bucket entries; it is increased by 1
each time a bucket splits. Associated
with the index is the index depth, d,
which is the maximum of all the
bucket depths. The size of the index is
always 2**d.
HASHING EXTENDIBLE HASHING
Drawbacks of dynamic and extendible
hashing:
• One drawback of dynamic and
extendible hashing is the need for
index. Although the index may be
kept in internal storage once the file
is opened, this is not always possible
if the index becomes very large.
• Also, the index does require external
storage when the file is not in use. In
addition, the external copy of the
index may have to be constantly
updated to guard against power
failure or other interruption that
would prevent rewriting the index
when the file is closed.
