DEV Community: iamanand07

Hash! A magical datastructure

iamanand07 — Fri, 15 Sep 2023 16:34:39 +0000

Hashing is a process of converting data into a fixed-length string of characters, which is typically a hexadecimal or binary representation. This fixed-length string is commonly known as a "hash value" or "hash code."

Components of hash

It consists of key components,

Key: It refers to the text that we want to hash.

Hash function: A hash function (H(x)) is a mathematical algorithm that takes the key as input and produces a fixed-length hash value as output

H(x)= x mod 7

where x is the key that we want to hash.
In this example , hash function we have taken 7 because we limit the hashtable size to 7. We can also modify the value as per our needs.

Hash Table: A Hash table is a data structure that maps keys to values using a hash function. Hash stores the data in an array where each data value has its unique index.

Why do we need hash?

In programming to insert, search, and delete data we have data structures like,

Array

In the array, the time complexity for insertion ,deletion and search takes O(n). But if we can reduce the time to O(log n) by search an element in a sorted order by binary search but then insertion and deletion becomes costly.

Linked Lists

This also takes linear time complexity.

Binary Search Tree

This takes logarithmic time in insertion ,deletion ,and search.

Hash

This takes constant time for every operations.
So this will increase the efficiency of the program and retrieve information in no time.

Collision

Collision is a situation in which where two keys having same hash values.
For example,

H(x)= x mod 7

H(13)= 13 mod 7 => 6 H(20)= 20 mod 7 => 6

So the program don't know where to store the second hash value.
This will lead to collision.

Collision Handling Techniques

Handling hash collisions is essential in hash tables, where each key needs to be mapped to a unique location within the table. Several techniques are commonly used to address hash collisions.

Chaining

This make each cell of the hash table point to a linked list of records that have the same hash function value. Chaining requires additional memory outside the table.

For example,

We have some elements like 14,21,49,50. Our hash function is

H(x) = x mod 7

H(14) = 14 mod 7 => 0 H(21) = 21 mod 7 => 0 H(49) = 49 mod 7 => 0

In 0th position of the hash table the values are stored like,

14 -> 21 -> 49

From this we clearly see that there is a collision that three key have the same hash value so the value can be stored using linked lists to store the series of values having same hash value.

Open Addressing

All elements are stored in the hash table itself. Each table entry contains either a record or NIL.
This is of three types,

Linear probing
Quadratic probing
Double probing

For example,

We have the same elements 14,21,49,50. Our hash function is

H(x) = x mod 7

H(14) = 14 mod 7 => 0 H(21) = 21 mod 7 => 0

Here the value of 14 is stored in 0th position and 21 can be stored in 1th position.

Getting Started With MongoDB

iamanand07 — Wed, 12 Jul 2023 07:35:50 +0000

Before getting started with MongoDB we have to know

what really a database is,
Why we use databases,
What are the different types of databases are available,
How to choose the database that suits our requirements.

WHAT IS A DATABASE?

A Database is a collection of tables which have the information stored in rows and columns, in which we can do whatever CRUD(CREATE,READ,UPDATE,DELETE) operations we need.
simple right!!

WHY WE USE DATABASE?

If we want to store large amount of data we need to have a database which is acts as a container to store our data in a understandable manner.

What are the different types of databases are available?

The following are the different types of databases available,

Centralized database.
Distributed database.
Personal database.
End-user database.
Commercial database.
NoSQL database.
Operational database.
Relational database.
Cloud database.
Object-oriented database.
Graph database.

To know more about types of databases

tutorialspoint.com

How to choose the database that suits our requirements

For choosing a database for our project we have to think about five important aspects they are

Integration.
Scaling Requirement.
Support Consideration.
CAP Consideration(Consistency, Availability, and Partition tolerance).
Schemas or Data Model.

INTRODUCTION TO MONGODB

A MongoDB is a container for all the collections, where Collection is a bunch of MongoDB documents similar to tables in RDBMS and Document is made up of the fields similar to a tuple in RDBMS, but it has a dynamic schema here.

