Skip to content

HashTable

Jump to bottom
Alegruz edited this page Sep 9, 2021 · 13 revisions

cave::HashTable

  • defined in module cave.Core.Containers.HashTable

The class cave::HashTable is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. Keys with the same hash code appear in the same bucket. This allows fast access to individual elements, since once the hash is computed, it refers to the exact bucket the element is placed into.

Member functions

Name Description
(constructor) constructs the cave::HashTable
(public member function)
(destructor) destroys the cave::HashTable
(public member function)
operator= assigns values to the container
(public member function)
GetMemoryPool returns the associated allocator
(public member function)
  • Capacity
Name Description
IsEmpty checks whether the container is empty
(public member function)
GetSize returns the number of elements
(public member function)
GetMaxSize returns the maximum possible number of elements
(public member function)
  • Modifier
Name Description
Clear clears the contents
(public member function)
Insert inserts elements or nodes
(public member function)
Erase erases elements
(public member function)
  • Lookup
Name Description
At access specified element with bounds checking
(public member function)
operator[] access or insert specified element
(public member function)
Find finds element with specific key
(public member function)
Contains checks if the container contains element with specific key
(public member function)
  • Bucket interface
Name Description
GetBucketCount returns the number of buckets
(public member function)
GetBucketSize returns the number of elements in specific bucket
(public member function)

  • Hash policy

  • Observers

  • Non-member functions

Constructor

HashTable(size_t elementSize);									(1)
explicit HashTable(size_t elementSize, MemoryPool& pool);					(1)
explicit HashTable(size_t elementSize, Hash& hash);						(1)
explicit HashTable(size_t elementSize, Hash& hash, MemoryPool& pool);				(1)
explicit HashTable(size_t elementSize, size_t bucketCount);					(1)
explicit HashTable(size_t elementSize, size_t bucketCount, Hash& hash);				(1)
explicit HashTable(size_t elementSize, size_t bucketCount, MemoryPool& pool);			(1)
explicit HashTable(size_t elementSize, size_t bucketCount, Hash& hash, MemoryPool& pool);	(1)
explicit HashTable(const HashTable& other);							(2)
explicit HashTable(const HashTable& other, MemoryPool& pool);					(2)
explicit HashTable(HashTable&& other);								(3)
explicit HashTable(HashTable&& other, MemoryPool& pool);					(3)

Constructs new container from a variety of data sources. Optionally uses user supplied elementSize as a size of element to store in bytes, bucketCount as a minimal number of buckets to create, hash as the hash function and pool as the allocator.

  1. Constructs empty container.
  2. Copy constructor. Constructs the container with the copy of the contents of other, copies the size of the element in bytes, the number of buckets, the number of elements, and the hash function as well. If pool is not provided, allocator is obtained by copy-construction from the allocator belonging to the other.
  3. Move constructor. Constructs the container with the contents of other using move semantics. If pool is not provided, allocator is obtained by move-construction from the allocator belonging to other.

Paramters

Parameters Description
pool allocator to use for all memory allocations of this container
elementSize size of the element in bytes
bucketCount minimal number of buckets to use on initialization. If it is not specified, implementation-defined default value is used
hash hash function to use
other another container to be used as source to initialize the elements of the container with

Complexity

  1. Constant
  2. Linear in size of other
  3. Constant

Example

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Constructor Test====");
	{
		HashTable hashTable1(sizeof(int32_t));
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #1 Success");

		MemoryPool temp(1024);
		HashTable hashTable2(sizeof(int32_t), temp);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #2 Success");

		Hash tHash(eHashId::NORMAL_REPRESENTATION);
		HashTable hashTable3(sizeof(int32_t), tHash);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #3 Success");

		HashTable hashTable4(sizeof(int32_t), tHash, temp);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #4 Success");

		HashTable hashTable5(sizeof(int32_t), gPrimeNumberArray[20]);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #5 Success");

		HashTable hashTable6(sizeof(int32_t), gPrimeNumberArray[30], tHash);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #6 Success");

		HashTable hashTable7(sizeof(int32_t), gPrimeNumberArray[30], temp);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #7 Success");

		HashTable hashTable8(sizeof(int32_t), gPrimeNumberArray[40], tHash, temp);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #8 Success");

		HashTable hashTable9(hashTable1);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #9 Success");

		HashTable hashTable10(hashTable1, temp);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #10 Success");

		HashTable hashTable11(std::move(hashTable9));
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #11 Success");

		HashTable hashTable12(std::move(hashTable11), temp);
		LOGD(eLogChannel::CORE_CONTAINER, "\tConstructor #12 Success");
	}
	return 0;
}

