#hash
Вопрос:
В нескольких доказательствах ожидаемой длины поиска в хэш-таблице открытой адресации делается предположение (которое, как говорят, следует из «простого единообразного предположения о хешировании»).:
Учитывая хэш-таблицу с n слотами и m ключами в ней, вероятность того, что какой-либо конкретный слот занят, равна m/n.
Я не могу понять, как это следует. Я имею в виду, как вы структурируете эксперимент, то есть каково пространство выборки и как вы это вычисляете.
Я имею в виду пространство выборки, состоящее из m-кортежей ключей. Эксперимент заключается в том, чтобы случайным образом выбрать один такой кортеж. Событие A-это набор всех таких кортежей, в которых есть по крайней мере 1 ключ, который хэшируется в данный слот.
Вероятность А тогда есть 1 - (the probability that none of the m keys hash to the given slot) . Так 1 - ((n-1)/n)^m . Но это не равносильно m/n …
Комментарии:
1. Это может дать лучшие ответы на дочернем сайте cs.stackexchange.com поскольку речь идет скорее о теории, чем о какой-либо практической проблеме. Ваш вопрос также немного сбивает с толку, потому что вы не объяснили, откуда берется ваш расчет вероятности, поэтому трудно понять, сделали ли вы неверное предположение, чтобы попасть туда.
2. Я голосую за то, чтобы закрыть этот вопрос, потому что он относится к обмену стеками компьютерных наук