STL-Style Open Address Hashmap

Usage

This is a header-only library, so you can just include the arraymap.h file in your project. The hashmap class is called ljl::array_map<K, V>. The hashmap uses the std::hash function for hashing they keys. Thus if you want to use user-defined types as keys, you will have to provide a specialization of std::hash for that type (for more information see the cppreference).

Example:

#include"arraymap.h"

int main(int argc, char** argv) {
    ljl::array_map<int, std::string> map;
	
    map.emplace(1, "1");
    std::cout << map.at(1) << std::endl;
   
    return 0;
}

Description

The goal of this repository is to provide a open address hashmap implementation that follows the STL standard as close as possible (granted there is much work to be done still). In its current state the most basic/important functions are implemented but it is by no means a full implementation up to STL standards.

Currently this is a Netbeans project, which can be a bit annoying as the make files are not super clear. I am looking to change this, for now however you can just compile everything using the included makefile generated by Netbeans.

Interface

For a more detailed description of the interface, see the header files.

Member types

• key_type = K;
• mapped_type = V;
• value_type = std::pair<K, V>;
• size_type = size_t;
• reference = value_type&;
• const_reference = const value_type&;
• iterator Iterator for the container (ForwardIterator).
• const_iterator Const iterator for the container.

Constructors

• array_map() Initializes the container with a capacity of 32 and a max_load_factor of 0.70f.

Member functions

• bool empty() const Checks if the container has no elements
• size_type size() const Returns the number of elements in the container
• size_type capacity() const Return the capacity of the container
• void clear() Removes all elements from the container.
• std::pair<iterator, bool> emplace(const key_type& key, const mapped_type& value) Inserts a new element into the container.
• V& at(const K& key) Returns a reference to the mapped value of the element with a key equivalent to key.
• const V& at(const K& key) const
• iterator find(const K& key) Finds an element with key equivalent to key.
• const_iterator find(const K& key) const
• V& operator[](const K& 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.
• size_type count(const K& key) const Returns the number of elements with key that compares equal to the specified argument key.
• iterator erase(const_iterator pos) Removes specified element at pos.
• size_type erase(const key_type& key) Removes the element (if one exists) with the key equivalent to key.
• float load_factor() const Returns the ratio between elements in the container and the capacity of the container.
• float max_load_factor() const Returns the maximum allowed load factor before rehashing occurs.
• void max_load_factor(float ml) Sets the maximum load factor to ml.
• void rehash(size_type count) Sets the capacity of the container to count and rehashes the container
• void reserve(size_type count) Sets the capacity to the number needed to accommodate at least count elements without exceeding maximum load factor and rehashes the container.
• iterator begin() Returns an iterator to the first element of the container.
• const_iterator begin() const
• const_iterator cbegin() const
• iterator end() Returns an iterator to the element following the last element of the container.
• const_iterator end() const
• const_iterator cend() const

Contributing

If you would like to contribute to the project please do! General guidelines for contributing:

• One change per commit
• Try to uphold the STL standard (as much as possible)
• Try to follow the coding standard of the project

When in doubt, just send me a pull-request and I'll have a look.

If you have discovered a bug, please let me know by creating a new issue. And I will try to fix it as soon as I have the time.

Building

The project is a header only library but it does come with a main function for testing. You can compile the project using make. Cloning the project:

$ git clone https://github.com/LasseJacobs/openaddress_hashmap.git

Building:

$ cd openaddress_hashmap/
$ make

Running the 'demo' (although this command may vary if you are not using Linux):

$ ./dist/Debug/GNU-Linux/hashmap
$ > 1
$ > Element not found

The project also comes with a number of tests to help you validate your changes. To run the tests:

$ make test

The TODO list:

There are a number of important things missing or things that need work, mainly the emplace function which is not fully up-to-spec. Here is a small list of things I would like to get done as soon as possible:

• Add a hash function and compare function template argument
• Write a proper emplace function
• Support list initialization
• Improve performance, in particular add more support for std::move operations
• Change the project structure to a more general make/Cmake project