Langsung ke konten utama

Introduction To Hash Table & Binary Tree


INTRODUCTION TO HASH TABLE
Hashing is the process of mapping large amount of data item to smaller table with the help of hashing function. In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.
Advantage using Hash Table :  
  • synchronization.
  • In many situations, hash tables turn out to be more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software , particularly for associative arrays, database indexing, caches and sets.
Disadvantages using Hash Table :
  • Hash collisions are practically unavoidable. when hashing a random subset of a large set of possible keys.
  • Hash tables become quite inefficient when there are many collisions.
  • Hash table does not allow null values, like hash map.
Hashing is a technique that is used to uniquely identify a specific object from a group of similar objects. Some examples of how hashing is used in our lives include:
  • In universities, each student is assigned a unique roll number that can be used to retrieve information about them.
  • 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
In this method, the hash is independent of the array size and it is then reduced to an index (a number between 0 and array_size − 1) by using the modulo operator (%).






INTRODUCTION TO TREES
Trees can be defined as a collection of entities called node linked together to stimulate hierarchy. Trees isn’t linear data structure hierarchical structures. Before jump into the explanation, the tree can only walk in 1 direction and cannot go back. For further explanation, let’s look the image below.
As I mentioned earlier, tree only can walk in 1 direction. For example, the node 2 can go to 7, but 7 can’t go back to 2. And it applied to others. That’s it.
There’re so many explanation about the trees. But for make it simple, the trees can be defined same as a Family tree but only a little different from it. There’re things called “Root”, ”Parents”, ”Children”, “Siblings”, “Leaf node” , “Grand Parent & Grand Child”, “Link”, etc. So, let’s jump into the mean all of that.
Root : The top of the trees called “Root”. Root always in the top of tree. It can be filled by any type of data such integer (ex : 2 ), string (ex : name), character (‘a’), etc.
Parent : from the picture above, 2 is a parent from 7 and 5. So, the 2 can be called parent and also 2 can be also called the root of the tree, and so on.
Children : from the picture above, we can see 7 and 5 is a children from 2. And also 2, 10, and 6 is the children from 7 and 9 is a children from 5, and so on.
Sibling : well, from the picture, because 7 and 5 is a child from 2, they can be called siblings because they’re had a same parent. It also applied to 2,10 and 6 as a sibling because they had a same parent is 7. And it applied to the other.
 Leaf Node : the node that hadn’t a child anymore called leaf node. You can see from the picture below that 2,5,11, and 4 are leaf node because they hadn’t a child anymore.
Grand Parent & Grand Child : I don’t know how to put it for definition, but example for grand parent is that 9 is a grand child from 2, and 2 is a grand parent to 9. And it applied to others.
Link : The arrow that connected one to each other called link. Same as the definition, the function from link is to connected each node to other node.
If we can go from node A to B, then A is a ancestors of node B. and B is a descendent to A.
For example, 2,7 and 6 are the ancestors of 11. And 11 is the descendent for 2,7, and 6.

Komentar

Posting Komentar

Postingan populer dari blog ini

Heap & Tries {Theory}

HEAP & TRIES 1.        Heap Dalam  ilmu komputer , sebuah  heap  adalah struktur data yang berdasarkan konsep struktur data  pohon . Di heap, juga diterapkan konsep binary tree. Terdapat 3 jenis heap, diantaranya : a.      Min heap Min heap merupakan heap yang node rootnya adalah angka terkecil dan setiap anak dari rootnya selalu lebih kecil daripada parentnya. Biasanya min heap ini, dia ascending ( dari terkecil ke terbesar ). b.     Max heap Max heap ini sama seperti min heap, tapi bedanya adalah angka yang berada di root adalah angka terbesar dan max heap ini descending ( dari terbesar ke terkecil ). c.      Min Max heap Untuk min max heap ini cukup unik, dimana root dari heap ini merupakan angka terkecil didalam tree nya, tapi angka yang berada dii node anak dari sebuah root merupakan angka paling besar dan berlaku seterusnya sampai ke bawah. Berikut ad...
Posting Komentar
Baca selengkapnya

AVL Tree [Theory]

AVL TREE AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. For example :    (Left : Correct AVL Tree || Right : Wrong AVL Tree) The reason why right AVL tree is wrong because the above tree is not AVL because differences between heights of left and right subtrees for 8 and 18 is greater than 1. AVL trees have an additional guarantee: The difference between the depth of right and left subtrees cannot be more than one. In order to maintain this guarantee, an implementation of an AVL will include an algorithm to rebalance the tree when adding an additional element would upset this guarantee. AVL trees have a worst case lookup, insert and delete time of O(log n). In AVL Tree, we can perform Insertion and Deletion. ·        Insertion To make sure that the given tree remains AV...
Posting Komentar
Baca selengkapnya

Binary Tree Introduction

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. PARTS OF NODE IN BINARY TREE : 1.       Data, 2.       Pointer to left child, and 3.       Pointer to right child. THE USED FROM BINARY TREE ARE FOLLOWING : 1.       Manipulate hierarchical data, 2.       Make information easy to search, 3.       Manipulate sort list of data, 4.       Composting digital images for visual effect, 5.       Router Algorithms, and 6.         Form of a multi-stage decision-making (see business chess). TREE’S PART 1. ...
Posting Komentar
Baca selengkapnya