unordered_map 随机元素

对于 unordered_map（hash 结构）来说，随机获取其中一个元素并不像数组那样简单。以下分析两种思路以及推荐的实现方式。

思路分析

思路 1：直接对内部 list 做随机下标访问。这种方式在数据量大时，迭代器定位极为麻烦，性能较差。

思路 2：先随机到一个非空 bucket，再在该 bucket 内随机取一个元素。

思路 2 存在一个问题：bucket 数量会随着 rehash / resize 等扩容操作而变化，而实际有效元素数 size 可能远小于 bucket_count。这使得随机命中目标元素的概率很低。通过 rehash 剔除多余的空 bucket 虽然可以缓解问题，但 rehash 本身代价较高。纯粹为了解决随机问题而引入 std::map 也不合适，因为查找性能会下降。综合来看，有必要自己实现一个适合这种场景的随机访问逻辑，而不是直接依赖 std::unordered_map 的标准接口。

具体实现（C++）

具体类版本

const std::string & GatewayLoginInfo::RandomMember()
{
	if (this->uuid_to_session_id.size() <= 0)
	{
		return  empty_string;
	}
	//way2 to random
	int max_random_counter = this->uuid_to_session_id.bucket_count();
	int iter = max_random_counter * 2;
	int bucket;
	while ((--iter) >= 0)
	{
		//	find a not empty bucket
		bucket = rand() % max_random_counter;
		int size = this->uuid_to_session_id.bucket_size(bucket);
		if (size > 0)
		{
			// this bucket is not empty
			//大部分情况下  size 一般为0 1 因此比way1 好很多
			auto this_bucket_iter = this->uuid_to_session_id.begin(bucket);
			int counter = rand() % size;
			while (--counter >= 0)
			{
				++this_bucket_iter;
			}
			return this_bucket_iter->first;
		}
	}
	return empty_string;
	//way1 to random
	/*auto it = this->uuid_to_session_id.begin();
	int counter = rand() % this->uuid_to_session_id.size();
	while (counter--)
	{
	++it;
	}
	return it->first;*/
}

泛型版本（带条件过滤）

//从hash表中随机一个元素
template< typename HashMap>
auto unordered_map_random_member_if(HashMap & hash, const std::function<bool(const decltype(hash.begin())&)> &cb)->decltype(hash.begin())
{
	if (hash.size() <= 0)
	{
		return  hash.end();
	}
	int max_random_counter = hash.bucket_count();
	int iter = max_random_counter * 2;
	int bucket;
	while ((--iter) >= 0)
	{
		//	find a not empty bucket
		bucket = rand() % max_random_counter;
		int size = hash.bucket_size(bucket);
		if (size > 0)
		{
			// this bucket is not empty
			//大部分情况下  size 一般为0 1
			auto this_bucket_iter = hash.begin(bucket);
			int counter = rand() % size;
			while (--counter >= 0)
			{
				++this_bucket_iter;
			}
			if (cb(this_bucket_iter))
			{
				return (this_bucket_iter);
			}
		}
	}
	return hash.end();
}

泛型版本（无过滤）

//从hash表中随机一个元素
template< typename HashMap>
auto unordered_map_random_member(HashMap & hash)->decltype(hash.begin())
{
	has_find_one = false;
	if (hash.size() <= 0)
	{
		return  hash.end();
	}
	int max_random_counter = hash.bucket_count();
	int iter = max_random_counter * 2;
	int bucket;
	while ((--iter) >= 0)
	{
		//	find a not empty bucket
		bucket = rand() % max_random_counter;
		int size = hash.bucket_size(bucket);
		if (size > 0)
		{
			// this bucket is not empty
			//大部分情况下  size 一般为0 1
			auto this_bucket_iter = hash.begin(bucket);
			int counter = rand() % size;
			while (--counter >= 0)
			{
				++this_bucket_iter;
			}
			return (this_bucket_iter);
		}
	}
	return hash.end();
}

std::map（非 hash 结构）的随机元素获取方式 TODO。