从哈希挑选一个随机元素设置

Question

我需要符合下列要求的集合（目标C，如果该事项）：

1. 恒定的时间插入
2. 固定时间删除元素
3. GET号
4. 固定时间获得随机元素

散列集合可以工作，但NSMutableSet类是抽象的。我不知道如何编写NSMutableSet类，但我想出了一个动态增长/收缩的散列集合是合适的，因为加载比例将具有保证范围，因此可以通过随机选择一个存储区块来实现随机元素功能并遍历桶直到找到非空的桶，然后从该桶中选择一个随机元素。这会很好，因为它会选择一个随机元素的恒定时间，但我不想重新发明轮子。有没有人有任何建议，或图书馆指向我。

在此先感谢。

Answer 1

我最近偶然发现了同样的问题。以下是我想出了

#include <unordered_set> 
#include <iostream> 

using namespace std; 

int main() { 

unordered_set<int> u; 
int ins = 0; 
for (int i=0; i<30; i++) { // something to fill the test set 
    ins += i; 
    ins %= 73; 
    u.insert(ins); 
} 
cout << "total number of buckets: " << u.bucket_count() << endl; 
for(size_t b=0; b<u.bucket_count(); b++)  //showing how the set looks like 
    if (u.bucket_size(b)) { 
     cout << "Bucket " << b << " contains: "; 
     unordered_set<int>::local_iterator lit; 
     for (lit = u.begin(b); lit != u.end(b);) { 
      cout << *lit; 
      if (++lit != u.end(b)) 
       cout << ", "; 
     } 
     cout << endl; 
    } 
cout << endl; 

int r = rand() % u.bucket_count(); 

while (u.bucket_size(r) == 0)   // finding nonempty bucket 
    r = (r + 1) % u.bucket_count(); // modulo is here to prevent overflow 

unordered_set<int>::local_iterator lit = u.begin(r); 

if (u.bucket_size(r) > 1) {    // if bucket has more elements then 
    int r2 = rand() % u.bucket_size(r); // pick randomly from them 
    for (int i = 0; i < r2; i++) 
     lit++; 
} 
cout << "Randomly picked element is " << *lit << endl; 
cin.ignore(); 

return 0; 
} 

现在的问题换汤不换药：

1. 如果您设置的增长则是在默认情况下它的元素之后改头换面/桶比大于一。所以我的解决方案在这里安全。

2. 但是，如果你的设置增长，然后迅速收缩，直到设置为空，所以你可能想执行检查，并最终重新散列。 （u.load_factor（）< 0.1） u.rehash（u.size（））;如果（u.load_factor（））< 0） u.rehash（u.size（））;

这将检查该集合是否至少有10％已满，如果没有，则重新设置以使集合的大小适合于存储当前数量的元素。 （通常是新的大小等于2的功率较小，比大小大）

Answer 2

由于您的constant实际上是log n，我建议卷起自己B-tree。那么你有：

- (id)randomObject { 
    Your_Branch_Type* branch = your_root; 
    NSUInteger randomIndex = RANDOM_INTEGER_UP_TO(count); 
    while (!branch.final) 
     if (branch.left.count >= randomIndex) { 
      branch = branch.left; 
     } else { 
      branch = branch.right; 
     } 
    return branch.object; 
}