Как случайным образом получить элемент из хеш-таблицы С++ в O (1)

Вы не можете выбрать случайный элемент из unordered_set за время O(1). Итераторов ForwardIterator, а не RandomAccessIterator. Вам придется использовать другой контейнер. Либо boost::container::flat_set<int>, либо напишите свой собственный также имеет что-то вроде vector внутри:

template <typename T>
class set_with_random_access
{
    std::vector<T*> vec;
    std::unordered_set<T> set;
};

Для которых мы предоставляем функции, которые держат их в очереди, например вставку:

void insert(const T& value) {
    auto pr = set.insert(value);
    if (pr.second) {
        vec.push_back(&*pr.first);
    }
}

И случайность:

template <typename GEN>
T& random(GEN& gen) {
    std::uniform_int_distribution<size_t> dist(0, vec.size() - 1);
    return *vec[dist(gen)];
}

Это, честно говоря, много работы, поэтому, вероятно, используйте ускорение.

способ случайного извлечения элемента из С++ unordered_set в среднем за время O (1)?

Зависит от того, что считается «случайным» для ваших целей, и достаточно ли быть немного выше O (1). Вы можете выбрать случайное ведро "b" между 0 и s.bucket_count() - 1, повторяя, если ведро пусто, затем индекс списка li между 0 и s.bucket_size(b) - 1, затем std::advance(s.begin(li)), чтобы получить итератор к "случайному" элементу, но рассмотрим эту ситуацию:

Вы бросаете три кубика, а затем случайным образом выбираете один из них: вы получаете случайное значение от 1 до 6 с четной вероятностью, но если вы продолжаете выбирать без повторного броска, вы можете получить только те значения, которые оказались на трех кубиках: вероятности каждого значения от 1 до 6 сильно неравномерны.

Приведенный выше подход к выбору случайного элемента в unordered_set немного похож на этот: если есть x корзин с элементами, то каждая корзина имеет равные шансы быть выбранными, но элементы в этой корзине имеют 1 / x / bucket_size() шансов выбора, что - для любое заданное ведро - может быть меньше или больше 1 / size(). Другими словами, если вы считаете хеширование фактически случайным, то различные элементы имеют равные шансы быть одобренными или оштрафованными при их размещении, но это «перекос» затем закрепит его до тех пор, пока данные таблицы не будут значительно изменены или таблица не будет перехэширована (и если он перефразирован, скажем, путем удвоения размера таблицы, а не до большего простого числа (смутная память, которая удваивается unordered_set), то однажды оштрафованные значения будут иметь тенденцию оставаться оштрафованными в половине случаев).

Эффективность вышеописанного вышеописанного — чуть-чуть выше O(1), потому что:

• в начальном тесте есть некоторое повторение, чтобы найти корзину с элементами, но с коэффициентом загрузки 1,0 вряд ли потребуется больше пары попыток (учитывая хорошую хеш-функцию); доступны другие варианты — например, итерация из пустого ведра или прыжки с помощью различных смещений (модифицированных в размер таблицы), — которые могут работать немного лучше, чем попытка использовать другое совершенно случайное ведро, но также могут усугубить несоответствия в шансах выбора элемента.

• существует линейная итерация в элементах, сталкивающихся в любом заданном сегменте, но, поскольку коэффициент нагрузки по умолчанию равен 1,0, будет редко иметь более пары столкновений, и все более и более крайне редко будет иметь гораздо больше.

Выбор случайного элемента из std::unordered_set — плохая идея. Это связано с тем, что std::unordered_set не поддерживает произвольный доступ и, следовательно, не имеет оператора нижнего индекса (т. е. operator[]).

Я твердо верю, что вам нужно std::vector в сочетании с std::unique, чтобы удовлетворить уникальность элемента.

В приведенном ниже примере я использую std::vector, а затем я гарантирую, что он содержит только уникальные элементы, применяя к нему алгоритм std::unique. Затем я использую утилиты random для генерации случайного индекса в [0, размер вектора - 1]:

std::vector<int> v{1, 2, 8, 3, 5, 4, 5, 6, 7, 7, 9, 9, 19, 19};
v.erase(std::unique(v.begin(), v.end()), v.end());

std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(0, v.size() - 1);

std::cout << "Random number from vector: " << v[distribution(generator)] << std::endl;

РЕАЛЬНАЯ ДЕМО