Обычно говорится, что вставка и поиск строки в хэш-таблице - это O (1). Но как сделан хэш-ключ строки? Почему это не O (L), длина строки? Мне ясно, почему для целых чисел это O (1), но не для строк.
Обратите внимание, что я понимаю, почему вообще вставка в хэш-таблицу - это O (1), но я смущен, прежде чем вставлять хэш в таблицу, делая фазу хэш-значения.
И существует ли какая-либо разница между тем, как хэш-ключи для строк создаются между hashTable в java и unordered_map в С++?
Вставка и т.д. в хэш-таблице - это O (1) в том смысле, что она является постоянной в количестве элементов в таблице.
"O (1)" в этом контексте не претендует на то, как быстро вы можете вычислить свои хэши. Если усилия для этого будут расти каким-то образом, так оно и есть. Тем не менее, я считаю маловероятным, что сложность хеш-функции приличного (т.е. "Пригодного для этого приложения" ) будет когда-либо хуже линейного по размеру (т.е. Длины в нашем примере строки) хэшируемого объекта.
Обычно говорится, что вставка и поиск строки в хэш-таблице - это O (1). Но как сделан хэш-ключ строки? Почему это не O (L), длина строки? Мне ясно, почему для целых чисел это O (1), но не для строк.
Общее предложение O (1) означает, что время не увеличивается с количеством элементов в контейнере. Как вы говорите, время генерации хэш-значения из строки может быть не самой O (1) в длине строки, хотя для некоторых реализаций это: например, Microsoft С++ std::hash<std::string> имеет:
size_t _Val = 2166136261U;
size_t _First = 0;
size_t _Last = _Keyval.size();
size_t _Stride = 1 + _Last / 10;
if (_Stride < _Last)
_Last -= _Stride;
for(; _First < _Last; _First += _Stride)
_Val = 16777619U * _Val ^ (size_t)_Keyval[_First];
return (_Val);
_Stride - это десятая часть длины строки, поэтому фиксированное количество символов, расположенных далеко друг от друга, будет включено в значение хэша. Такая хэш-функция - это O (1) в длине строки.
Стандартная библиотека GCC С++ использует другой подход: по крайней мере, в v4.7.2, он вызывает через класс поддержки _Hash_impl функцию static _Hash_bytes, который делает хеш мурмура, включающий каждый байт. GCC hash<std::string>, следовательно, O (N) в длине строки.
std::unordered_set и std::unordered_map, реализация MS которых не выполняется - по крайней мере, до VS2013/VC12; общий подход MS будет более легким/быстрым для ключей, которые не подвержены столкновениям, но ухудшаются раньше и более резко в противном случае.И существует ли какая-либо разница между тем, как хэш-ключи для строк создаются между hashTable в java и unordered_map в С++?
Как строки хэширования не заданы стандартом С++ - он оставлен для отдельных реализаций компилятора. Следовательно, разные компромиссы поражают разные компиляторы - даже разные версии одного и того же компилятора.
Документация David Pérez Cabrera ответит на ссылки на объяснение функции hashCode в Java:
Возвращает хэш-код для этой строки. Хэш-код для объекта String вычисляется как
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
с использованием
intарифметики, гдеs[i]является символомith строки,nявляется длиной строки, а^указывает на возведение в степень. (Хэш-значение пустой строки равно нулю.)
Очевидно, что O (N) в длине строки.
В соответствии с реализацией Java, Hashtable использует метод hashCode ключа (String или Integer). Hashtable String.hashCode Integer.hashCode
И С++ используют std::hash<std::string> или std::hash<int> в соответствии с http://en.cppreference.com/w/cpp/utility/hash, и реализация была в функциональном файле (/path/to/С++.../include/С++/4.8/functional)