Skip to content

Dense hash map hangs(assert in debug) when find() on non-existent #141

@ghost

Description

Hi there. Was testing dense_hash_map and found it would hang on a certain test configuration

Load factor = 1
Completely fill map with items
delete an item
find() for that item
The find() should return failure but find_position never exits. It seems that find_position (in densehashtable) only exits when it finds the item or finds an empty item. If all items are either deleted or existing then it will never exit.

Now I'm not sure if the intention is to ensure there are always empty items by having more buckets than items (Never actually being loadfactor=1), or if it's an issue with find_position that needs to take into account hash tables full of only deleted and valid items. My fix took the latter approach

Below is one way to reproduce the error.

	GOOGLE_NAMESPACE::dense_hash_map<int, int> google_dense;
	google_dense.set_empty_key(0);
	google_dense.set_deleted_key(1);
	google_dense.max_load_factor(1);

	size_t bc = google_dense.bucket_count();
	for (int t = 0; t < bc; ++t)
	{
		google_dense.insert({ t + 2, t });
	}
	google_dense.erase(2);
	google_dense.find(2);

My fix was to insert after ++num_probes the following. This may or may not suit the aims of the container in general

	  // We've searched everything, not found it, but we did find a deleted bucket. 
	  if (num_probes == bucket_count() && insert_pos != ILLEGAL_BUCKET)
	  {
		  return std::pair<size_type, size_type>(ILLEGAL_BUCKET, insert_pos);
	  }

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions