Mid-Square hashing

Mid-Square hashing is a hashing technique in which unique keys are generated. In this technique, a seed value is taken and it is squared. Then, some digits from the middle are extracted. These extracted digits form a number which is taken as the new seed. This technique can generate keys with high randomness if a big enough seed value is taken. However, it has a limitation. As the seed is squared, if a 6-digit number is taken, then the square will have 12-digits. This exceeds the range of int data type. So, overflow must be taken care of. In case of overflow, use long long int data type or use string as multiplication if overflow still occurs. The chances of a collision in mid-square hashing are low, not obsolete. So, in the chances, if a collision occurs, it is handled using some hash map. Example:

Suppose a 4-digit seed is taken. seed = 4765 Hence, square of seed is = 4765 * 4765 = 22705225 Now, from this 8-digit number, any four digits are extracted (Say, the middle four). So, the new seed value becomes seed = 7052 Now, square of this new seed is = 7052 * 7052 = 49730704 Again, the same set of 4-digits is extracted. So, the new seed value becomes seed = 7307 . . . . This process is repeated as many times as a key is required.

Mid square technique takes a certain number of digits from the square of a number. This number extracted is a pseudo-random number, which can be used as a key for hashing. Algorithm:

1. Choose a seed value. This is an important step as for same seed value, the same sequence of random numbers is generated.
2. Take the square of the seed value and update seed by a certain number of digits that occur in the square. Note: The larger is the number of digits, larger will be the randomness.
3. Return the key.

Below is the implementation of above algorithm: 

// C++ program to illustrate the
// mid-square hashing technique
#include <ctime>
#include <iostream>

using namespace std;

// Returns a seed value based on current system time.
long long int newTime()
{

    // Acquiring number of seconds
    // passed from Jan 1, 1970.
    time_t t = time(NULL);

    // Converting the time to year, month,
    // day, hour, minute, and second.
    struct tm* tm = localtime(&t);
    long long int x;

    // Applying a certain logic to get
    // required number of digits. It may vary.
    x = (tm->tm_hour) * 10000000 + (tm->tm_min) * 100000
        + (tm->tm_sec) * 1000 + (tm->tm_mday) * 10 + (tm->tm_year);

    // Return the calculated number.
    return x;
}

// Returns a random 8-digit key.
long int getKey()
{

    // Taking the key from system time. 
    // returns a  8-digit seed value.
    static long long int key = newTime();

    // Squaring the key.
    key = key * key;

    // Extracting required number of digits ( here, 8 ).
    if (key < 1000000000000000) {
        key = key / 10000;
        key = key % 100000000;
    }
    else {
        key = key / 10000;
        key = key % 100000000;
    }

    // Returning the key value.
    return key;
}

// Driver Code
int main()
{
    // get the first key
    std::cout << getKey() << endl;

    // get the second key
    std::cout << getKey() << endl;
    return 0;
}

//Note: The output will change according to the date and time.

import java.time.LocalDateTime;

public class Main {
    
    // Returns a seed value based on current system time.
    public static long newTime() {
        // Acquiring the current date and time
        LocalDateTime now = LocalDateTime.now();
        
        // Extracting components: hour, minute, second, day, and year
        long x = now.getHour() * 10000000 + now.getMinute() * 100000 +
                 now.getSecond() * 1000 + now.getDayOfMonth() * 10 + now.getYear();
        
        // Return the calculated seed value
        return x;
    }

    // Returns a random 8-digit key.
    public static long getKey() {
        // Taking the key from system time to generate a seed value
        long key = newTime();
        
        // Squaring the key
        key = key * key;

        // Extracting required number of digits (here, 8).
        if (key < 1000000000000000L) {
            key = key / 10000;
            key = key % 100000000;
        } else {
            key = key / 10000;
            key = key % 100000000;
        }

        // Returning the key value
        return key;
    }

