DEV Community: M Muiz Hassan

String Hashing in C++

M Muiz Hassan — Fri, 01 Oct 2021 17:35:42 +0000

Hashing is an algorithm that, given any input, results in a fixed size output called hash. Today, we use hashing algorithm in data structures, cryptography, and searching etc. In this tutorial we will implement a string hashing algorithm in C++ and use it in a data structure called hash table.

Polynomial Rolling Algorithm

We shall use Polynomial Rolling algorithm to generate a hash code from a string input. It uses the following formula:

hash = x₁*A⁰ + x₂*Aⁱ + x₃*A² ... xₙ*Aⁿ⁻ⁱ

We get x from the ASCII code of a character in the string. We then multiply this ASCII code with "A", a prime number. We use a prime number to evenly distribute the values. The prime number should be close to number of available characters. For English alphabets 31 is a good empirical choice. The exponent ensures a different hash code for anagrams.

Now let's implement this algorithm in the form of a function.

#include <cmath>
#include <iostream>
using namespace std;

const int PRIME_CONST = 31;

int hashFunction(string key) {
    int hashCode = 0;
    for (int i = 0; i < key.length(); i++) {
        hashCode += key[i] * pow(PRIME_CONST, i);
    }
    return hashCode;
}

int main() {
    cout << hashFunction("abc") << endl;

    return 0;
}

In C++ we do not need to convert a character to ASCII code, as the conversion is implicit. This will print the hash of string "abc" on console.

Using the hash function in a hash table

A hash table is a data structure that uses a hashing algorithm to store key-value pairs. It is known as HashMap in Java and Dictionary in Python. In C++ it called unordered_map, which is part of unordered_map standard library.

Mapping Values

To map our values in the hash-table array we take modulus of the hash by the array's size:

index = hash code % SIZE_OF_ARRAY

This number is always less than the size of array and we can use it as the index for the value. The hash function will always produce the same index for same string key, that is the beauty of the hash function.

We can use the hash-function implementation above, but there is a huge problem. The hash code can overflow for very large values. We need a way to use our hash code for direct addressing without losing to overflow.

Fortunately, we have this formula to save the day:

(a + b) % c = (a % c + b % c) % c

and for n terms:

Σx % c = Σ(x % c) % c

The modulus shrinks the value in each iteration, so we can avoid getting a huge number. That's how we can map very long strings.

Now we create a HashTable class to use our fancy hash function.

#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

class HashTable {
    static const int PRIME_CONST = 31;
    static const int ARR_SIZE = 3001;
    int arr[ARR_SIZE];

    public:
        HashTable() {
            fill_n(arr, ARR_SIZE, 0);
        }

        void put(string key, int value) {
            int index = hashFunc(key);
            arr[index] = value;
        }

        static int hashFunc(string key) {
            size_t sum;
            for (int i = 0; i < key.length(); i++) {
                sum += (key[i] * (int)pow(PRIME_CONST, i)) % ARR_SIZE;
            }
            return sum % ARR_SIZE;
        }

        void printAll() {
            for (int i = 0; i < ARR_SIZE; i++) {
                if (arr[i] > 0) {
                    cout << arr[i] << ", ";
                }
            }
            cout << endl;
        }
};

int main() {
    HashTable hTable;
    hTable.put("abc", 1);
    hTable.put("longString", 200);
    hTable.put("veryLongString", 3000);
    hTable.printAll();

    return 0;
}

The length of array should be slightly larger than the count of data to be inserted. We use a prime number as array size to reduce collisions. Above code prints the non-zero values, inserted in the hash table, on console.

A collision occurs when we get the same index for two nodes. We use techniques such as separate chaining and open addressing for collision handling. The implementation in this tutorial does not handle collisions.

And that concludes this tutorial. We learned how to implement a hash function and use it in a data structure.

This tutorial is my attempt to help beginners learn hashing by collecting all the fundamental concepts at one place. I hope you find it beneficial.

Create an Interactive Splash Screen in Flutter

M Muiz Hassan — Sun, 30 May 2021 12:41:58 +0000

Hi, I hope you all are doing great. In this tutorial I'll be sharing the technique I use to make a quick and interactive splash screen in flutter.

Prerequisites

Basic knowledge of flutter
Basic knowledge of android

Overview

In some cases we want to add an interactive splash screen to our app to prompt the user for different states, such as no internet connection. But just creating a splash widget may not be as satisfactory because flutter takes some time to draw its first frame when the app is launched. So today we'll be combining flutter splash screen with native android splash to get a quick and interactive splash screen.

Let's Get Started

Flutter Side

1. Create a new flutter project and open it in an IDE of your choice.

2. Go to the pubspec.yaml file and specify the assets directory as following:

flutter:
  # ... other properties here
  assets:
    - assets/images/

Also change the dart SDK version constraints to enable null safety:

environment:
  sdk: ">=2.12.0 <3.0.0"

3. Create a folder assets in the project root directory. And paste this image as "logo_flutter.png" in it.

