A hash-map implementation using open-addressing with various probe sequence patterns.

HashMap2.cpp

template<typename Key, typename Value>
class HashMap2
{
public:
	
	using size_t = std::size_t;
	
	using hash_function_t = std::function<size_t(const Key& key)>;

	
	static const size_t minimum_capacity = 8;

	
	struct Pair
	{
		Pair(const Key& key = Key(),
			 const Value& value = Value())
		{ }
		
		Key key;
		Value value;
	};
	
	
	HashMap2(const hash_function_t& function = std::hash<Key>(),
			 size_t capacity = minimum_capacity)
	: _items(new Item*[capacity + 1])
	, _size(0)
	, _alive(0)
	, _capacity(capacity)
	, _hash_function(function)
	{
		_nullify();
		
		_items[capacity] = new Item;
	}
	
	HashMap2(std::initializer_list<Pair> items,
			 const hash_function_t& function = std::hash<Key>(),
			 size_t capacity = minimum_capacity)
	: _size(0)
	, _alive(0)
	, _hash_function(function)
	{
		_capacity = std::max(capacity, items.size() * 2);
		
		_items = new Item*[_capacity];
		
		_nullify();
	}
	
	HashMap2(const HashMap2& other)
	: _size(other._size)
	, _capacity(other._capacity)
	, _hash_function(other._hash_function)
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			if (other._items[i]) _items[i] = new Item(other._items[i]);
			
			else _items[i] = nullptr;
		}
	}
	
	HashMap2(HashMap2&& other) noexcept
	: HashMap2()
	{
		swap(other);
	}
	
	HashMap2& operator=(HashMap2 other) noexcept
	{
		swap(other);
	}
	
	void swap(HashMap2& other)
	{
		swap(_items, other._items);
		
		swap(_size, other._size);
		
		swap(_capacity, other._capacity);
	}
	
	friend void swap(HashMap2& first, HashMap2& second)
	{
		first.swap(second);
	}
	
	~HashMap2()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			delete _items[i];
		}
		
		delete [] _items;
	}
	
	
	void insert(const Key& key, const Value& value)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				_items[index]->value = value;
			}
		}
		
		_items[index] = new Item(key, value);
		
		++_alive;
		
		if (++_size == _capacity/2) _resize();
	}
	
	void insert(const Pair& pair)
	{
		insert(pair.key, pair.value);
	}
	
	template<typename Itr>
	void insert(Itr begin, Itr end)
	{
		for ( ; begin != end; ++begin)
		{
			insert(*begin);
		}
	}
	
	
	void erase(const Key& key)
	{
		bool found = erase_if_found(key);
		
		if (! found) throw std::invalid_argument("No such key to erase!");
	}
	
	bool erase_if_found(const Key& key)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				_items[index]->is_alive = false;
				
				if (--_alive == _capacity/8) _resize();
				
				return true;
			}
		}
		
		return false;
	}
	
	void clear()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			delete _items[i];
		}
		
		delete [] _items;
		
		_capacity = minimum_capacity;
		
		_items = new Item*[_capacity];
		
		_nullify();
		
		_alive = _size = 0;
	}
	
	
	bool contains(const Key& key) const
	{
		size_t index = _hash(key);
		
		for(size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive &&
			    _items[index]->key == key) return true;
		}
		
		return false;
	}
	
	
	Value& at(const Key& key)
	{
		return _at(key);
	}
	
	const Value& at(const Key& key) const
	{
		return _at(key);
	}
	
	
	Value& operator[](const Key& key)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->key == key) return _items[index]->value;
		}
		
		Item* item = new Item(key);
		
		_items[index] = item;
		
		++_alive;
		
		if (++_size == _capacity/2) _resize();
		
		return item->value;
	}
	
	
	bool insert_or_assign(const Key& key, const Value& value)
	{
		size_t index = _hash(key);
		
		for (size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				_items[index]->value = value;
				
				return false;
			}
		}
		
		_items[index] = new Item(key, value);
		
		++_alive;
		
		if (++_size == _capacity/2) _resize(_capacity * 2);
		
		return true;
	}
	
	bool insert_or_assign(const Pair& pair)
	{
		insert_or_assign(pair.key, pair.value);
	}
	
	
	size_t size() const
	{
		return _alive;
	}
	
	size_t capacity() const
	{
		return _capacity;
	}
	
	bool is_empty() const
	{
		return _alive == 0;
	}
	
	
	const hash_function_t& hash_function() const
	{
		return _hash_function;
	}

private:
	
	struct Item
	{
		Item(const Key& k = Key(),
			 const Value& v = Value())
		: key(k)
		, value(v)
		, is_alive(true)
		{ }
		
		Key key;
		Value value;
		
		bool is_alive;
	};
	
	Value& _at(const Key& key) const
	{
		size_t index = _hash(key);
		
		for(size_t step = 0; _items[index]; index = _hash(key, ++step))
		{
			if (_items[index]->is_alive && _items[index]->key == key)
			{
				return _items[index]->value;
			}
		}
		
		throw std::invalid_argument("No such key!");
	}
	
	size_t _linear_hash(const Key& key, size_t step = 0) const
	{
		return (_hash_function(key) + step) % _capacity;
	}
	
	size_t _quadratic_hash(const Key& key, size_t step = 0) const
	{
		static const size_t a = 99;
		static const size_t b = 13;
		
		const size_t offset = (a * step) + (b * (step * step));
		
		return (_hash_function(key) + offset) % _capacity;
	}
	
	size_t _double_hash(const Key& key, size_t step = 0) const
	{
		static const size_t a = 57;
		static const size_t b = 69;
		static const size_t p_1 = 99;

		static const size_t c = 131;
		static const size_t d = 23;
		static const size_t p_2 = 77;
		
		size_t pre_hash = _hash_function(key);
		
		size_t h_1 = _universal_hash(pre_hash, a, b, p_1);
		size_t h_2 = _universal_hash(pre_hash, c, d, p_2);
		
		return (h_1 + step * h_2) % _capacity;
		
	}
	
	size_t _universal_hash(size_t pre_hash,
						   size_t constant_1,
						   size_t constant_2,
						   size_t prime) const
	{
		return ((constant_1 * pre_hash + constant_2) % prime) % _capacity;
	}
	
	size_t _hash(const Key& key, size_t step = 0) const
	{
		return _double_hash(key, step);
	}
	
	void _resize()
	{
		size_t new_capacity = _alive * 4;
		
		if (new_capacity < minimum_capacity) new_capacity = minimum_capacity;

		const size_t old_capacity = _capacity;
		
		Item** old = _items;
		
		_capacity = new_capacity;
		
		_items = new Item*[_capacity];
		
		_nullify();
		
		for (size_t i = 0; i < old_capacity; ++i)
		{
			if (old[i] && old[i]->is_alive)
			{
				size_t index = _hash(old[i]->key);
				
				for (size_t step = 1; _items[index]; ++step)
				{
					index = _hash(old[i]->key, step);
				}
				
				_items[index] = old[i];
				
				old[i] = nullptr;
			}
			
			else delete old[i];
		}
		
		delete [] old;
		
		_size = _alive;
	}
	
	void _nullify()
	{
		for (size_t i = 0; i < _capacity; ++i)
		{
			_items[i] = nullptr;
		}
	}
	
	
	Item** _items;
	
	size_t _size;
	
	size_t _alive;
	
	size_t _capacity;
	
	hash_function_t _hash_function;
};