    // Driver Code
    public static void main(String[] args) {
        // Get the first key
        System.out.println(getKey());
        
        // Get the second key
        System.out.println(getKey());
    }
}
//Note: The output will change according to the date and time.

using System;

namespace MidSquareHashing
{
class Program
{
// Returns a seed value based on current system time.
static long newTime()
{
// Acquiring number of seconds
// passed from Jan 1, 1970.
long t = DateTimeOffset.UtcNow.ToUnixTimeSeconds();

        // Converting the time to year, month,
        // day, hour, minute, and second.
        DateTime dtDateTime = new DateTime(1970, 1, 1, 0, 0, 0, DateTimeKind.Utc);
        dtDateTime = dtDateTime.AddSeconds(t).ToLocalTime();
        long x;

        // Applying a certain logic to get
        // required number of digits. It may vary.
        x = (dtDateTime.Hour) * 10000000 + (dtDateTime.Minute) * 100000
            + (dtDateTime.Second) * 1000 + (dtDateTime.Day) * 10 + (dtDateTime.Year);

        // Return the calculated number.
        return x;
    }

    // Returns a random 8-digit key.
    static long getKey()
    {
        // Taking the key from system time.
        // returns a 8-digit seed value.
        long key = newTime();

        // Squaring the key.
        key = key * key;

        // Extracting required number of digits ( here, 8 ).
        if (key < 1000000000000000)
        {
            key = key / 10000;
            key = key % 100000000;
        }
        else
        {
            key = key / 10000;
            key = key % 100000000;
        }

        // Returning the key value.
        return key;
    }

    // Driver Code
    static void Main(string[] args)
    {
        // get the first key
        Console.WriteLine(getKey());

        // get the second key
        Console.WriteLine(getKey());
    }
}
}

//Note: The output will change according to the date and time.

// Returns a seed value based on current system time.
function newTime() {
    // Acquiring the current date and time
    const now = new Date();
    
    // Extracting components: hour, minute, second, day, and year
    let x = now.getHours() * 10000000 + now.getMinutes() * 100000 +
             now.getSeconds() * 1000 + now.getDate() * 10 + now.getFullYear();
    
    // Return the calculated seed value
    return x;
}

// Returns a random 8-digit key.
function getKey() {
    // Taking the key from system time to generate a seed value
    let key = newTime();
    
    // Squaring the key
    key = key * key;

    // Extracting required number of digits (here, 8).
    if (key < 1000000000000000) {
        key = Math.floor(key / 10000) % 100000000;
    } else {
        key = Math.floor(key / 10000) % 100000000;
    }

    // Returning the key value
    return key;
}

// Driver Code
// Get the first key
console.log(getKey());

// Get the second key
console.log(getKey());

import time

# Returns a seed value based on current system time.
def new_time():
    # Acquiring number of seconds passed since Jan 1, 1970.
    t = int(time.time())
    
    # Converting the time to year, month, day, hour, minute, and second.
    tm = time.localtime(t)
    
    # Applying a certain logic to get required number of digits.
    x = (tm.tm_hour) * 10000000 + (tm.tm_min) * 100000 + (tm.tm_sec) * 1000 + (tm.tm_mday) * 10 + (tm.tm_year)
    
    # Return the calculated number.
    return x

# Returns a random 8-digit key.
def get_key():
    # Taking the key from system time. 
    # Returns an 8-digit seed value.
    global key
    key = new_time()

    # Squaring the key.
    key *= key

    # Extracting required number of digits (here, 8).
    if key < 1000000000000000:
        key //= 10000
        key %= 100000000
    else:
        key //= 10000
        key %= 100000000

    # Returning the key value.
    return key

# Driver Code
if __name__ == "__main__":
    # Get the first key
    print(get_key())
    
    # Get the second key
    print(get_key())
    
 #Note: The output will change according to the date and time.

24788668
47806121

Note: The output will change according to the date and time.

47AbhinavSharma

Follow

Improve