1

我需要一个具有以下要求的集合（如果重要的话，在 Objective C 中）：

  1. 恒定时间插入
  2. 恒定时间删除
  3. 获取元素数量
  4. 恒定时间获取随机元素

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

提前致谢。

4

2 回答 2

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. 如果您的集合正在增长，则在其元素/存储桶比率大于 1 后默认重新散列。所以我的解决方案在这里是安全的。

  2. 但是，如果您的集合增长然后迅速缩小，则在集合为空之前不会重新散列，因此您可能需要执行检查并最终重新散列。

    如果 (u.load_factor() < 0.1) u.rehash(u.size());

这会检查集合是否至少 10% 已满，如果没有，则重新散列，以便集合的大小适合存储当前的元素数量。（通常新大小等于大于大小的 2 的较小幂）

于 2013-09-26T21:07:16.110 回答
0

既然你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;
}
于 2013-09-27T10:54:51.150 回答