Summary of Hashing Tables and Binary Tree

HASHING

Hashing is a technique used for storing and retrieving keys in a rapid manner. Also defined as a concept of distributing keys in an array called hash table using a predetermined function called hash function. 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. For example :

1. In universities, each student is assigned a unique roll number that can be used to retrieve information about them.

2. In libraries, each book is assigned a unique number that can be used to determine information about the book, such as its exact position in the library or the users it has been issued to etc.

Hashing is implemented in two steps:

1. An element is converted into an integer by using a hash function. This element can be used as an index to store the original element, which falls into the hash table.

2. The element is stored in the hash table where it can be quickly retrieved using hashed key.

- hash = hashfunc(key) - index = hash % array_size

1. HASH FUNCTION

A hash function is any function that can be used to map a data set of an arbitrary size to a data set of a fixed size, which falls into the hash table. The values returned by a hash function are called hash values, hash codes, hash sums, or simply hashes. To achieve a good hashing mechanism, you should need :

1. Easy to compute.

2. provide a uniform distribution across the hash table and should not result in clustering.

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

• Division (most common)

• Folding

• Digit Extraction

• Rotating Hash

2. HASH TABLE

Hash table is a table (array) where we store the original string. Index of the table is the hashed key while the value is the original string. The size of hash table is usually several orders of magnitude lower than the total number of possible string, so several string might have a same hashed-key.

TREE & BINARY TREE

A tree is a non-linear data structure that represents the hierarchical relationships among the data objects. Some of the tree relations can be observed in directory structures or organizational hierarchies. Commonly used terminologies for tree:

1. Root: Top node in a tree

2. Child: Nodes that are next to each other and connected downwards

3. Parent: Converse notion of child

4. Siblings: Nodes with the same parent

5. Descendant: Node reachable by repeated proceeding from parent to child

6. Ancestor: Node reachable by repeated proceeding from child to parent.

7. Leaf: Node with no children

8. Internal node: Node with at least one child

9. External node: Node with no children

There are also 4 types of binary tree :

1. Perfect Binary Tree : binary tree in which every level are at the same depth.

2. Complete Binary Tree : 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.

3. Skewed Binary Tree : binary tree in which each node has at most one child.

4. Balanced Binary Tree : binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

---

SOURCE :

1. https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/

2. https://www.hackerearth.com/practice/data-structures/trees/binary-and-nary-trees/tutorial/

3. Binusmaya powerpoint

For The Image :

1. https://www.geeksforgeeks.org/wp-content/uploads/HashingDataStructure-min-1024x512.png