integer_modulo_hash.cpp

#include <string>
#include <cstring>
#include <filesystem>
#include <string>
#include <iostream>
#include <regex>
#include <vector>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>

using namespace std::chrono;

struct ChunkCache {
	struct Slot {
		size_t hash = 0;
		size_t chunk = 0;
	};

	size_t count = 0;
	size_t size = 0;
	Slot* slots = nullptr;

	ChunkCache(size_t amount): size(amount), slots(new Slot[amount]()) {

	}

	void expand() {
		const size_t oldSize = size;
		const size_t newSize = size * 3;
		Slot* oldSlots = slots;
		Slot* newBuf = new Slot[newSize]();
		size = newSize;
		count = 0;
		slots = newBuf;
		for (size_t i = 0; i < oldSize; ++i)
		{
			insert(oldSlots[i].hash, oldSlots[i].chunk);
		}
		delete[] oldSlots;
	}

	size_t get(size_t hash) const {
		const size_t mySpot = hash % size;
		if (slots[mySpot].hash == hash) {
			return slots[mySpot].chunk;
		}
		if (slots[mySpot].hash == 0) {
			return 0;
		}
		size_t i = mySpot + 1;
		while (i <  size) {
			if (slots[i].hash == hash) {
				return slots[i].chunk;
			}
			if (slots[i].hash == 0) {
				return 0;
			}
			++i;
		}
		i = 0;
		while (i < mySpot) {
			if (slots[i].hash == hash) {
				return slots[i].chunk;
			}
			if (slots[i].hash == 0) {
				return 0;
			}
			++i;
		}
		return 0;
	}

	void insert(size_t hash, size_t chunk) {
		if (count >= size/2) {
			expand();
		}
		++count;
		const size_t mySpot = hash % size;
		if (slots[mySpot].hash == 0) {
			slots[mySpot].hash = hash;
			slots[mySpot].chunk = chunk;
			return;
		}
		size_t i = mySpot + 1;
		while (i <  size) {
			if (slots[i].hash == 0) {
				slots[i].hash = hash;
				slots[i].chunk = chunk;
				return;
			}
			++i;
		}
		i = 0;
		while (i < mySpot) {
			if (slots[i].hash == 0) {
				slots[i].hash = hash;
				slots[i].chunk = chunk;
				return;
			}
			++i;
		}
	}

	~ChunkCache() {
		delete[] slots;
	}
};


static void fillVecWithRand(std::vector<size_t>& nums, size_t amount) {
	while (amount--) {
		nums.push_back(rand());
	}
}

#define TEST_SIZE 40000000

static void mapTest() {
	std::unordered_map<size_t, size_t> myMap;
	std::vector<size_t> myNums;
	fillVecWithRand(myNums, TEST_SIZE);
	auto start = high_resolution_clock::now();
	for (const auto& num : myNums) {
		myMap.insert(std::make_pair(num, 4));
	}
	auto stop = high_resolution_clock::now();

	auto duration = duration_cast<microseconds>(stop - start);
	std::printf("Time taken %s %s %llu\n", "insert", __func__, duration.count());

	size_t adder = 0;
	auto start2 = high_resolution_clock::now();
	for (const auto& num : myNums) {
		adder += myMap.find(num)->second;
	}
	auto stop2 = high_resolution_clock::now();

	auto duration2 = duration_cast<microseconds>(stop2 - start2);
	std::printf("Time taken %s %s %llu\n", "find", __func__, duration2.count());
	std::printf("adder is %zu\n", adder);
}

static void cacheTest() {
	ChunkCache myMap(40000000);
	std::vector<size_t> myNums;
	fillVecWithRand(myNums, TEST_SIZE);
	auto start = high_resolution_clock::now();
	for (const auto& num : myNums) {
		myMap.insert(num, 4);
	}
	auto stop = high_resolution_clock::now();

	auto duration = duration_cast<microseconds>(stop - start);
	std::printf("Time taken %s %s %llu\n", "insert", __func__, duration.count());

	size_t adder = 0;
	auto start2 = high_resolution_clock::now();
	for (const auto& num : myNums) {
		adder += myMap.get(num);
	}
	auto stop2 = high_resolution_clock::now();

	auto duration2 = duration_cast<microseconds>(stop2 - start2);
	std::printf("Time taken %s %s %llu\n", "find", __func__, duration2.count());
	std::printf("adder is %zu\n", adder);
}

int main(int argc, char const *argv[])
{
	srand(time(nullptr));
	mapTest();
	cacheTest();
	return 0;
}