Overview

I coded & added Hashmap to Foxtrot Data Structure, replacing the STL unordered_map (preferrably all of its instances). This will mainly be used for resource management, which includes operations such as loading resource, accessing each of them with corresponding key, and deleting all if needed.

To-do list:

• Code Hashmap Data Structure, include it to Foxtrot DS.
• Performance test with example resources, compare with std::unordered_map.
• Embed FTDS::Hashmap to FoxtrotEngine
  • class ResourceManager (std::unordered_map instance)
    

Special thanks: JeongHwan Park (박정환)

Development Logs

2025.05.09. Friday

Task : Code Hashmap Data Structure, include it to Foxtrot DS.

I did some research on Hashmap data structures. The number of the resources should be static after the game is initialized, which means there is no occasion for a resource can be deleted or added. Thus, I thought implementing a Hash function to be used with FTDS::Array (an array wrapper DS in Foxtrot Engine) will be enough.
Due to the dangers of Hash Collision, however, I decided to go for HashMap, with Chaining technique features implemented. AVL tree was an another interesting candidate for solution, but I think despite the issues of collision, nearly O(1) of search time looks charming.

• Input to DS
  • A filename (const char*)
    
• Output from DS
  • A pointer to the resource
    

Code

Link to GitHub Repository

2025.05.12. Monday

Task: Performance test with example resources, compare with std::unordered_map.

Problem Occurred: The 1st implementation is even slower than std::unordered_map.

I ran a simple test which compares the amount of time cost for pair insertion.

Here are the input variables:

• key type: const char*
• value type: int
• insertion count: 10000
• Estimation unit: Nano-seconds

And here is the result!

…which is quite humiliating.
The Hashmap I implemented was even slower than the one from STL. After consulting with the online programming community, I gained an advice with a little bit of code review:

1) High possibilities of generated keys making collisions.
(Low quality hashing leads to longer delay of insertion & searching, due to the increasing length of linked list)

2) Chaining method to handle collision makes the work "heavy". Most of the optimal Hashmaps use the technique called Open Addressing (Linear/Quadratic Probing).

Recommendation: Consider referring to FNV-1a Hash function with keyword 'Open Addressing'.

Original comment in Korean, Thanks, JeongHwan Park (박정환)!

Now let’s get to work on FNV Hash function!
I implemented a Hash generator function based on FNV-1a (64 bits) hash function.

namespace FTDS
{
	uint64_t GenerateHash_fnv1a_64(const char* str) {
		const uint64_t FNV_PRIME = 0x100000001b3;
		const uint64_t OFFSET_BASIS = 0xcbf29ce484222325;

		uint64_t hash = OFFSET_BASIS;

		while (*str) {
			hash ^= (uint8_t)*str++;
			hash *= FNV_PRIME;
		}

		return hash;
	}

	// Simple HashFunction using modular operator.
	inline size_t HashFunction(const char* key, size_t arrSize)
	{
		return GenerateHash_fnv1a_64(key) % arrSize;
	}

    // The horrible, previous one!
	inline size_t Transform(const char* key)
	{
		size_t number = 0;
		while (*key)
			number += (*key++);
		return number;
	}
}

Link to GitHub Repository
And the result was…


Quite impressive, huh?
Now it costs only about 4% amount of time compared to the previous version (refer to the Transform(const char*) above).
Also, it’s even 65% faster than std::unordered_map!
Problem Solved! :]