Open Addressing Hash Table
A hash table implementation using open addressing. Uses a single overflow deque to store items that could not be stored within the main table (due to collisions).
Notice that the tests do not try to insert more than the capacity of the table, since that leads to extremely poor performance. You are encouraged to try that yourself to see just how quickly performance deteriorates when the table goes over capacity. Also notice the much better usage of available memory in the table (as long as a good hash function is used).
HashTable
The open addressing based hash table declaration. Same interface as the simple chaining hash table.
// OpenAddressHashTable.h #pragma once #include <array> #include <deque> #include <functional> #include <optional> #include <sstream> namespace csc280 { template <typename T, std::size_t B, typename Hash = std::hash<T>, typename Equals = std::equal_to<T>> class OpenAddressHashTable final { using Data = std::optional<T>; using Ptr = std::unique_ptr<Data>; using Array = std::array<Ptr, B>; using ArrayPtr = std::unique_ptr<Array>; using Deque = std::deque<T>; public: #include "private/OAIterator.h" using key_type = T; using value_type = T; using iterator = OAIterator<T, B, Hash, Equals>; using const_iterator = OAIterator<T, B, Hash, Equals>; OpenAddressHashTable() : buckets{ std::make_unique<Array>() } {} ~OpenAddressHashTable() = default; OpenAddressHashTable( const OpenAddressHashTable& ) = delete; OpenAddressHashTable& operator=( const OpenAddressHashTable& rhs ) = delete; auto begin() const -> iterator; auto cbegin() const -> const_iterator { return begin(); } auto end() const -> iterator; auto cend() const -> const_iterator { return end(); } auto insert( T data ) -> iterator; template <typename... Args> iterator emplace( Args&&... args ) { return insert( { args } ); } auto erase( const T& data ) -> iterator; void clear(); auto find( const T& data ) const -> iterator; bool empty() const { return !count; } std::size_t size() const { return count; } std::size_t capacity() const { return B; } std::string getStats() const { return static_cast<std::string>( stats ); } private: #include "private/OAStats.h" std::size_t probe( const T& data, const std::size_t hashCode ) const; bool isEmpty( const std::size_t index ) const; auto findInOverflow( const T& data ) const -> typename Deque::const_iterator; auto addToOverflow( T&& data )->iterator; ArrayPtr buckets; Deque deque; mutable OAStats<B> stats; Hash hash; Equals equals; std::size_t count = 0; }; #include "private/OATImpl.h" }
Iterator
The iterator for the hash table. A bi-directional iterator just as with the simple chaining hash table implementation.
// private/OAIterator.h template <typename T, std::size_t B, typename Hash, typename Equals> struct OAIterator final { using difference_type = std::size_t; using value_type = T; using reference = T & ; using const_reference = const T&; using pointer = T * ; using const_pointer = const T*; using iterator_category = std::bidirectional_iterator_tag; OAIterator() = delete; OAIterator( const OAIterator& ) = default; OAIterator& operator++() { if ( biter == buckets->cend() && diter == deque->cend() ) return *this; if ( biter != buckets->cend() ) { ++biter; nextBucket(); return *this; } if ( diter != deque->cend() ) { ++diter; return *this; } return *this; } OAIterator& operator--() { if ( biter == buckets->cbegin() ) return *this; if ( biter == buckets->cend() ) { if ( diter == deque->cend() ) { auto iter = deque->cbegin(); std::advance( iter, deque->size() - 1 ); diter = iter; } --diter; return *this; } --biter; previousBucket(); return *this; } bool operator==( const OAIterator& rhs ) const { return buckets == rhs.buckets && deque == rhs.deque && biter == rhs.biter && diter == rhs.diter; } bool operator!=( const OAIterator& rhs ) const { return !operator==( rhs ); } const_reference operator*() const { return ( biter == buckets->cend() ) ? diter.operator*() : biter.operator*()->value(); } const_pointer operator->() const { return ( biter == buckets->cend() ) ? diter.operator->() : *(biter.operator->()->value); } private: explicit OAIterator( typename const ArrayPtr::pointer buckets, const Deque* deque ) : buckets{ buckets }, deque{ deque }, biter { buckets->cbegin() }, diter{ deque->cbegin() } {} static OAIterator createBegin( typename const ArrayPtr::pointer buckets, const Deque* deque ) { OAIterator iter{ buckets, deque }; iter.nextBucket(); return iter; } static OAIterator createEnd( typename const ArrayPtr::pointer buckets, const Deque* deque ) { OAIterator iter{ buckets, deque }; iter.biter = buckets->cend(); iter.diter = deque->cend(); return iter; } static OAIterator createBucket( typename const ArrayPtr::pointer buckets, const Deque* deque, const std::size_t index ) { OAIterator it{ buckets, deque }; std::advance( it.biter, index ); return it; } static OAIterator createOverflow( typename const ArrayPtr::pointer buckets, const Deque* deque, typename Deque::const_iterator iter ) { OAIterator it{ buckets, deque }; it.biter = buckets->cend(); it.diter = iter; return it; } void nextBucket() { while ( biter != buckets->cend() && !hasValue( biter ) ) ++biter; } void previousBucket() { while ( biter != buckets->cbegin() && !hasValue( biter ) ) --biter; } bool hasValue( const typename Array::const_iterator& iter ) { return *biter && biter->get()->has_value(); } typename const ArrayPtr::pointer buckets; const Deque* deque; typename Array::const_iterator biter; typename Deque::const_iterator diter; friend class OpenAddressHashTable<T, B, Hash, Equals>; };
Stats
A simple structure that captures storage statistics for the open addressing based hash table implementation. Note that the collision count is no longer a map, since there is no key-value mapping. Collisions are just the number of times a collision was encountered, leading to quadratic probing operations on the table to find the next potential bucket.
// private/OAStats.h template <int B> struct OAStats { operator std::string() const { std::ostringstream ss; ss << "{\n" << " \"bucketCount\": " << B << ",\n" << " \"occupiedBuckets\": " << occupied << ",\n" << " \"emptyBuckets\": " << ( B - occupied ) << ",\n" << " \"usePercentage\": " << percentage() << ",\n" << " \"collisions\": " << collisions << ",\n" << " \"overFlow\": " << overflow << "\n" << "}\n"; return ss.str(); } void clear() { occupied = 0; collisions = 0; overflow = 0; } float percentage() const { return 100.0f * ( occupied / float( B ) ); } std::size_t occupied = 0; std::size_t collisions = 0; std::size_t overflow = 0; };
Implementation
The private implementation header that implements the main hash table functions.
// private/OATImpl.h template <typename T, std::size_t B, typename Hash, typename Equals> auto OpenAddressHashTable<T, B, Hash, Equals>::begin() const -> iterator { return iterator::createBegin( buckets.get(), &deque ); } template <typename T, std::size_t B, typename Hash, typename Equals> auto OpenAddressHashTable<T, B, Hash, Equals>::end() const -> iterator { return iterator::createEnd( buckets.get(), &deque ); } template <typename T, std::size_t B, typename Hash, typename Equals> auto OpenAddressHashTable<T, B, Hash, Equals>::insert( T data ) -> iterator { if ( stats.occupied == B ) return addToOverflow( std::move( data ) ); const auto hashCode = hash( data ); auto index = probe( data, hashCode ); if ( index < B ) { if ( !isEmpty( index ) ) return iterator::createBucket( buckets.get(), &deque, index ); buckets->at( index ) = std::make_unique<Data>( Data{ std::move( data ) } ); ++count; ++stats.occupied; return iterator::createBucket( buckets.get(), &deque, index ); } return addToOverflow( std::move( data ) ); } template <typename T, std::size_t B, typename Hash, typename Equals> auto OpenAddressHashTable<T, B, Hash, Equals>::erase( const T& data ) -> iterator { auto iter = find( data ); if ( iter == end() ) return iter; --count; if ( iter.biter != buckets->cend() ) { auto i = buckets->begin(); std::advance( i, iter.biter - i ); i->get()->reset(); --stats.occupied; iter.previousBucket(); return iter; } --stats.overflow; auto ri = deque.erase( iter.diter ); return iterator::createOverflow( buckets.get(), &deque, ri ); } template <typename T, std::size_t B, typename Hash, typename Equals> void OpenAddressHashTable<T, B, Hash, Equals>::clear() { for ( auto iter = buckets->begin(); iter != buckets->end(); ++iter ) { iter->reset(); } deque.clear(); stats.clear(); count = 0; } template <typename T, std::size_t B, typename Hash, typename Equals> auto OpenAddressHashTable<T, B, Hash, Equals>::find( const T& data ) const -> iterator { const auto hasValue = [this, &data]( const std::size_t index ) -> bool { const auto optional = buckets->at( index ).get(); return ( optional->has_value() && equals( data, optional->value() ) ); }; const auto hashCode = hash( data ); auto index = hashCode % B; if ( !buckets->at( index ) ) return iterator::createEnd( buckets.get(), &deque ); if ( hasValue( index ) ) return iterator::createBucket( buckets.get(), &deque, index ); const auto initialIndex = index; std::size_t i = 0; while ( true ) { index = ( hashCode + ( ++i * i ) ) % B; if ( index == initialIndex ) { auto iter = findInOverflow( data ); return iterator::createOverflow( buckets.get(), &deque, iter ); } if ( !buckets->at( index ) ) return iterator::createEnd( buckets.get(), &deque ); if ( hasValue( index ) ) return iterator::createBucket( buckets.get(), &deque, index ); } } template <typename T, std::size_t B, typename Hash, typename Equals> std::size_t OpenAddressHashTable<T, B, Hash, Equals>::probe( const T& data, const std::size_t hashCode ) const { if ( stats.occupied == B ) return B; auto index = hashCode % B; const auto initialIndex = index; std::size_t i = 0; while ( !isEmpty( index ) ) { if ( equals( data, buckets->at( index )->value() ) ) return index; ++stats.collisions; index = ( hashCode + ( ++i * i ) ) % B; if ( index == initialIndex ) return B; } return index; } template <typename T, std::size_t B, typename Hash, typename Equals> bool OpenAddressHashTable<T, B, Hash, Equals>::isEmpty( const std::size_t index ) const { return ( !buckets->at( index ) ) ? true : !buckets->at( index )->has_value(); } template<typename T, std::size_t B, typename Hash, typename Equals> auto OpenAddressHashTable<T, B, Hash, Equals>::findInOverflow( const T & data ) const -> typename Deque::const_iterator { for ( auto iter = deque.cbegin(); iter != deque.cend(); ++iter ) { if ( equals( *iter, data ) ) return iter; } return deque.cend(); } template <typename T, std::size_t B, typename Hash, typename Equals> auto OpenAddressHashTable<T, B, Hash, Equals>::addToOverflow( T&& data ) -> iterator { auto iter = findInOverflow( data ); if ( iter == deque.cend() ) { deque.push_back( std::move( data ) ); ++count; ++stats.overflow; iter = deque.cbegin(); std::advance( iter, deque.size() - 1 ); } return iterator::createOverflow( buckets.get(), &deque, iter ); }
Test1
// OpenAddressSet.cpp #include "catch.hpp" #include "../main/Book.h" #include "../main/OpenAddressHashTable.h" SCENARIO( "Hashing same book in stages using OpenAddressHashTable" ) { GIVEN( "An unordered_hashTable of book instances" ) { using HashTable = csc280::OpenAddressHashTable<csc280::Book, 10>; HashTable hashTable; THEN( "Changing book properties makes book invisible" ) { csc280::Book book; hashTable.insert( book ); REQUIRE( 1 == hashTable.size() ); book.setTitle( "Something" ); REQUIRE( hashTable.find( book ) == hashTable.cend() ); hashTable.clear(); REQUIRE( hashTable.empty() ); hashTable.insert( book ); REQUIRE( 1 == hashTable.size() ); book.setTitle( "Something" ); REQUIRE( hashTable.find( book ) != hashTable.cend() ); hashTable.clear(); hashTable.insert( book ); book.setSubtitle( "Else" ); REQUIRE( hashTable.find( book ) == hashTable.cend() ); } AND_THEN( "Adding same book with different information creates copies" ) { csc280::Book book; book.setTitle( "Something" ); hashTable.insert( book ); REQUIRE( 1 == hashTable.size() ); REQUIRE_FALSE( hashTable.find( book ) == hashTable.cend() ); hashTable.insert( book ); REQUIRE( 1 == hashTable.size() ); book.setSubtitle( "Else" ); hashTable.insert( book ); REQUIRE( 2 == hashTable.size() ); } } GIVEN( "An unordered_hashTable of book pointers" ) { using HashTable = csc280::OpenAddressHashTable<csc280::Book*, 10>; HashTable hashTable; THEN( "Changing book properties does not affect visibility" ) { csc280::Book book; hashTable.insert( &book ); REQUIRE( 1 == hashTable.size() ); book.setTitle( "Something" ); REQUIRE_FALSE( hashTable.find( &book ) == hashTable.cend() ); } AND_THEN( "Copy of book is not visisble" ) { csc280::Book book; book.setTitle( "Something" ); hashTable.insert( &book ); REQUIRE( 1 == hashTable.size() ); csc280::Book other = book; REQUIRE( hashTable.find( &other ) == hashTable.cend() ); } } GIVEN( "An unordered_hashTable of book pointers with custom hash function" ) { using HashTable = csc280::OpenAddressHashTable<csc280::Book*, 10, csc280::BookPointerHash, csc280::BookPointerEquals>; HashTable hashTable; THEN( "Changing book properties affects visibility" ) { csc280::Book book; hashTable.insert( &book ); REQUIRE( 1 == hashTable.size() ); book.setTitle( "Something" ); REQUIRE( hashTable.find( &book ) == hashTable.cend() ); } AND_THEN( "Copy of book is visisble" ) { csc280::Book book; book.setTitle( "Something" ); hashTable.insert( &book ); REQUIRE( 1 == hashTable.size() ); csc280::Book other = book; REQUIRE_FALSE( hashTable.find( &other ) == hashTable.cend() ); } } }
Test2
Test suite with more comprehensive tests of the hash table functions. Also includes similar tests with varying sizes and output of the time to create those tables. Compare the results with the results for the simple chained hash table implementation. Notice the big difference in performance as well as better memory utilisation.
// OpenAddressHashTable.cpp #include "catch.hpp" #include "functions.h" #include "../main/OpenAddressHashTable.h" #include <algorithm> #include <chrono> #include <cstdlib> #include <ctime> #include <iostream> SCENARIO( "OpenAddress hash table operations with integers" ) { GIVEN( "A open address hash table of integers" ) { constexpr std::size_t size = 100; csc280::OpenAddressHashTable<uint32_t, size> hash; REQUIRE( size == hash.capacity() ); WHEN( "Adding same number of random numbers as table size" ) { std::srand( static_cast<std::size_t>( std::time( nullptr ) ) ); for ( std::size_t i = 0; i < size; ++i ) { auto value = std::rand(); while ( hash.find( value ) != hash.cend() ) value = std::rand(); hash.insert( value ); } THEN( "Iterating all stored numbers" ) { auto counter = 0; for ( auto iter = hash.cbegin(); iter != hash.cend(); ++iter ) { auto value = *iter; ++counter; } REQUIRE( counter == size ); } AND_THEN( "Can iterate in reverse from middle" ) { auto iter = hash.cbegin(); std::advance( iter, 10 ); for ( std::size_t i = 0; i < 10; ++i ) { --iter; auto value = *iter; } } AND_THEN( "Removing elements one-by-one" ) { auto count = hash.size(); for ( std::size_t i = 0; i < size; ++i ) { const auto iter = hash.cbegin(); auto value = *iter; const auto del = hash.erase( value ); --count; if ( i == size - 1 ) REQUIRE( del == hash.cend() ); else REQUIRE( del != hash.cend() ); REQUIRE( hash.size() == count ); REQUIRE( hash.find( value ) == hash.cend() ); } REQUIRE( hash.empty() ); } } } csc280::test::ofs.flush(); } SCENARIO( "Generating statistics for open address hash tables with varying capacity" ) { using std::chrono::duration_cast; using std::chrono::high_resolution_clock; using std::chrono::microseconds; GIVEN( "A hash table with capacity 100" ) { constexpr std::size_t size = 100; csc280::OpenAddressHashTable<uint32_t, size> hash; WHEN( "Adding same number of random numbers as table size" ) { const auto t1 = high_resolution_clock::now(); std::srand( static_cast<std::size_t>( std::time( nullptr ) ) ); for ( std::size_t i = 0; i < size; ++i ) { auto value = std::rand(); while ( hash.find( value ) != hash.cend() ) value = std::rand(); hash.insert( value ); } csc280::test::ofs << "OpenAddress hash table stats for capacity 100\n" << hash.getStats(); const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to add " << size << " numbers to open address hash table: " << duration << " microseconds\n"; } } GIVEN( "A hash table with capacity 500" ) { constexpr std::size_t size = 500; csc280::OpenAddressHashTable<uint32_t, size> hash; WHEN( "Adding same number of random numbers as table size" ) { const auto t1 = high_resolution_clock::now(); std::srand( static_cast<std::size_t>( std::time( nullptr ) ) ); for ( std::size_t i = 0; i < size; ++i ) { auto value = std::rand(); while ( hash.find( value ) != hash.cend() ) value = std::rand(); hash.insert( value ); } csc280::test::ofs << "OpenAddress hash table stats for capacity 500\n" << hash.getStats(); const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to add " << size << " numbers to open address hash table: " << duration << " microseconds\n"; } } GIVEN( "A hash table with capacity 1000" ) { constexpr std::size_t size = 1000; csc280::OpenAddressHashTable<uint32_t, size> hash; WHEN( "Adding same number of random numbers as table size" ) { const auto t1 = high_resolution_clock::now(); std::srand( static_cast<std::size_t>( std::time( nullptr ) ) ); for ( std::size_t i = 0; i < size; ++i ) { auto value = std::rand(); while ( hash.find( value ) != hash.cend() ) value = std::rand(); hash.insert( value ); } csc280::test::ofs << "OpenAddress hash table stats for capacity 1000\n" << hash.getStats(); const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to add " << size << " numbers to open address hash table: " << duration << " microseconds\n"; } } GIVEN( "A hash table with capacity 5000" ) { constexpr std::size_t size = 5000; csc280::OpenAddressHashTable<uint32_t, size> hash; WHEN( "Adding same number of random numbers as table size" ) { const auto t1 = high_resolution_clock::now(); std::srand( static_cast<std::size_t>( std::time( nullptr ) ) ); for ( std::size_t i = 0; i < size; ++i ) { auto value = std::rand(); while ( hash.find( value ) != hash.cend() ) value = std::rand(); hash.insert( value ); } csc280::test::ofs << "OpenAddress hash table stats for capacity 5000\n" << hash.getStats(); const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to add " << size << " numbers to open address hash table: " << duration << " microseconds\n"; } } GIVEN( "A hash table with capacity 10000" ) { constexpr std::size_t size = 10000; csc280::OpenAddressHashTable<uint32_t, size> hash; WHEN( "Adding same number of random numbers as table size" ) { const auto t1 = high_resolution_clock::now(); std::srand( static_cast<std::size_t>( std::time( nullptr ) ) ); for ( std::size_t i = 0; i < size; ++i ) { auto value = std::rand(); while ( hash.find( value ) != hash.cend() ) value = std::rand(); hash.insert( value ); } csc280::test::ofs << "OpenAddress hash table stats for capacity 10000\n" << hash.getStats(); const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to add " << size << " numbers to open address hash table: " << duration << " microseconds\n"; } } GIVEN( "A hash table of strings with capacity 10000" ) { constexpr std::size_t size = 10000; csc280::OpenAddressHashTable<std::string, size> hash; WHEN( "Adding same number of random strings as table size" ) { const auto t1 = high_resolution_clock::now(); for ( std::size_t i = 0; i < size; ++i ) { auto value = csc280::test::generateRandomString(); while ( hash.find( value ) != hash.cend() ) value = csc280::test::generateRandomString(); hash.insert( std::move( value ) ); } csc280::test::ofs << "OpenAddress hash table of strings stats for capacity 10000\n" << hash.getStats(); const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to add " << size << " strings to open address hash table: " << duration << " microseconds\n"; } AND_WHEN( "Finding each string added to table" ) { std::vector<std::string> values; values.reserve( size ); for ( std::size_t i = 0; i < size; ++i ) { auto value = csc280::test::generateRandomString(); while ( hash.find( value ) != hash.cend() ) value = csc280::test::generateRandomString(); values.push_back( value ); hash.insert( std::move( value ) ); } const auto t1 = high_resolution_clock::now(); const auto iter = hash.cend(); for ( const auto& value : values ) { REQUIRE( hash.find( value ) != iter ); } const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to find " << size << " strings in open address hash table: " << duration << " microseconds\n"; } AND_WHEN( "Finding each string added to table of double capacity" ) { std::vector<std::string> values; values.reserve( size / 2 ); for ( std::size_t i = 0; i < size / 2; ++i ) { auto value = csc280::test::generateRandomString(); while ( hash.find( value ) != hash.cend() ) value = csc280::test::generateRandomString(); values.push_back( value ); hash.insert( std::move( value ) ); } const auto t1 = high_resolution_clock::now(); const auto iter = hash.cend(); for ( const auto& value : values ) { REQUIRE( hash.find( value ) != iter ); } const auto t2 = high_resolution_clock::now(); const auto duration = duration_cast<microseconds>( t2 - t1 ).count(); std::cout << "Time to find " << size / 2 << " strings in open address hash table of capacity " << size << ": " << duration << " microseconds\n"; } } csc280::test::ofs.flush(); }