Better Implementation of Unordered Map

Secure Unordered Map from Collision Attacks:

The custom hash function can be integrated into the unordered map or other hash tables like gp_hash_table. Below is a better implementation of the unordered map which almost guarantees O(1) time for all operations like Insertion, deletion, etc.

C++

#include <bits/stdc++.h>

struct custom_hash {
    static uint64_t splitmix64(uint64_t x)
    {
        // Implementation of splitmix64
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM
            = std::chrono::steady_clock::now()
                  .time_since_epoch()
                  .count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = 2e5;

void insert_numbers(long long x)
{
    clock_t begin = clock();
    std::unordered_map<long long, int, custom_hash> numbers;

    for (int i = 1; i <= N; i++)
        numbers[i * x] = i;

    long long sum = 0;

    for (const auto& entry : numbers)
        sum += (entry.first / x) * entry.second;

    std::cout << "x = " << x << ": " << std::fixed
              << static_cast<double>(clock() - begin) / CLOCKS_PER_SEC
              << " seconds, sum = " << sum << "\n";
}

int main()
{
    insert_numbers(107897);
    insert_numbers(126271);

    return 0;
}

Java

import java.util.*;
import java.time.*;

public class Main {
    // Define the size of the numbers
    static final int N = 200000;

    // Custom hash function
    static class CustomHash {
        long splitmix64(long x) {
            // Implementation of splitmix64
            x += 0x9e3779b97f4a7c15L;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9L;
            x = (x ^ (x >> 27)) * 0x94d049bb133111ebL;
            return x ^ (x >> 31);
        }

        public int hashCode(long x) {
            long FIXED_RANDOM = Instant.now().toEpochMilli();
            return (int) splitmix64(x + FIXED_RANDOM);
        }
    }

    // Function to insert numbers and calculate the sum
    static void insertNumbers(long x) {
        long begin = System.currentTimeMillis();
        HashMap<Long, Integer> numbers = new HashMap<>(N, 1.0f);

        for (int i = 1; i <= N; i++)
            numbers.put(i * x, i);

        long sum = 0;

        for (Map.Entry<Long, Integer> entry : numbers.entrySet())
            sum += (entry.getKey() / x) * entry.getValue();

        System.out.printf("x = %d: %.2f seconds, sum = %d\n", x, (System.currentTimeMillis() - begin) / 1000.0, sum);
    }

    // Main function
    public static void main(String[] args) {
        insertNumbers(107897);
        insertNumbers(126271);
    }
}

Python

import time
import hashlib

class CustomHash:
    @staticmethod
    def splitmix64(x):
        # Implementation of splitmix64
        x += 0x9e3779b97f4a7c15
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb
        return x ^ (x >> 31)

    def __call__(self, x):
        # FIXED_RANDOM is set to the current time since epoch
        FIXED_RANDOM = int(time.time() * 1000)
        return self.splitmix64(x + FIXED_RANDOM)

def insert_numbers(x):
    begin = time.process_time()  # or time.perf_counter()
    numbers = {}
    custom_hash = CustomHash()

    for i in range(1, N + 1):
        numbers[i * x] = i

    sum_val = 0

    for key, value in numbers.items():
        sum_val += (key // x) * value

    print(f"x = {x}: {time.process_time() - begin:.6f} seconds, sum = {sum_val}")

if __name__ == "__main__":
    N = int(2e5)
    insert_numbers(107897)
    insert_numbers(126271)

JavaScript

class CustomHash {
    static splitmix64(x) {
        // Implementation of splitmix64
        x += 0x9e3779b97f4a7c15n;
        x = (x ^ (x >> 30n)) * 0xbf58476d1ce4e5b9n;
        x = (x ^ (x >> 27n)) * 0x94d049bb133111ebn;
        return Number(x ^ (x >> 31n));
    }

    static customHash(x) {
        // FIXED_RANDOM is set to the current time since epoch
        const FIXED_RANDOM = Date.now();
        return this.splitmix64(BigInt(x) + BigInt(FIXED_RANDOM));
    }
}

function insertNumbers(x) {
    const begin = Date.now();
    const numbers = new Map();

    for (let i = 1; i <= N; i++) {
        numbers.set(BigInt(i) * BigInt(x), i);
    }

    let sum = 0n;

    for (const [key, value] of numbers) {
        sum += (key / BigInt(x)) * BigInt(value);
    }

    console.log(`x = ${x}: ${(Date.now() - begin) / 1000} seconds, sum = ${sum}`);
}

const N = 200000;
insertNumbers(107897);
insertNumbers(126271);

Output:

x = 107897: 0.068000 seconds, sum = 2666686666700000
x = 126271: 0.064000 seconds, sum = 2666686666700000

Optimization for Unordered Map O(1) operations

C++ provides convenient data structures like std::set and std::map, tree-based structures with operations taking O(log n) time. With C++11, hash-based alternatives were introduced: std::unordered_set and std::unordered_map. However, concerns arise regarding potential vulnerabilities and efficiency in real-world scenarios. In this article, we’re going to explore strategies to optimize unordered maps for O(1) operations and address security issues.

Table of Content

Implementation of Unordered Map
Understanding Vulnerabilities of Unordered Map
Vulnerable Implementation for Unordered Map
Secure Unordered Map from Collision Attacks
Better Implementation of Unordered Map

Better Implementation of Unordered Map

Optimization for Unordered Map O(1) operations

Similar Reads