Output:

Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:536 :	====Constructor Test====
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:539 :		Constructor #1 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:543 :		Constructor #2 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:547 :		Constructor #3 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:550 :		Constructor #4 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:553 :		Constructor #5 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:556 :		Constructor #6 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:559 :		Constructor #7 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:562 :		Constructor #8 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:565 :		Constructor #9 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:568 :		Constructor #10 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:571 :		Constructor #11 Success
Core/Containers/...\Core\Public\Containers\HashTable.ixx/Constructor/line:574 :		Constructor #12 Success
...

cave::HashTable::operator=

HashTable& operator=(const HashTable& other);	(1)
HashTable& operator=(HashTable&& other);	(2)

Replaces the contents of the container.

  1. Copy assignment operator. Replaces the contents with a copy of the contents of other.
  2. Move assignment operator. Replaces the contents with those of other using move semantics (i.e. the data in other is moved from other into this container). other is in a valid but unspecified state afterwards.

Parameters

Parameters Description
other another container to use as data source

Return value

*this

Complexity

  1. Linear in size of *this and other.
  2. Linear in size of *this.

Example

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Assignment Operator Test====");
	{
		HashTable copiedHashTable(sizeof(int32_t));
		HashTable movedHashTable(sizeof(int32_t));
		HashTable hashTable1(sizeof(int32_t));

		copiedHashTable = hashTable1;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #1 Success");

		MemoryPool temp(1024);
		HashTable hashTable2(sizeof(int32_t), temp);
		copiedHashTable = hashTable2;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #2 Success");

		Hash tHash(eHashId::NORMAL_REPRESENTATION);
		HashTable hashTable3(sizeof(int32_t), tHash);
		copiedHashTable = hashTable3;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #3 Success");

		HashTable hashTable4(sizeof(int32_t), tHash, temp);
		copiedHashTable = hashTable4;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #4 Success");

		HashTable hashTable5(sizeof(int32_t), gPrimeNumberArray[20]);
		copiedHashTable = hashTable5;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #5 Success");

		HashTable hashTable6(sizeof(int32_t), gPrimeNumberArray[30], tHash);
		copiedHashTable = hashTable6;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #6 Success");

		HashTable hashTable7(sizeof(int32_t), gPrimeNumberArray[30], temp);
		copiedHashTable = hashTable7;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #7 Success");

		HashTable hashTable8(sizeof(int32_t), gPrimeNumberArray[40], tHash, temp);
		copiedHashTable = hashTable8;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #8 Success");

		HashTable hashTable9(hashTable1);
		copiedHashTable = hashTable9;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #9 Success");

		HashTable hashTable10(hashTable1, temp);
		copiedHashTable = hashTable10;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #10 Success");

		HashTable hashTable11(std::move(hashTable9));
		copiedHashTable = hashTable11;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #11 Success");

		HashTable hashTable12(std::move(hashTable11), temp);
		copiedHashTable = hashTable12;
		movedHashTable = std::move(copiedHashTable);
		LOGD(eLogChannel::CORE_CONTAINER, "\tAssignment Operator #12 Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:580 :	====Assignment Operator Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:588 :		Assignment Operator #1 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:594 :		Assignment Operator #2 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:600 :		Assignment Operator #3 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:605 :		Assignment Operator #4 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:610 :		Assignment Operator #5 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:615 :		Assignment Operator #6 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:620 :		Assignment Operator #7 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:625 :		Assignment Operator #8 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:630 :		Assignment Operator #9 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:635 :		Assignment Operator #10 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:640 :		Assignment Operator #11 Success
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/AssignmentOperator/line:645 :		Assignment Operator #12 Success

cave::HashTable::GetMemoryPool

constexpr MemoryPool& GetMemoryPool();
constexpr const MemoryPool& GetMemoryPool() const;

Returns the allocator associated with the container.

Parameters

(none)

Return value

The associated allocator.

Complexity

Constant

Iterators

Capacity

cave::HashTable::IsEmpty

[[nodiscard]] constexpr bool IsEmpty() const;
  • Checks if the container has no elements.

Parameters

(none)

Return value

true if the container is empty, false otherwise

Complexity

Constant.

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Capacity Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{
				numbers[index] = rand();
				indices[index] = index;
				hashTable.Insert(&indices[index], &numbers[index]);
				assert(!hashTable.IsEmpty());
				++index;
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				numbers[index] = 0;
				indices[index] = 0;
			}
		}

		LOGD(eLogChannel::CORE_CONTAINER, "\tCapacity Success");
	}

    return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Capacity/line:659 :	====Capacity Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Capacity/line:692 :		Capacity Success

