Hashing

Data Structures Notes

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.

Binary Tree

Data Structures Notes

Binary tree traversal: Preorder, Inorder, and Postorder

In order to illustrate few of the binary tree traversals, let us consider the below binary tree:












Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Linked List

linked list is a dynamic and linear data structure.

---

The Concept Of Link List

1.Link list used for the dynamic memory allocation.
2.Array and link list both are the linear data structure.
3.When we want to represent several lists by using arrays of varying size, either we have to represent.
4.each list using a separate array of maximum size or we have to represent each of the lists using one single array.
5.The first one will lead to wastage of storage, and the second will involve a lot of data movement.
6.A linked list is a list of elements in which the elements of the list can be placed anywhere in memory, and these elements are linked with each other using an explicit link field, that is, by storing the address of the next element in the link field of the previous element.

Data Structure

Data Structures

Introduction

1. Computer system is used as Data Management System where ‘Data’ are very    important for it.
2. Data are aggregated and summarized in various ways to form information.
3. All these factors very much depend on the way data are aggregated.
4. The Data Structures are an effective and reliable way to achieve this.