Project Report on

MATRIX HASHING WITH TWO LEVEL OF

COLLISION RESOLUTION

Submitted By:
KOMARAVALLI RAJESH Roll No. : 20116052
2ndSemester
Electronics and Communication Engineering

National Institute of technology Raipur

Under the guidance of

Prof. Manan Kumar Tiwari National Institute of
Technology, Raipur
 MATRIX HASHING WITH TWO PROBLING,QUADRATIC
LEVEL COLLISION RESOLUTION PROBING,DOUBLE HASING.
Abstract

This is the report for the matrix Introduction

hashing with two level of collision
resolution. Firstly discussing about hashing
A hash function is a function which
is designed to solve the problem of needing
when given a Value, generates an
to efficiently find or store an item in a
address in the table. The example of a
collection .It is a well-known heuristic used
hash function is a book call number.
for indexing and retrieving items from
Each book in the library has a unique
database as it uses a shorter hashed key, for call number.
finding the element, which is more efficient A hash table uses a hash function to
hashing is used to index and retrieve compute an index into an array in
information from a database because it which an element will be inserted or
helps accelerate the process; it is much searched. By using a good hash
easier to find an item using its shorter function, hashing can work well.
hashed key than its original value.. Hash Hashing is a way to store data into
function should be properly designed to some data structure generally Hash
avoid collisions. This paper presents a new Table is used in such a way that the
and innovative technique for collision basic operations on that data i.e. the
resolution based on two-dimensional array. insertion, deletion, and searching can
The proposed strategy followed a unique be performed in O(1) time. Here data
is stored in the form of key-value pairs
way of evaluating and implementing
i.e. for each data you will assign some
algorithms to resolve collisions in hash
key and based on that key the
tables. Analytical modelling and software
insertion, deletion, and searching of
simulations are quantifiable measures for your data will be performed.
the effectiveness of our algorithm. Hash
function is any function that can be used to So, let's dive deeper into the concept
map data of arbitrary size to fixed-size of hashing by learning about the basic
values. The values returned by a hash version of the hash table i.e. Direct
Address Table.
function are called hash values, hash
codes, digests, or simply hashes. The values
are usually used to index a fixed-size table
Hash Table
called a hash table. Use of a hash function
In a Hash Table, to store data we use
to index a hash table is Hash function that takes the data as
called hashing or scatter storage input and based on that data it
addressing. generates some key and we store the
data based on that key.Our data can
be of any form i.e. it can be in integer
or string or some other data type. But
KEYWORDS:HASH-FUNCTION,HASH-
our main aim should be to convert
TABLE,OPEN ADRESSING,LINEAR that data into an integer by doing
some pre-processing and then apply
 some hash function to it and map the case of collision,Probing is performed
result in the hash table. until an empty bucket is found.Once an
empty bucket is found, the key is
inserted.Probing is performed in
Existing hashing techniques and their accordance with the technique used for
disadvantages open addressing.

Using a single Dimensional array will Search Operation-To search any

only provide two directions to move in a particular key,Its hash value is obtained
array which is forward or backwards. using the hash function used.Using the
hash value, that bucket of the hash table is
checked.If the required key is found, the
Open Addressing: key is searched.Otherwise, the subsequent
buckets are checked until the required key
• Unlike separate chaining, all the or an empty bucket is found.The empty
keys are stored inside the hash bucket indicates that the key is not
table. present in the hash table.

• No key is stored outside the hash Delete Operation-The key is first

table. searched and then deleted.After deleting
the key, that particular bucket is marked
as “deleted”.

Linear probing: Linear probing is a

Techniques used for open addressing are- scheme in computer programming for
resolving collisions in hash tables, data
structures for maintaining a collection of
• Linear Probing
key–value pairs and looking up the value
associated with a given key. Linear
• Quadratic Probing probing is a component of open
addressing schemes for using a hash table
to solve the dictionary problem. In the
• Double Hashing dictionary problem, a data structure
should maintain a collection of key–value
Operations in Open Addressing:Insert pairs subject to operations that insert or
Operation: Hash function is used to delete pairs from the collection or that
compute the hash value for a key to be search for the value associated with a
inserted.Hash value is then used as an given key. In open addressing solutions to
index to store the key in the hash table. In this problem, the data structure is an array
T the hash table)whose cells T i when c1i + c2i2) mod Where (as in linear
nonempty each store a single key–value probing) h' is an auxiliary hash function
pair. A hash function is used to map each c1 and c2 ≠0 are auxiliary constants and

