Hashing de medio cuadrado

El hash de medio cuadrado es una técnica de hash en la que se generan claves únicas. En esta técnica, se toma un valor inicial y se eleva al cuadrado. Luego, se extraen algunos dígitos del medio. Estos dígitos extraídos forman un número que se toma como la nueva semilla. Esta técnica puede generar claves con alta aleatoriedad si se toma un valor semilla lo suficientemente grande. Sin embargo, tiene una limitación. Como la semilla está elevada al cuadrado, si se toma un número de 6 dígitos, entonces el cuadrado tendrá 12 dígitos. Esto excede el rango del tipo de datos int. Por lo tanto, el desbordamiento debe ser atendido. En caso de desbordamiento, use el tipo de datos long long int o use una string como multiplicación si aún ocurre el desbordamiento. Las posibilidades de una colisión en el hash de mitad de cuadrado son bajas, no obsoletas. Entonces, en las posibilidades, si ocurre una colisión, se maneja usando algún mapa hash.

Ejemplo :

Supongamos que se toma una semilla de 4 dígitos. semilla = 4765
Por lo tanto, el cuadrado de la semilla es = 4765 * 4765 = 22705225
Ahora, de este número de 8 dígitos, se extraen cuatro dígitos (digamos, los cuatro del medio).
Entonces, el nuevo valor semilla se convierte en semilla = 7052
Ahora, el cuadrado de esta nueva semilla es = 7052 * 7052 = 49730704
Nuevamente, se extrae el mismo conjunto de 4 dígitos.
Entonces, el nuevo valor semilla se convierte en seed = 7307
.
.
.
.
Este proceso se repite tantas veces como clave se requiera.

La técnica del cuadrado medio toma un cierto número de dígitos del cuadrado de un número. Este número extraído es un número pseudoaleatorio, que se puede utilizar como clave para el hashing.

Algoritmo:

1. Elija un valor inicial. Este es un paso importante ya que para el mismo valor inicial, se genera la misma secuencia de números aleatorios.
2. Tome el cuadrado del valor semilla y actualice la semilla por un cierto número de dígitos que ocurren en el cuadrado. Nota : Cuanto mayor sea el número de dígitos, mayor será la aleatoriedad.
3. Devuelve la llave.

A continuación se muestra la implementación del algoritmo anterior:

// 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;
}

56002270
25424515

Nota: La salida cambiará según la fecha y la hora.