MongoDB is a NoSQL cross-platform document-oriented database.
MongoDB is one of the popular databases which is written in C++.
MongoDB stores data as BSON documents.
BSON is a binary representation of JSON documents.
It organized as Database->Collections->Documents.

BASIC OPERATIONS PERFORMED IN MONGODB

Create Database.
Drop Database.
Create Collection.
Drop Collection.
Insert Document.
Query Document.
Update Document.
Delete Document.

1. Create Database.

To create a new database in mongodb we can use the command
use DATABASE_NAME. The command will create a new database if it doesn't exist, otherwise, it will return the existing database.

>use student
switched to student

Here we have created a database student with use command COOL!!

2. Drop Database.

To drop a existing database in mongodb we can use the command
db.dropDatabase(). The command will remove a database if it does exist.

>use student
switched to student
>db.dropDatabase();
{ "ok" : 1 }

First we have entered into the database then we can use dropDatabase command to delete our existing database.

3. Create Collection.

To create collection in MongoDB , we can use db.createCollection(name, options)
In this command, name is the name of the collection to be created. options are a document and are used to specify the configuration of collection.

>db.createCollection("newCollection")
{ "ok" : 1 }

We can see list of collections by show collections command.

4. Drop Collection.

To drop a existing collection in mongodb we can use the command
drop(). The command will remove a collection if it does exist.

>db.newCollection.drop()
true

Here newCollection is the name of the collection. true is the value that returned that the collection is dropped successfully.

5. Insert Document.

There are two ways for inserting a document in mongodb.

Inserts a single document.
Inserts multiple documents.

To insert a single document we can use db.collection.insertOne().It inserts a single document into a collection.

> db.newCollection.insertOne({
    title: 'My first Blog',
    description: 'Insert a single document to a collection',
    by: 'Anand',
    url: 'https://dev.net',
    tags: ['NoSQL', 'database', 'beginner'],
    likes: 85
 });
{
        "acknowledged" : true,
        "insertedId" : ObjectId("5e5972397596f4d696a78944")
}

To insert multiple documents we can use db.collection.insertMany().It inserts multiple documents into a collection.It will pass an array of documents to the method.

db.newCollection.insertMany([
   {
    title: 'My first Blog',
    description: 'Insert a single document to a collection',
    by: 'Anand',
    url: 'https://dev.net',
    tags: ['NoSQL', 'database', 'beginner'],
    likes: 85
   },

   {
    title: 'My second Blog',
    description: 'Insert multiple documents to a collection',
    by: 'Anand',
    url: 'https://dev.net',
    tags: ['NoSQL', 'database', 'beginner'],
    likes: 85


   }
]);

{
        "acknowledged" : true,
        "insertedIds" : [
                ObjectId("5e5972397596f4d696a78944"),
                ObjectId("5e7572397455f4d696a78597")
        ]
}

6.QUERY DOCUMENT.

To retrieve the document that we just inserted, query the collection:

>db.newCollection.find().pretty();
{
    "id": ObjectId("5e5972397596f4d696a78944")
    "title": 'My first Blog',
    "description": 'Insert a single document to a collection',
    "by": 'Anand',
    "url": 'https://dev.net',
    "tags": [
             'NoSQL',
             'database', 
             'beginner'
],
    "likes": 85
 }

find() method will display all the documents in a non-structured way.
pretty() method will display all the documents in a understandable manner.

7. Update Document.

There are three ways to update a document in mongodb , they are

db.newCollection.updateOne(<filter>, <update>, <options>)
db.newCollection.updateMany(<filter>, <update>, <options>)
db.newCollection.replaceOne(<filter>, <update>, <options>)

8.DELETE DOCUMENT.

There are three ways to delete a document in mongodb , they are

db.newCollection.deleteOne() - Delete at most a single document that match a specified filter even though multiple documents may match the specified filter.
db.newCollection.deleteMany() - Delete all documents that match a specified filter.
db.newCollection.remove() - Delete a single document or all documents that match a specified filter.