More

    HASHING BASICS

    Hashing is a technique for storing and retrieving information faster. Hashing can give a complexity of O(1) in best case; however the worst case is still O(n).

    COMPONENTS OF HASHING

    Important components of hashing are:

    1. Hash buckets
    2. Hashing functions

    BASIC HASHING EXPLAINED

    1. There will be storage locations called buckets.
    2. Your hash function will generate a bucket number for every object.
    3. When you want to store any element, you use the hash function to get the bucket number and store the element in that bucket.
    4. When you need the element back, you use the same hash function to get the bucket number of your object and then get the object from that bucket.

    Note: If a bucket contain only one element, you can retrieve in O(1) time, but if one bucket contain all elements, you might need O(n) complexity in worst case.

    IMPLEMENTING USING ARRAYS

    You may implement a hashing data structure using arrays. Each array location can be considered as a bucket. The value generated by your hash function can be mapped to one of array location using a simple mod function.

    Collisions

    Even though the ideal hashing algorithm will generate a different bucket for every object, in practical scenarios, more than one object will have the same hash code. Thus more than one element will be mapped to a single bucket. Mapping more than one element to a single bucket is called as collision.

    If you are implementing using arrays, this means that, more than one element needs to be stored in one array location. However this is not possible in most programming languages like Java.

    Collision resolution techniques

    We can have a linked list of elements in each array location. This is one of the popular collision resolution techniques.

    Based on the hash code generated by the hash function, you can find the array location (or bucket) and then traverse through the associated linked list and place the elements to the end of the linked list. You may also add elements to the beginning of the linked list for faster O(1) insertion.

    When you want to retrieve elements, you can use the same hash function to get the array location, then traverse through the associated linked list to find the element.

    Note that even if you have collisions, this is better than using a linked list alone, as now you will need to only search on a subset of elements and not the complete set of elements. 

    HASHING IN JAVA

    • In earlier Java versions, hashing is implemented (in case of HashMap) using arrays and linked list roughly as explained above.
    • Java uses Object class’s hashCode method to generate the hashcode and uses it to find the array location, and then use Object class’s equals method to find the right object in the bucket (the associated linked list).

    TODO

    Find out how hash maps are implemented in your programming language of choice (if it has one).

    Recent Articles

    OAUTH – FREQUENTLY ASKED QUESTIONS FOR INTERVIEWS AND SELF EVALUATION

    Why is refresh token needed when you have access token? Access tokens are usually short-lived and refresh tokens are...

    SUMO LOGIC VIDEOS AND TUTORIALS

    Sumo Logic Basics - Part 1 of 2 (link is external) (Sep 29, 2016)Sumo Logic Basics - Part 2 of 2...

    GIT – USEFUL COMMANDS

    Discard all local changes, but save them for possible re-use later:  git stash Discarding local changes...

    DISTRIBUTED COMPUTING – RECORDED LECTURES (BITS)

    Module 1 - INTRODUCTION Recorded Lecture - 1.1 Introduction Part I – Definition

    BOOK REVIEW GUIDELINES FOR COOKBOOKS

    Whenever you add reviews for the book, please follow below rules. Write issues in an excel.Create an excel...

    Related Stories

    Leave A Reply

    Please enter your comment!
    Please enter your name here

    Stay on op - Ge the daily news in your inbox