Hash And Binary

Hash And Binary


Hashing


Hashing is a technique used for storing and retrieving keys in a rapid manner.In hashing, a string of characters are transformed into a usually shorter length value or key that represents the original string.Hashing is used to index and retrieve items in a database because it is faster to find item using shorter hashed key than to find it using the original value.Hashing can also be defined as a concept of distributing keys in an array called a hash table using a predetermined function called hash function.


Hash Table


Hash table  is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.

Example:

Supposed we want to store 5 string: define, float, exp, char, atan into a hash table with size 26. The hash function we will use is “transform the first character of each string into a number between 0..25”
(a will be 0, b will be 1, c will be 2, …, z will be 25).
There are many ways to hash a string into a key. The following are some of the important methods for constructing hash functions.
•Mid-square
Mid-Square hashing is a hashing technique in which unique keys are generated. In this technique, a seed value is taken and it is squared. Then, some digits from the middle are extracted. These extracted digits form a number which is taken as the new seed. This technique can generate keys with high randomness if a big enough seed value is taken.
Hash Function

Example:
Suppose a 4-digit seed is taken. seed = 4765
Hence, square of seed is = 4765 * 4765 = 22705225
Now, from this 8-digit number, any four digits are extracted (Say, the middle four).
So, the new seed value becomes seed = 7052
Now, square of this new seed is = 7052 * 7052 = 49730704
Again, the same set of 4-digits is extracted.
So, the new seed value becomes seed = 7307

•Division (most common)
Divide the string/identifier by using the modulus operator.
Example:
"COBB” would be stored at the location ( 64+3 + 64+15 + 64+2 + 64+2) % 97 = 88

•Folding
Partition the string/identifier into several parts, then add the parts together to obtain the hash key
Example:
Key:4578
Parts: 45 and 78
Sum:123
Hash Value:23

•Digit Extraction
A predefined digit of the given number is considered as the hash address. 
Example:
X=15,678
Hash Code=168

•Rotating Hash
Use any hash method (such as division or mid-square method)
After getting the hash code/address from the hash method, do rotation
Rotation is performed by shifting the digits to get a new hash address

Example:
–Given hash address = 56890
–Rotation result: 09865(fold the digits)


Collision

The situation where there are several srings use the same hash key
 
Two general ways to handle this problem:
-Linear Probing:
Search the next empty slot and put the string there. 
Linear probing has a bad search complexity if there are many collisions.

-Chaining:
Put the string in a slot as a chained list (linked list).
In chaining, we store each string in a chain (linked list). So if there is collision, we only
need to iterate on that chain.

Tree

Tree is a non linear data structures that represents the hierarchical relationships among the data        object .The node in the tree need no to be stored contiguously and can be stored anywhere and linked by pointers.

Tree Concept

-Tree is a collection of one or more nodes
-Node at the top is called a root 
-A line connecting the parent to the child is edge.
-Nodes that do not have children are called leaf.
-Nodes that have the same parent are called sibling.
-Degree of node is the total sub tree of the node.
-Height/Depth is the maximum degree of nodes in a tree.
-If there is a line that connects a to b, then a is called the ancestor of b, and b is a descendant of a.


Binary Tree Concept

Binary tree is a rooted tree that contain maximum of two children(left child and right child)

Type Of Binary Tree

-Perfect Binary Tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level. 

-Complete Binary Tree is  a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A perfect binary tree is a complete binary tree.

-Skewed Binary Tree is a binary tree in which each node has at most one child.

-Balance Binary Tree is a binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.[One may also consider binary trees where no leaf is much farther away from the root than any other leaf.

Threaded Binary Tree Concept

-Threaded Binary Tree is same as the binary tree,the difference between them is in storing of NULL pointers 
-In the linked representation, a number of nodes contain a NULL pointer either in their left or right fields or in both. 
-This space that is wasted in storing a NULL pointer can be efficiently used to store some other useful peace of information

Comments

Post a Comment

Popular posts from this blog

AVL Tree And B Tree

Image
AVL Tree An AVL tree is a subtype of binary search tree. Named after it's inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. ~  Height of a node: -The height of an empty subtree is 0. -The height of a leaf is 1. -The height of an internal node is the maximum height of its children plus 1. ~ Balance factor: -The difference height of its LEFT subtree and its RIGHT subtree . The balance factor of all nodes in AVL tree should be at most 1. AVL Tree Example Right Rotation Left Rotation AVL Insertion Process If there is an imbalance in left child of right subtree, then you perform a left-right rotation. If there is an imbalance in left child of left subtree, then you perform a right rotation. If there is an imbalance in right child of right subtree, then you perform a left rotation. If there is an imbalance in right chi...
Read more

Linked List

Image
Linked List Linked List Definition A linked list is a dynamic data structure where a  node  is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a  head  and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front. A Simple Linked List Circular Single Linked list In Circular Single Linked List, last node contains a pointer to the first node, We can have a circular singly linked list as well as a circular doubly linked list. There is no storing of NULL values in the list Implementation Insertion A node can be added in three ways: Insertion in an empty list Insertion at the beginning of the li...
Read more

Rangkuman Before UTS

Image
Linked List Linked List Definition A linked list is a dynamic data structure where a  node  is made up of two items - the data and a reference (or pointer) which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through a pointer. The first node is called a  head  and if the list is empty then the value of head is NULL.For a real-world analogy of linked list, you can think of conga line, a special kind of dance in which people line up behind each other with hands on shoulders of the person in front. A Simple Linked List Circular Single Linked list In Circular Single Linked List, last node contains a pointer to the first node, We can have a circular singly linked list as well as a circular doubly linked list. There is no storing of NULL values in the list Implementation Insertion A node can be added in three ways: Insertion in an empty list Insertion at the beginning of the li...
Read more