key into the cell of T where that key i=0, 1...m-1. The initial position is T [h'
should be stored, typically scrambling the (k)]; later position probed is offset by
keys so that keys with similar values are the amount that depend in a quadratic
not placed near each other in the table. A manner on the probe number i.
hash collision occurs when the hash
function maps a key into a cell that is
already occupied by a different key. Double Hashing:
Linear probing is a strategy for resolving
collisions, by placing the new key into the Double Hashing is one of the best
closest following empty cell. techniques available for open addressing
because the permutations produced have
Time Complexity: Worst time to many of the characteristics of randomly
search an element in linear probing is O chosen permutations.Double hashing
(table size). uses a hash function of the form h (k, i)
= (h1(k) + i h2 (k)) mod m Where h1 and
h2 are auxiliary hash functions and m is
This is because-Even if there is only one the size of the hash table. h1 (k) = k mod
element present and all other elements m or h2 (k) = k mod m'. Here m' is
are deleted.Then, “deleted” markers slightly less than m (say m-1 or m-2).
present in the hash table makes search
the entire table.
There are mainly two methods to handle
collision:
Quadratic Probing:Suppose a record R 1) Separate Chaining
with key k has the hash address H (k) = 2) Open Addressing
h then instead of searching the location In this article, only separate chaining is
with addresses h, h+1, and h+ 2...We discussed. We will be discussing Open
linearly search the locations with addressing in the next post.
addresses h, h+1, h+4,
h+9...h+i2Quadratic Probing uses a hash
function of the form h (k,i) = (h' (k) + Separate Chaining:
The idea is to make each cell of hash
table point to a linked list of records that stored in the same table.
have same hash function value. Let us 2) Wastage of Space (Some Parts of
consider a simple hash function as “key hash table are never used)
mod 7” and sequence of keys as 50, 3) If the chain becomes long, then
700, 76, 85, 92, 73, 101. search time can become O(n) in the
worst case.
4) Uses extra space for links.

Performance of Chaining:
Performance of hashing can be
evaluated under the assumption that
each key is equally likely to be hashed
to any slot of table (simple uniform
hashing). m = Number of slots in hash
table n = Number of keys to be inserted
in hash table Load factor α = n/m
Expected time to search = O(1 + α)
Expected time to delete = O(1 + α) Time
to insert = O(1)Time complexity of
search insert and delete is O(1) if α is
O(1)

Conclusion:As these are the some

techniques discussing about matrix
hashing with two level collision
resolution.discussing that about
hashing,hash function,hash table,with
some hashing techniques of open
addressing and its search,insertion
,delete operations respectively by there
C++ program for hashing with methods of linear probing quadratic
chaining probing and double hashing with there
advantages and disadvantages with
knowing the use of hashing as hashing
Advantages:
is a cryptographic process that can be
1) Simple to implement.
used to validate the authenticity and
2) Hash table never fills up, we can
integrity of various types of input. It is
always add more elements to the chain.
widely used in authentication systems to
3) Less sensitive to the hash function or
avoid storing plaintext passwords in
load factors.
databases, but is also used to validate
4) It is mostly used when it is unknown
files, documents and other types of data.
how many and how frequently keys may
be inserted or deleted.
REFERNCES:
Disadvantages: https://www.csoonline.com/article/3602698/
1) Cache performance of chaining is not hashing-explained-why-its-your-best-bet-to-
good as keys are stored using a linked protect-stored-passwords.html
list. Open addressing provides better
cache performance as everything is
https://www.geeksforgeeks.org/double-
hashing/

https://www.google.com/url?sa=i&url=https
%3A%2F%2Fcourses.cs.washington.edu%2Fco
urses%2Fcse326%2F00wi%2Fhandouts%2Flec
ture16%2Fsld015.htm&psig=AOvVaw3FdspBb
_yA97a8ETtU56De&ust=1630058158686000&
source=images&cd=vfe&ved=0CAwQjhxqFwo
TCNiDnZG2zvICFQAAAAAdAAAAABAP

https://www.tutorialspoint.com/difference-
between-data-type-and-data-structure

https://www.includehelp.com/data-structure-
tutorial/collisions-in-hashing-and-collision-
resolution-techniques.aspx