История изменений
Исправление KivApple, (текущая версия) :
Нет, колизии повышают сложность. В вырожденном случае (у всех элементов один хеш) сложность хеш таблицы O(N). В идеальном случае, где у всех элементов разные хеши O(1). В реальности где-то посередине в зависимости от данных. При этом надо учитывать, что используется не хеш целиком, а последние N бит, потому что хештаблица не будет содержать SIZE_MAX элементов, а всегда меньше. Так что коллизии случаются чаще, чем кажется. Конечно, с этим борятся авторы хешфункций и сама хештаблица (load factor), но это не панацея.
Если упираешься в перф, бенчить хештаблица vs std::map (и аналоги) стандартная практика. Потому что хештаблица не всегда быстрее и не серебряная пуля. Зависит от конкретной задачи и только бенчи знают правду наверняка.
Ну и само собой бенчить хеш таблицы с открытой адресацией и обычные тоже надо между собой, потому что они тоже по-разному ведут себя на разных наборах данных. Хотя на бумаге обе обещают сложность где-то между O(1) и O(N).
Исправление KivApple, :
Нет, колизии повышают сложность. В вырожденном случае (у всех элементов один хеш) сложность хеш таблицы O(N). В идеальном случае, где у всех элементов разные хеши O(1). В реальности где-то посередине в зависимости от данных. При этом надо учитывать, что используется не хеш целиком, а последние N бит, потому что хештаблица не будет содержать SIZE_MAX элементов, а всегда меньше. Так что коллизии случаются чаще, чем кажется. Конечно, с этим борятся авторы хешфункций и сама хештаблица (load factor), но это не панацея.
Если упираешься в перф, бенчить хештаблица vs std::map (и аналоги) стандартная практика. Потому что хештаблица не всегда быстрее и не серебряная пуля. Зависит от конкретной задачи и только бенчи знают правду наверняка.
Ну и само собой бенчить хеш таблицы с открытой адресацией и обычные тоже надо между собой, потому что они тоже по-разному ведут себя на разных наборах данных. Хотя на бумаге обе обещают сложность где-то между O(1) и O(N)
Исправление KivApple, :
Нет, колизии повышают сложность. В вырожденном случае (у всех элементов один хеш) сложность хеш таблицы O(N). В идеальном случае, где у всех элементов разные хеши O(1). В реальности где-то посередине в зависимости от данных. При этом надо учитывать, что используется не хеш целиком, а последние N бит, потому что хештаблица не будет содержать SIZE_MAX элементов, а всегда меньше. Так что коллизии случаются чаще, чем кажется. Конечно, с этим борятся авторы хешфункций и сама хештаблица (load factor), но это не панацея.
Если упираешься в перф, бенчить хештаблица vs std::map (и аналоги) стандартная практика. Потому что хештаблица не всегда быстрее и не серебряная пуля. Зависит от конкретной задачи и только бенчи знают правду наверняка.
Ну и само собой бенчить хеш таблицы с открытой адресацией и обычные тоже надо между собой, потому что они тоже по-разному ведут себя на разных наборах данных.
Исправление KivApple, :
Нет, колизии повышают сложность. В вырожденном случае (у всех элементов один хеш) сложность хеш таблицы O(N). В идеальном случае, где у всех элементов разные хеши O(1). В реальности где-то посередине в зависимости от данных. При этом надо учитывать, что используется не хеш целиком, а последние N бит, потому что хештаблица не будет содержать SIZE_MAX элементов, а всегда меньше. Так что коллизии случаются чаще, чем кажется. Конечно, с этим борятся авторы хешфункций и сама хештаблица (load factor), но это не панацея.
Если упираешься в перф, бенчить хештаблица vs std::map (и аналоги) стандартная практика. Потому что хештаблица не всегда быстрее и не серебряная пуля. Зависит от конкретной задачи и только бенчи знают правду наверняка.
Исправление KivApple, :
Нет, колизии повышают сложность. В вырожденном случае (у всех элементов один хеш) сложность хеш таблицы O(N). В идеальном случае, где у всех элементов разные хеши O(1). В реальности где-то посередине в зависимости от данных. При этом надо учитывать, что используется не хеш целиком, а последние N бит, потому что хештаблица не будет содержать SIZE_MAX элементов, а всегда меньше. Так что коллизии случаются чаще, чем кажется. Конечно, с этим борятся авторы хешфункций и сама хештаблица (load factor), но это не панацея.
Если упираешься в перф, бенчить хештаблица vs std::map (и аналоги) стандартная практика. Потому что хештаблица не всегда быстрее и не серебряная пуля.
Исходная версия KivApple, :
Нет, колизии повышают сложность. В вырожденном случае (у всех элементов один хеш) сложность хеш таблицы O(N). В идеальном случае, где у всех элементов разные хеши O(1). В реальности где-то посередине в зависимости от данных. При этом надо учитывать, что используется не хеш целиком, а последние N бит, потому что хештаблица не будет содержать SIZE_MAX элементов, а всегда меньше. Так что коллизии случаются чаще, чем кажется. Конечно, с этим борятся, но это не панацея.