4. Create a new dart file "splash_page.dart" in the "lib" folder and paste the following code in it:

import 'package:flutter/material.dart';

class SplashPage extends StatefulWidget {
  @override
  _SplashPageState createState() => _SplashPageState();
}

class _SplashPageState extends State<SplashPage> {
  @override
  void initState() {
    WidgetsBinding.instance?.addPostFrameCallback((_) => _afterBuild(context));
    super.initState();
  }

  @override
  Widget build(BuildContext context) {
    return Container(
      color: Colors.white,
      child: Center(
        child: Image.asset('assets/images/logo_flutter.png'),
      ),
    );
  }

  void _afterBuild(BuildContext context) {
    showModalBottomSheet(
      context: context,
      isDismissible: false,
      enableDrag: false,
      barrierColor: Colors.transparent,
      backgroundColor: Colors.blue,
      shape: RoundedRectangleBorder(
          borderRadius: BorderRadius.only(
        topLeft: const Radius.circular(25),
        topRight: const Radius.circular(25),
      )),
      builder: (builderContext) {
        return SizedBox(
          height: 100,
          child: Padding(
            padding: EdgeInsets.all(16),
            child: Center(
              child: ElevatedButton(
                style: ElevatedButton.styleFrom(
                  primary: Colors.white,
                  onPrimary: Colors.blue,
                ),
                onPressed: () => Navigator.pop(context),
                child: Text('Dismiss'),
              ),
            ),
          ),
        );
      },
    );
  }
}

In the above code, we schedule our _afterBuild method to be called after the build method, inside the initState callback. The _afterBuild method will display a modal bottom sheet after the splash page has been drawn. Which can be dismissed by pressing the dismiss button.

5. Go to main.dart file and replace the existing code with following.

import 'package:flutter/material.dart';
import 'splash_page.dart';

void main() => runApp(MyApp());

class MyApp extends StatelessWidget {
  @override
  Widget build(BuildContext context) {
    return MaterialApp(
      title: 'Flutter App',
      debugShowCheckedModeBanner: false,
      home: SplashPage(),
    );
  }
}

The SplashPage widget has been passed as the home parameter, meaning flutter will show the SplashPage when our app is launched.

Android Side

6. For the android side we will need to create resolution aware image assets for our splash logo. Open the Image Baker website in your browser. Drop the the "logo_flutter.png" image you downloaded earlier. The site will generate the assets for you. Go ahead and download them by clicking on the Android button.

7. Extract the folder somewhere and you will find several drawable folders inside the extracted folder. These folders tell android which asset to use for different density displays. Copy all the drawable folders and paste them inside the {your_project}/android/app/src/main/res folder.

8. Now we need to tell android to use our newly added asset. Open the "launch_background.xml" file in the "res/drawable" folder and replace the contents with following:

<?xml version="1.0" encoding="utf-8"?>
<!-- Modify this file to customize your launch splash screen -->
<layer-list xmlns:android="http://schemas.android.com/apk/res/android">
    <item android:drawable="@android:color/white" />

    <item>
        <bitmap
            android:gravity="center"
            android:src="@drawable/logo_flutter" />
    </item>
</layer-list>

Make sure you are using the correct drawable resource name. Flutter creates a drawable-v21 variant by default for "launch_background.xml". If you don't need it for anything else delete the drawable-v21 folder or the "launch_background.xml" in it.

9. Now that we have added all the assets we need to make sure that the splash image size for our flutter splash and native android splash is the same. Open "logo_flutter.png" inside the res/drawable-xxxhdpi folder. Note the size of the image, we will need our flutter splash image to match the size of this image.

For xxxhdpi an image of 640px will be drawn as 1 inch on the device screen, while for flutter an image of 160 logical pixels will occupy 1 physical inch.

So we can calculate the size needed for flutter splash with the following equation:

h = (height of the xxxhdpi image) / 640 * 160

Where h is the calculated height for the flutter splash image. Go to "splash_page.dart" and add the calculated height to the image.

@override
  Widget build(BuildContext context) {
    return Container(
      color: Colors.white,
      child: Center(
        child: Image.asset(
          'assets/images/logo_flutter.png',
          height: 168.94,  // calculated height in my case
        ),
      ),
    );
  }

Conclusion

And that's it we're done. Go ahead and run the application to watch your custom splash screen in action! Now we can discuss the pros and cons of this approach.

Pros

You get an instantaneous splash screen that is visible the moment your app launches. The splash becomes interactive when the flutter splash widget is drawn.

Cons

There is a slight blink when flutter draws its first frame. The lag is unacceptably long in development mode but it turns to only a slight blink in release mode. You can try to further optimize your flutter splash image by using resolution aware image assets.

That concludes this tutorial. I have hosted an example project on GitHub for anyone who is interested. I can't wait to see your feedback in the comments below. I hope to see you folks next time with more interesting content.

C++: How to Write a Bitmap Image from Scratch.

M Muiz Hassan — Sat, 27 Jun 2020 12:10:17 +0000

