Hashing table & Binary Tree.

Nama :Dea Claresta
Nim:23018637376


Hashing is a technique used for storing and retrieving keys in a rapid manner
hash table is a table(array) where we store the original string.
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

The two heuristic methods are hashing by division and hashing by multiplication which are as follows:

1. The mod method:
   • In this method for creating hash functions, we map a key into one of the slots of table by taking the remainder of key divided by table_size. That is, the hash function is

     h(key) = key mod table_size 
     
     i.e. key % table_size

   • Since it requires only a single division operation, hashing by division is quite fast.
   • When using the division method, we usually avoid certain values of table_size like table_size should not be a power of a number suppose r, since if table_size = r^p, then h(key) is just the p lowest-order bits of key. Unless we know that all low-order p-bit patterns are equally likely, we are better off designing the hash function to depend on all the bits of the key.
   • It has been found that the best results with the division method are achieved when the table size is prime. However, even if table_size is prime, an additional restriction is called for. If r is the number of possible character codes on an computer, and if table_size is a prime such that r % table_size equal 1, then hash function h(key) = key % table_size is simply the sum of the binary representation of the characters in the key mod table_size.
   Example:
   • Suppose r = 256 and table_size = 17, in which r % table_size i.e. 256 % 17 = 1.
   • So for key = 37596, its hash is

     37596 % 17 = 12

   • But for key = 573, its hash function is also

     573 % 12 = 12

   • Hence it can be seen that by this hash function, many keys can have the same hash. This is called Collision.
   • A prime not too close to an exact power of 2 is often good choice for table_size.
2. The multiplication method:
   • In multiplication method, we multiply the key k by a constant real number c in the range 0 < c < 1 and extract the fractional part of k * c.
   • Then we multiply this value by table_size m and take the floor of the result. It can be represented as

     h(k) = floor (m * (k * c mod 1))
                          or
     h(k) = floor (m * frac (k * c))
     

     where the function floor(x), available in standard library math.h, yields the integer part of the real number x, and frac(x) yields the fractional part. [frac(x) = x – floor(x)]
   • An advantage of the multiplication method is that the value of m is not critical, we typically choose it to be a power of 2 (m = 2p for some integer p), since we can then easily implement the function on most computers
   • Suppose that the word size of the machine is w bits and that key fits into a single word.
   • We restrict c to be a fraction of the form s / (2w), where s is an integer in the range 0 < s < 2w.
   • Referring to figure, we first multiply key by the w-bit integer s = c * 2w. The result is a 2w-bit value

     r1 * 2w + r0
     
     where r1 = high-order word of the product
           r0 = lower order word of the product
     

   • Although this method works with any value of the constant c, it works better with some values than the others.

     c ~ (sqrt (5) – 1) / 2 = 0.618033988 . . .

     is likely to work reasonably well.
   Example:
• Suppose k = 123456, p = 14,
• m = 2^14 = 16384, and w = 32.
• Adapting Knuth’s suggestion, c to be fraction of the form s / 2^32.
• Then key * s = 327706022297664 = (76300 * 2^32) + 17612864,
• So r1 = 76300 and r0 = 176122864.
• The 14 most significant bits of r0 yield the value h(key) = 67.

• Binary Tree Data Structure

  A tree whose elements have at most 2 children is called a binary tree. Since each element in a binary tree can have only 2 children, we typically name them the left and right child.
  
  A Binary Tree node contains following parts.
  
  
  
  
  1. Data
  2. Pointer to left child
  3. Pointer to right childFollowing are common types of Binary Trees.
     Full Binary Tree A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree. We can also say a full binary tree is a binary tree in which all nodes except leaves have two children.
     
     
     
     

                    18
                /       \  
              15         30  
             /  \        /  \
           40    50    100   40
     
                  18
                /    \   
              15     20    
             /  \       
           40    50   
         /   \
        30   50
     
                    18
                 /     \  
               40       30  
                        /  \
                      100   40
     

     
     
     
     
     In a Full Binary, number of leaf nodes is number of internal nodes plus 1
            L = I + 1
     Where L = Number of leaf nodes, I = Number of internal nodes
     See Handshaking Lemma and Tree for proof.
     
     
     Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible
     Following are examples of Complete Binary Trees

                    18
                /       \  
              15         30  
             /  \        /  \
           40    50    100   40
     
     
                    18
                /       \  
              15         30  
             /  \        /  \
           40    50    100   40
          /  \   /
         8   7  9 
     

     Practical example of Complete Binary Tree is Binary Heap.
     
     
     Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.
     Following are examples of Perfect Binary Trees.

                    18
                /       \  
              15         30  
             /  \        /  \
           40    50    100   40
     
     
                    18
                /       \  
              15         30  
     

     A Perfect Binary Tree of height h (where height is the number of nodes on the path from the root to leaf) has 2h – 1 node.
     Example of a Perfect binary tree is ancestors in the family. Keep a person at root, parents as children, parents of parents as their children.
     
     
     Balanced Binary Tree
     A binary tree is balanced if the height of the tree is O(Log n) where n is the number of nodes. For Example, AVL tree maintains O(Log n) height by making sure that the difference between heights of left and right subtrees is atmost 1. Red-Black trees maintain O(Log n) height by making sure that the number of Black nodes on every root to leaf paths are same and there are no adjacent red nodes. Balanced Binary Search trees are performance wise good as they provide O(log n) time for search, insert and delete.
     
     
     A degenerate (or pathological) tree A Tree where every internal node has one child. Such trees are performance-wise same as linked list.

           10
           /
         20
          \
          30
           \
           40     

     Hashing table implementation in Blockchain. Is that used in current block chain technology?:In a blockchain, each node of the network stores the full data. So it is absolutely not the same idea as the DHT in which data are divided among nodes. Every new entry in the blockchain must be validated by a process called mining whose details are out of the scope of this answer but this process insure consensus of the data.
     The two structures are both distributed data structure but serve different purposes. DHT aims to provide an efficient (in term of lookup time and storage footprint) structure to divide data on a network and blockchain aims to provide a tamper-proof data structure.