DEV Community: Bhavana

Hashing

Bhavana — Mon, 25 Oct 2021 05:23:58 +0000

DEFINITION:
A hash table is a special collection that is used to store key-value items. So
instead of storing just one value like the stack, array list and queue, the
hash table stores 2 values. These 2 values form an element of the hash
table.

Do C have a built in hash table:
In C we only have indexed arrays to work with. Thus to make a hash table
we will need to retrieve data with functions that use indexed arrays.

*HASHING:
Hashing is an efficient method to store and retrieve elements.
It’s exactly same as index page of a book. In index page, every topic is
associated with a page number. If we want to look some topic, we can
directly get the page number from the index.

How to calculate the hash key? Let’s take hash table size as 7.
size = 7 arr[size];
Formula:
key = element % size

*INITIALIZATION OF THE HASH BUCKET
Before inserting elements into array. Let’s make array default value as -1.
-1 indicates element not present or the particular index is available to
insert.

*INSERTING ELEMENTS

INSERTED 24

INSERTED 8

*What if we insert an element say 15 to existing hash table?
Insert : 15
Key = element % key
Key = 15 % 7
Key = 1
But already arr[1] has element 8 !
Here, two or more different elements pointing to the same index under
modulo size. This is called collision.

*IMPLEMENTATION OF HASH PROGRAM
Create an array of structure, data (i.e a hash table).
Take a key to be stored in hash table as input.
Corresponding to the key, an index will be generated.
*BASIC OPERATION OF A HASH TABLE
searches ,inserts and deletes an element from the hash table

*USES:
to compute an index ,also called hash code ,into an array of buckets or
slots from which the desired location can be found
*ADVANTAGES:
Synchronization
In many situations, hash tables turn out to be more efficient than search
trees or any other table lookup structure. For this reason, they are widely
used in many kinds of computer software's, particularly for associative
arrays, database indexing, caches and sets.

*DISADVANTAGES:
Hash collisions Hash tables becomes quite in efficient when there are
many collisions Hash tables does not all

ALGORITHM of Infix to Postfix Conversion Using Stack.

Bhavana — Thu, 06 May 2021 11:52:11 +0000

Postfix expression: The expression of a b op. when an operator is followed for every pair of operands.

Infix expression: The expression of the from a op b. when an operator is in between every pair of operands

ALGORITHM

step1: First we should scan the infix expression from left to right

step2: If scanned character is an operand ,we should get the output.

step3:Else,pop all the operators in the stack which are greater than or equal to in precedence than that of the scanned operator to the stack

step4: If the scanned character is an ’ ( ', push it to the stack.

step5 : If the scanned character is an ‘)’,pop the stack an output it until it is encountered, and discard both the parenthesis.

step 6: Repeat steps 2-6 until infix expression is scanned.

step7: print the output

step 8: pop and output from the stack until it is not empty

BACKTRACKING

Bhavana — Thu, 06 May 2021 11:41:55 +0000

Many problems which deal with searching for a set of solutions or for a optimal solution satisfying some constraints can be solved using the backtracking formulation.

To apply backtracking method, the desired solution must be expressible as an n-tuple (X1…Xn) where Xi is chosen from some finite set Si.

Often the problem to be solved calls for finding one vector that maximizes (or minimizes or satisfies) a criteria function P(X1,X2, --- Xn). Sometimes it seeks all vectors that satisfy P.

Suppose mi is the size of set Si. Then the number of n-tuples may satisfy the criteria function P(x1,x2,---,xn) are m=m1,m2,---mn. The brute force approach would be to form all these n-tuples, evaluates each one with P, and save those which yield the optimum and save those which yield optimum.

In backtracking we will get the same answer but fewer than m trials. Its basic idea is to build up the solution vector one component at a time and to use modified criteria function P(x1,x2, ---xi) (sometimes called bounding functions) to test whether the vector being formed has any chance of success.

The major advantage of this method is if it is realized that the partial vector (x1,x2,---xi) can no way lead to an optimal solution, then mi+1….mn possible test vectors can be ignored entirely.

Many problems solved using backtracking require that all the solutions satisfy a complex set of constraints. These constraints are classified as
1.Explicit constraints
2.Implicit constraints