/simd_hash_map

A c++ hash map/table which utilizes simd (specifically Intel x86 SSE/AVX)

Primary LanguageC++MIT LicenseMIT

simd_hash_map

REQUIREMENTS TO BUILD:

API as of 26 April 2019

  • Template Parameters
    • class Key
    • class T
    • class Hash = std::hash<Key>
    • class KeyEqual = std::equal_to<Key>
  • Member Types
    • key_type : Key
    • mapped_type : T
    • value_type : std::pair<const Key, T>
    • size_type : std::size_t
    • difference_type : std::ptrdiff_t
    • hasher : Hash
    • key_equal : KeyEqual
    • reference : value_type&
    • const_reference : const value_type&
    • pointer : value_type*
    • const_pointer : const value_type*
    • iterator : LegacyForwardIterator
    • const_iterator : Constant LegacyForwardIterator
  • Member Functions
    • (constructor)
    • (destructor)
  • Iterators
    • begin() and cbegin()
      • Returns an iterator to the beginning.
    • end() and cend()
      • Returns an iterator to the end.
  • Modifiers
    • template<typename Args...>
    • try_emplace(key_type, Args &&...)
      • return : std::pair<iterator, bool>
        • Iterator to key/value pair.
        • True: Emplaced with given Args.
        • False: Key already found in map, nothing occured.
      • Try to emplace key/value into the map.
      • If key is already present, nothing occurs
    • template<typename Args...>
    • emplace_or_assign(key_type, Args &&...)
      • return : std::pair<iterator, bool>
        • Iterator to key/value pair.
        • True: Emplaced with given key and Args.
        • False: Key already found in map, new value assigned.
      • Emplace key/value into the map.
    • erase(key_type)
      • return : bool
        • True: Key found, value_type erased
        • False: Key not found, nothing occured
      • Erase key/value with given key.
  • Lookup
    • find(key_type)
      • return : std::optional<iterator>
        • Optional contains iterator if key was successfully found.
        • Iterator to key/value pair.
      • find key/value pair with given key
    • contains(key_type)
      • return : bool
        • True: Map conatins key.
        • False: Map does not contain key.
      • Check if map conatins key/value pair with given key.
    • clear()
      • return : void
      • Clear and reset the map.
      • Does not change max_size() of map.
  • Capcaity
    • size()
      • return : std::size_t
      • Returns the size of the map (aka number of inserted pairs).
    • max_size()
      • return : std::size_t
      • Returns the maximum capacity of map before needing to grow/rehash.
    • empty()
      • return : bool
      • Checks if the map is empty or not.
  • Hash Policy
    • load_factor()
      • return : float
      • Returns the load factor of the current map.
      • load_factor() == size()/max_size()
  • Observers
    • key_eq()
      • return : const KeyEqual&
    • hash_functions()
      • return : const Hash&

Major Differences between simd_hash_map and std::unordered_map

  • To optimize value semantics and reduce unnecessary moves and copies, the two "inserting" functions take a key and forwarded value arguments separately. If value_type is emplaced, it is constructed as value_type {std::piecewise_construct, std::forward_as_tuple(key_type), std::forward_as_tuple(std::forward<Args>(args)...)};. If just the mapped_type is inserted due to the key already existing, the following occurs: old_mapped_value = std::move(mapped_type{std::forward<Args>(args)...});.
  • Due to the nature of how this hash table deals with collisions, the user cannot determine the load factor as when the hash table will grow in size.
  • find(key_type) returns an std::optional<iterator>. This is because I try to practice declarative programming, and returning an std::optional is IMO more delcarative than just an iterator which could point to the end of the map.
  • As of 26 April 2019, this container does not take custom allocators, however, this feature will be implemented in the future.

Tests

To run tests, compile as follow inside the tests/ directory

gcc tests-main.cpp "test file"