CONCEPT OF
HASHING
In this technique, data is stored at
the data blocks whose address is
generated by using the hashing
function. The memory location
where these records are stored is
known as data bucket or data
blocks.
Types Of Hashing:
Basic Terms used in Hashing
1. Hash Table
2. Hash Function
3. Bucket
4. Collision
5. Probe
6. Synonym
7. Overflow
Hash Table
. Hash table is a data
structure used for storing
and retrieving data quickly.
. Every entry in the hash
table is made using hash
function
Hash Function
. Hash function is a used to to
place data in hash table
. Similarly hash function is
used retrieve data from hash
table
. Thus the use of hash is to
implement
hash table
Bucket
. The hash function function
H(key) is used map several
dictionary entries in the hash
table
. Each position of the hash table
is called bucket
Collision
. Collision is situation in which
hash function returns the same
address for more than one record
Probe
. Each calculation of an address and
tests for success is known as a probe
Static Hashing
.In the methods of hashing the resulting data bucket
address will be always same
. Hence in this static hashing, the number of data
buckets in memory remains constant throughout. In this
example, we will have five data buckets in the memory
used to store the data.
1.Open Hashing
. When a hash function generates an address at which
data is already stored, then the next bucket will be
allocated to it. This mechanism is called as Linear
Probing.
2.Close Hashing
. When buckets are full, then a new data
bucket is allocated for the same hash result
and is linked after the previous one. This
mechanism is known as Overflow chaining.
Dynamic Hashing
. The dynamic hashing method is used to
overcome the problems of static hashing like
bucket overflow.
.In this method, data buckets grow or shrink as
the records increases or decreases. This method
is also known as Extendable hashing method.
.This method makes hashing dynamic, i.e., it
allows insertion or deletion without resulting in
poor performance
Extendible Hashing
Extendible Hashing is a
dynamic hashing method
wherein directories, and buckets
are used to hash data. It is an
aggressively flexible method in
which the hash function also
experiences dynamic changes.
THANK
YOU