Image processing is a vast subject covering simple filtering to complex object detection. For those of you who want to go in depth and learn how an image is stored in the computer, this is the right place to start.

In this tutorial we'll be seeing how to write a simple cyan colored bitmap image.

Preview:

The approach used in this tutorial is only compatible with systems that process data in little-endian byte format (used in most Intel and AMD machines).

Prerequisites:

Basic knowledge of C++

I. Introduction to Binary File Formats

A binary file is a collection of bits i.e. 1s and 0s, stored in a file. In most binary file formats information is stored byte by byte, byte is a collection of 8 bits. The bytes are arranged in an orderly fashion to store information. Most binary files have two major portions:

Header

Header in a binary file contains meta data (additional information about the data, for example width and height of an image).

Body

The body of a binary file contains actual data. In case of a bitmap file this is the information about each pixel in the image.

II. What is a Bitmap File?

A bitmap file basically consists of a header of variable size, however most commonly used header is of 54 bytes. In this tutorial we'll be writing a 24 bit Bitmap image. The body of a 24 bit bitmap image contains value for each pixel. Each pixel consists of 3 color channels in BGR (blue, green and red) sequence, where each channel is of 1 byte. Therefore each pixel in a 24 bit bitmap file is of 3 bytes (or 24 bits).
(For detailed specifications of the bitmap file format check: Bitmap-Specifications)

III. Code

(For Complete Example Code: Click Here)

Including Standard Libraries:



#include <cstdint> // for specific size integers
#include <fstream> // for file handling
using namespace std;

Creating the Header:

The Bitmap file has two headers for meta data. First header (bitmap file header) tells that this binary file is a bitmap file. The next header (bitmap info header) contains additional meta-data about the image.
For bitmap file header (14 bytes) we need to create the following data structure:



struct BmpHeader {
    char bitmapSignatureBytes[2] = {'B', 'M'};
    uint32_t sizeOfBitmapFile = 54 + 786432;
    uint32_t reservedBytes = 0;
    uint32_t pixelDataOffset = 54;
} bmpHeader;

The first two bytes 'B' and 'M' are unique to the bitmap file format (there still are different versions of it check bitmap format specification). The next four bytes contain total size of the bitmap file in bytes. As we are creating a 512 by 512 bitmap image, total size is the sum of size of meta data (14 + 40 = 54 bytes) and size of pixels (512 * 512 * 3 = 7863432, each pixel is of 3 bytes in 24 bit bitmap file). The last field of bitmap file header contains the offset to the pixel data of the image from the start of the file. In our case the offset is 54 bytes, as our pixel data is right after the bitmap file header and info header (14 + 40 = 54).

The bitmap file has various types of info header, but the most common one is the 40 byte Bitmap Info Header, so we need to write it down in the following data structure:



struct BmpInfoHeader {
    uint32_t sizeOfThisHeader = 40;
    int32_t width = 512; // in pixels
    int32_t height = 512; // in pixels
    uint16_t numberOfColorPlanes = 1; // must be 1
    uint16_t colorDepth = 24;
    uint32_t compressionMethod = 0;
    uint32_t rawBitmapDataSize = 0; // generally ignored
    int32_t horizontalResolution = 3780; // in pixel per meter
    int32_t verticalResolution = 3780; // in pixel per meter
    uint32_t colorTableEntries = 0;
    uint32_t importantColors = 0;
} bmpInfoHeader;

The height of bitmap file can also be negative (you may have noticed the signed integers). When height is negative the first pixel in file is drawn at top left of the image. However the standard for bitmap files is to use positive height and the first pixel in file is drawn at the bottom left of the image followed by other pixels.

The bitmap file may also contain a color table but it is not mandatory in a 24 bit bitmap file, so we will not be creating one in this example.

Creating pixel:

As I'll be creating a mono color bitmap image (all pixels have same value), I'm creating an additional struct for the pixel:



struct Pixel {
    uint8_t blue = 255;
    uint8_t green = 255;
    uint8_t red = 0;
} pixel;

Each channel in a pixel must be an unsigned integer of 1 byte for a 24 bit bitmap file. Where 255 specifies maximum color intensity and 0 specifies absence of the color.

Main function:



int main(int argc, char **argv) {
    ofstream fout("output.bmp", ios::binary);

    fout.write((char *) &bmpHeader, 14);
    fout.write((char *) &bmpInfoHeader, 40);

    // writing pixel data
    size_t numberOfPixels = bmpInfoHeader.width * bmpInfoHeader.height;
    for (int i = 0; i < numberOfPixels; i++) {
        fout.write((char *) &pixel, 3);
    }
    fout.close();

    return 0;
}

A struct may have padding (additional bytes) added by the compiler for optimizing performance. Hence sizeof() is not going to return accurate value. So I have manually specified the size of each struct in ofstream::write() method.

IV. Conclusion

So if you've succeeded in writing your first bitmap file give yourself a pat on the shoulder. Next you may be interested in writing different types of bitmap files, for that check bitmap specifications. Kudos and keep learning!