您可以通过额外维护每个节点下方的总权重来使用任何平衡的二叉搜索树数据结构来做到这一点。要随机抽样，计算一个介于 $0$ 和根节点权重之间的均匀随机数，然后向下遍历树，直到找到其范围包含随机数的叶子。$0$ and the weight of the root node, and traverse down through the tree until you find the leaf whose range contains the random number.

不幸的是，虽然将总权重保持在给定节点以下很简单，但这确实意味着您可能必须实现自己的平衡二叉树结构。就程序员时间而言，复制和修改现有数据结构可能是最快的；你甚至可以使用 libstdc++ 的红黑树实现。

假设 C++，如果您愿意存储重复的项目，对于未加权的情况，一种省时的方法是将它们未排序地存储在 astd::vector或std::deque, 中v。
然后，您可以通过在v.
要抽取样本，只需选择一个随机索引i并v使用

sample = v[i];
v[i] = v.back();
v.pop_back();

对于额外的存储成本，您将获得（在 的情况下摊销std::vector）恒定时间迭代。

C++ 中的“标准”数据结构是多集

http://www.cplusplus.com/reference/set/multiset/

基于平衡二叉树和 unordered_multiset

http://www.cplusplus.com/reference/unordered_set/unordered_multiset/

基于哈希表。

我会先尝试这些，看看它们的性能是否足以满足您的要求。

你说你希望有很多项目只有一次，几次。

虽然一般来说，像 Geoffrey 建议的那样的自平衡搜索树会是最快的，但有一种更容易实现的替代方案。

只需将仅在向量中出现一次的 $k$ 项保留在无序映射中，就像这样说 ak 建议的那样，而将其他 $m$ 唯一项保留在无序映射中。然后，您跟踪每个结构中的项目总数，当您必须对地图进行采样时，您接受 $O(m)$ 时间。但是，正如您所期望的 $k >> m$，这可能不是问题。$k$ items that only occur once in a vector, like thus spake a.k. suggested, and the other $m$ unique items in an unordered map. You then keep track of the total number of items in each structure, and when you have to sample the map, you accept the $O(m)$ time. However as you expect $k >> m$, this is likely not a problem.