Анализ хеширования в хеш-таблице

#data-structures #hash #hashtable

#структуры данных #хеширование #хеш-таблица

Вопрос:

Время поиска хеш-значения равно O (1 альфа), где

  alpha = number of elements/size of table

Я не понимаю, почему добавляется 1?

Проверенное ожидаемое число элементов

 (1/n  summation of i=1 to n (1 (i-1/m)))

Я тоже этого не понимаю.Как это происходит?

(Я знаю, как решить приведенное выше выражение, но я хочу понять, как это привело к этому выражению ..)

РЕДАКТИРОВАТЬ: n — количество присутствующих элементов, а m — количество слотов или размер таблицы

1. пожалуйста, укажите, во время какой операции «элементы [проверяются]»? во время одного поиска? что такое m и n в вашем выражении? n вероятно, общее количество элементов, но m ?

2. @armel спасибо .. Я отредактировал вопрос и да во время одной операции поиска, а n — количество элементов, присутствующих в таблице

Ответ №1:

Я не понимаю, почему добавляется 1?

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

Ваша вторая часть нуждается в уточнениях. Смотрите мои комментарии.

Редактировать: Ваша вторая часть предназначена для «амортизированного анализа», идея состоит в том, чтобы фактически учитывать каждую вставку в наборе из n вставок в изначально пустой хеш-таблице, каждый поиск будет принимать O (1) хеширование плюс O (i-1 / m) поиск содержимого корзины, учитывая, что каждое ведро равномернозаполняется относительно предыдущих элементов. Разрешение суммы фактически дает амортизированное время O (1 альфа).

1. Таким образом, это означает, что для поиска этого конкретного элемента ключевое хэш-значение для него вычисляется за постоянное время O (1).. Я прав?

2. O (1) здесь означает, что оно не зависит от количества элементов и размера хеш-таблицы. Конечно, это зависит от сложности ключа. Вычисление хеш-ключа для целого числа может быть тривиальным и занимать постоянное время, поэтому O (1), в то время как для строк это может быть O (размер строки) и так далее.

3. ХОРОШО, понял, спасибо .. и информация о второй части актуальна? что-нибудь еще требуется с моей стороны?