Hash table & Binary Tree

Hash table & Binary Tree.

Hashing

A technique used for storing and retrieving keys in a rapid manner.  What hashing do basically, they are transforming a string of characters into a shorter length value or key that represents the original string and then these transform string of character is used to index and retrieve in a database since it is faster to find item using the shorter key that was previously transform.  Hashing can be defined as a concept of distributing keys in an array called hash table (which is going to be explained next) using a predetermined function called hash function.

Hash Table

A table of array in which where we store the original string.  The index of the table is the hashed key while the value is the original string.  The size of hash table is usually significantly lower than the number of possible string, so several string might have a same hashed-key.

1.1 Hash Table coding example.

There are many ways to hash a string and here is a few hash function to name:

• Mid-square
• Division
• Folding
• Digit Extraction
• Rotating Hash

Binary Tree

First thing first a tree is a non-linear data structure that represent the hierarchical relationships among the data object.  The data or node in the tree need not to be stored continuously and can be stored anywhere and linked by pointers.  A binary tree is a data structure in which each node has at most two children that is usually distinguished as left child and right child.

1.2 Example of Binary Tree