Hashing, Hash Data Structure and Hash Table

Hashing is the process of mapping large amount of data item to a smaller table with the help of a hashing function. The essence of hashing is to facilitate the next level searching method when compared with the linear or binary search. The advantage of this searching method is its efficiency to hand vast amount of data items in a given collection (i.e. collection size).

Due to this hashing process, the result is a Hash data structure that can store or retrieve data items in an average time disregard to the collection size.

Hash Table is the result of storing the hash data structure in a smaller table which incorporates the hash function within itself. The Hash Function primarily is responsible to map between the original data item and the smaller table itself. Here the mapping takes place with the help of an output integer in a consistent range produced when a given data item (any data type) is provided for storage and this output integer range determines the location in the smaller table for the data item. In terms of implementation, the hash table is constructed with the help of an array and the indices of this array are associated to the output integer range.

Hash Table Example :
Here, we construct a hash table for storing and retrieving data related to the citizens of a county and the social-security number of citizens are used as the indices of the array implementation (i.e. key). Let's assume that the table size is 12, therefore the hash function would be Value modulus of 12.

Hence, the Hash Function would equate to:
(sum of numeric values of the characters in the data item) %12
Note! % is the modulus operator

Let us consider the following social-security numbers and produce a hashcode:
120388113D => 1+2+0+3+8+8+1+1+3+13=40
Hence, (40)%12 => Hashcode=4

310181312E => 3+1+0+1+8+1+3+1+2+14=34
Hence, (34)%12 => Hashcode=10

041176438A => 0+4+1+1+7+6+4+3+8+10=44
Hence, (44)%12 => Hashcode=8

Therefore, the Hashtable content would be as follows:
-----------------------------------------------------
0:empty
1:empty
2:empty
3:empty
4:occupied Name:Drew Smith SSN:120388113D
5:empty
6:empty
7:empty
8:occupied Name:Andy Conn SSN:041176438A
9:empty
10:occupied Name:Igor Barton SSN:310181312E
11:empty
-----------------------------------------------------

What is a Search Tree?

Search Tree is based on the Binary Search Tree (BST) in which each node has a left and right child. All the childern to the left of the node with key values have smaller than the root node, all the childern to the right of the node have values greater than the root node.

For example, a sequence of numbers like 34, 54, 66, 12, 43, 28, 83 in a Search Tree is represented as follows:
Now, in order to search a given value i.e. 43 in this constructed tree. Start at the root node to search 43, this is done by making comparsion with the node value. When the value compared with the search value results to be greater, then move to the right node or vice versa. In this case, we move right because 43 is greater than 34.

From, now on just repeat the comparison procedure until you find a matching value or end the comparing procedure at a leaf node.

Continuing our search, we now compare 54 with 43, we notice 43 is less than 54, hence we move left and compare the leaf nodes value i.e. 43 with the search value i.e. 43, therefore 43 equals to 43... match found!

Advantages of such a search tree: Insertion, Removal, Search are performed efficiently. In particularly, when considering the searching iteration we reduce the number of elements to search by one-half.