cave::HashTable::GetSize

constexpr size_t GetSize() const;

Returns the number of elements in the container

Parameters

(none)

Return value

The number of elements in the container.

Complexity

Constant.

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Capacity Test====");
	{
		HashTable hashTable(sizeof(size_t));

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{
				numbers[index] = rand();
				indices[index] = index;
				hashTable.Insert(&indices[index], &numbers[index]);
				++index;
				assert(hashTable.GetSize() == index);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}

		LOGD(eLogChannel::CORE_CONTAINER, "\tCapacity Success");
	}

    return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Capacity/line:659 :	====Capacity Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Capacity/line:692 :		Capacity Success

cave::HashTable::GetMaxSize

constexpr size_t GetMaxSize() const;

Returns the maximum number of elements the container is able to hold due to system or library implementation limitations.

Parameters

(none)

Return value

Maximum number of elements.

Complexity

Constant.

Modifiers

cave::HashTable::Clear

void Clear();

Erases all elements from the container. After this call, GetSize() returns zero.

Invalidates all void pointers referring to contained elements.

Parameters

(none)

Return value

(none)

Complexity

Linear in the size of the container, i.e., the number of elements.

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Modifiers Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{

				numbers[index] = rand();
				indices[index] = index;

				if (numbers[index] % 3 == 0)
				{
					hashTable.Insert(&indices[index], &numbers[index]);
				}
				else if (numbers[index] % 3 == 1)
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(pair);
				}
				else
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(std::move(pair));
				}
				assert(!hashTable.IsEmpty());
				++index;
				assert(hashTable.GetSize() == index);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}
		hashTable.Clear();
		assert(hashTable.GetSize() == 0);
		assert(hashTable.IsEmpty());

		LOGD(eLogChannel::CORE_CONTAINER, "\tModifiers Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Modifiers/line:698 :	====Modifiers Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Modifiers/line:749 :		Modifiers Success

cave::HashTable::Insert

bool Insert(void* key, void* value);	(1)
bool Insert(const Pair& pair);		(2)
bool Insert(Pair&& pair);		(3)

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

  1. Inserts key and value.
  2. Inserts key and value.
  3. Inserts key and value.

Parameters

Parameters Description
key element key to use for insertion
value element value to insert
pair pair with key and value to insert

Return value

true if insertion succeeds, false when insertion fails.

Complexity

Average case: O(1), worst case O(GetSize())

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Modifiers Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{

				numbers[index] = rand();
				indices[index] = index;

				if (numbers[index] % 3 == 0)
				{
					hashTable.Insert(&indices[index], &numbers[index]);
				}
				else if (numbers[index] % 3 == 1)
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(pair);
				}
				else
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(std::move(pair));
				}
				assert(!hashTable.IsEmpty());
				++index;
				assert(hashTable.GetSize() == index);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}
		hashTable.Clear();
		assert(hashTable.GetSize() == 0);
		assert(hashTable.IsEmpty());

		LOGD(eLogChannel::CORE_CONTAINER, "\tModifiers Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Modifiers/line:698 :	====Modifiers Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Modifiers/line:749 :		Modifiers Success

cave::HashTable::Erase

bool Erase(const void* key);

Removes element (if one exists) with the key equivalent to key from the container.

References to the erased elements are invalidated. Other references are not invalidated.

The order of the elements that are not erased is preserved. (This makes it possible to erase individual elements while iterating through the container.)

Parameters

Parameters Description
key key value of the elements to remove

Return value

true if removal succeeds, false when removal fails.

Complexity

Average case: O(1), worst case O(GetSize())

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Modifiers Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{

				numbers[index] = rand();
				indices[index] = index;

				if (numbers[index] % 3 == 0)
				{
					hashTable.Insert(&indices[index], &numbers[index]);
				}
				else if (numbers[index] % 3 == 1)
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(pair);
				}
				else
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(std::move(pair));
				}
				assert(!hashTable.IsEmpty());
				++index;
				assert(hashTable.GetSize() == index);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}
		hashTable.Clear();
		assert(hashTable.GetSize() == 0);
		assert(hashTable.IsEmpty());

		LOGD(eLogChannel::CORE_CONTAINER, "\tModifiers Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Modifiers/line:698 :	====Modifiers Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Modifiers/line:749 :		Modifiers Success

Lookup

cave::HashTable::At

void* At(const void* key);		(1)
const void* At(const void* key) const;	(2)

Returns a reference to the mapped value of the element with key equivalent to key. If no such element exists, returns nullptr.

Parameters

Parameters Description
key the key of the element to find

Return value

Pointer to the mapped value of the requested element. nullptr when there is no element.

Complexity

Average case: O(1), worst case O(GetSize())

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Lookup Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{

				numbers[index] = rand();
				indices[index] = index;

				if (numbers[index] % 3 == 0)
				{
					hashTable.Insert(&indices[index], &numbers[index]);
				}
				else if (numbers[index] % 3 == 1)
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(pair);
				}
				else
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(std::move(pair));
				}
				assert(!hashTable.IsEmpty());
				++index;
				assert(hashTable.GetSize() == index);
				assert(hashTable.Find(&indices[index - 1]) == &numbers[index - 1]);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				assert(hashTable.Find(&indices[index]) == nullptr);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}
		hashTable.Clear();
		assert(hashTable.GetSize() == 0);
		assert(hashTable.IsEmpty());

		LOGD(eLogChannel::CORE_CONTAINER, "\tLookup Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:755 :	====Lookup Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:810 :		Lookup Success

cave::HashTable::operator[]

void* operator[](void* key);

Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.

Parameters

Parameters Description
key the key of the element to find

Return value

Pointer to the mapped value of the new element if no element with key key existed. Otherwise a pointer to the mapped value of the existing element whose key is equivalent to key.

Complexity

Average case: O(1), worst case O(GetSize())

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Lookup Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{

				numbers[index] = rand();
				indices[index] = index;

				if (numbers[index] % 3 == 0)
				{
					hashTable.Insert(&indices[index], &numbers[index]);
				}
				else if (numbers[index] % 3 == 1)
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(pair);
				}
				else
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(std::move(pair));
				}
				assert(!hashTable.IsEmpty());
				++index;
				assert(hashTable.GetSize() == index);
				assert(hashTable.Find(&indices[index - 1]) == &numbers[index - 1]);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				assert(hashTable.Find(&indices[index]) == nullptr);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}
		hashTable.Clear();
		assert(hashTable.GetSize() == 0);
		assert(hashTable.IsEmpty());

		LOGD(eLogChannel::CORE_CONTAINER, "\tLookup Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:755 :	====Lookup Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:810 :		Lookup Success

cave::HashTable::Find

void* Find(const void* key);			(1)
const void* Find(const void* key) const;	(2)

Finds an element with key equivalent to key.

Parameters

Parameters Description
key key value of the element to search for

Return value

Pointer to an element with key equivalent to key. If no such element is found, nullptr is returned.

Complexity

Average case: O(1), worst case O(GetSize())

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Lookup Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{

				numbers[index] = rand();
				indices[index] = index;

				if (numbers[index] % 3 == 0)
				{
					hashTable.Insert(&indices[index], &numbers[index]);
				}
				else if (numbers[index] % 3 == 1)
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(pair);
				}
				else
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(std::move(pair));
				}
				assert(!hashTable.IsEmpty());
				++index;
				assert(hashTable.GetSize() == index);
				assert(hashTable.Find(&indices[index - 1]) == &numbers[index - 1]);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				assert(hashTable.Find(&indices[index]) == nullptr);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}
		hashTable.Clear();
		assert(hashTable.GetSize() == 0);
		assert(hashTable.IsEmpty());

		LOGD(eLogChannel::CORE_CONTAINER, "\tLookup Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:755 :	====Lookup Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:810 :		Lookup Success

cave::HashTable::Contains

constexpr bool Contains(const void* key) const;

Checks if there is an element with key equivalent to key in the container.

Parameters

Parameters Description
key key value of the element to search for

Return value

true if there is such an element, otherwise false.

Complexity

Average case: O(1), worst case O(GetSize())

Example

  • Samples/Main.cpp
#include "Utils/Crt.h"

#include "CoreTypes.h"
#include "Debug/Log.h"

import cave.Core.Containers.Hash;
import cave.Core.Containers.HashTable;

int main()
{
	LOGD(eLogChannel::CORE_CONTAINER, "====Lookup Test====");
	{
		HashTable hashTable(sizeof(size_t));
		assert(hashTable.IsEmpty());

		size_t indices[256] = { 0, };
		int numbers[256] = { 0, };

		size_t index = 0;
		for (size_t i = 0; i < 131072; ++i)
		{
			if (index == 0 || index < 256 && rand() % 5 != 0)
			{

				numbers[index] = rand();
				indices[index] = index;

				if (numbers[index] % 3 == 0)
				{
					hashTable.Insert(&indices[index], &numbers[index]);
				}
				else if (numbers[index] % 3 == 1)
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(pair);
				}
				else
				{
					Pair pair(&indices[index], &numbers[index]);
					hashTable.Insert(std::move(pair));
				}
				assert(!hashTable.IsEmpty());
				++index;
				assert(hashTable.GetSize() == index);
				assert(hashTable.Find(&indices[index - 1]) == &numbers[index - 1]);
			}
			else
			{
				--index;
				hashTable.Erase(&indices[index]);
				assert(hashTable.Find(&indices[index]) == nullptr);
				numbers[index] = 0;
				indices[index] = 0;
				assert(hashTable.GetSize() == index);
			}
		}
		hashTable.Clear();
		assert(hashTable.GetSize() == 0);
		assert(hashTable.IsEmpty());

		LOGD(eLogChannel::CORE_CONTAINER, "\tLookup Success");
	}

	return 0;
}

Possible output:

Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:755 :	====Lookup Test====
Core/Containers/D:\SWTube\SpecialProject\Darkest-Cave\CaveEngine\Core\Public\Containers\HashTable.ixx/Lookup/line:810 :		Lookup Success

Bucket Interface

cave::HashTable::GetBucketCount

constexpr size_t GetBucketCount() const;

Returns the number of buckets in the container.

Parameters

(none)

Return value

The number of buckets in the container.

Complexity

Constant.

cave::HashTable::GetBucketSize

size_t GetBucketSize(size_t index) const;

Returns the number of elements in the bucket with index index.

Parameters

Parameters Description
index the index of the bucket to examine

Return value

The number of elements in the bucket index.

Complexity

Linear in the size of the bucket index.

Core

Physics

Clone this wiki locally