Какова временная сложность метода String.GetHashCode()? Например, если хешированная строка длиной n, по mod 2 с использованием схемы Хорнера это O(n). Что такое Big O для GetHashCode?Какова временная сложность string.GetHashCode?
В соответствии с reference source временной сложностью является O (n). Он в основном просто берет каждый символ строки и добавляет его значение в хэш.
Как упоминалось в комментарии Питера Ричиса, алгоритм может быть изменен в соответствии с инструкциями на http://msdn.microsoft.com/en-us/library/jj152924(v=vs.110).aspx.
Я не думаю, что это указано, что означает «вы не должны делать никаких предположений». Если вы хотите, чтобы эта информация что-то делала, вы идете по неверному пути. Если вы спрашиваете из любопытства, почему бы просто не использовать декомпилятор и не узнать? – Jon
Если уточнить вопрос, я хотел бы знать, как работает этот метод, если он дает преимущество в производительности по сравнению с методом с использованием схемы Хорнера. – Dmytro
Ну, технически это O (n/4), но я считаю, что считается O (n). String.GetHashCode генерирует хэш памяти, используемой строкой, на основе слов (по два за раз), а не символов (следовательно, n/4) –