При создании хеша строки это является поддающимся сортировке

Только в том случае, если строк меньше, чем хэшей, и хэши являются совершенными . Даже тогда вы все равно должны убедиться, что порядок хэшей совпадает с порядком строк, это, вероятно, невозможно, если только вы не знаете все строки заранее.

Нет. Хэш должен содержать тот же объем информации, что и заменяемая им строка. Иначе, если две строки отображаются в один и тот же хэш-значение, как их можно отсортировать?

Другой способ размышлять об этом: Если у меня есть две строки, "a" и "b", то я хэширую обе из них этой сортировочной хэш-функцией и получаю f(a) и f(b). Однако, существует бесконечное количество строк, которое больше "a", но меньше "b". Это потребует хэширования строк с произвольной точностью Реальные значения (из-за кардинальности). В конце концов, в основном, строка была бы закодирована как число

Как отмечали другие, делать именно то, что вы просили, непрактично. Вам пришлось бы использовать саму строку в качестве хэша, который ограничивал бы длину строк, которые можно было бы "хэшировать" и т.д.

Очевидным подходом к сохранению структуры данных "отсортированных хэшей" было бы ведение как отсортированного списка (кучи или двоичного дерева, например), так и хэшированного отображения данных. Вставки и удаления должны быть O(log(n)), а извлечения - O(1). Я не уверен, как часто это будет стоить дополнительной сложности и накладных расходов.

Если бы у вас был особенно большой набор данных, в основном только для чтения, и такой, что логарифмическое время поиска было бы слишком дорого, то я полагаю, что это могло бы быть полезно. Обратите внимание, что стоимость обновлений на самом деле является суммой постоянного времени (хэш) и логарифмического времени (двоичное дерево или куча) операций. Однако O(1) + O(log(n)) при асимптотическом анализе уменьшается до большего из двух сроков. (При этом базовая стоимость остается --- актуальной для любых усилий по реализации, независимо от ее теоретической неактуальности).

При значительном диапазоне размеров массивов данных стоимость поддержания этой гипотетической гибридной структуры данных можно оценить как "в два раза" по сравнению с стоимостью поддержания любой из чистых структур. (Другими словами, многие реализации двоичного дерева могут масштабироваться до миллиардов элементов (2^~32 или около того) во временной стоимости, сравнимой со стоимостью типичных хэш-функций). Поэтому мне было бы трудно убедить себя в том, что такая сложность кода и стоимость исполнения (гибридной структуры данных) на самом деле была бы полезна для данного проекта

(Примечание: я видел, что на Python 3.1.1 было добавлено понятие "упорядоченных" словарей... и это похоже на сортировку, но не совсем одно и то же. Из того, что я собираю, упорядоченный словарь сохраняет порядок, в котором элементы были вставлены в коллекцию. Также я, кажется, помню некоторые разговоры о "видах" ... объектов на языке, которые могут обращаться к ключам словаря определенным образом (отсортированные, перевернутые, обратно отсортированные, ...) по (возможно) более низкой цене, чем передача набора ключей через встроенные "sorted()" и "reverseed()". Я ими не пользовался и не рассматривал детали реализации. Я бы догадался, что одним из таких "видов" будет что-то вроде лениво оцениваемого индекса, выполняющего необходимую сортировку по вызову, и сохраняющего результаты с каким-то флагом или триггером (шаблон наблюдателя или слушателя), который сбрасывается при обновлении бэк-эндной коллекции исходников. В этой схеме вызов "вида" будет обновлять свой индекс; вызовы подпоследовательностей смогут использовать эти результаты до тех пор, пока в словаре не будут сделаны ни вставки, ни удаления. Любой вызов представления после ключевых изменений повлечет за собой расходы по обновлению представления. Однако это все чистая спекуляция с моей стороны. Я упоминаю об этом, потому что это может также дать представление о некоторых альтернативных способах подхода к вопросу)

Вы, по сути, спрашиваете, можете ли вы сжимать строки ключей в меньшие по размеру клавиши, сохраняя при этом порядок их сопоставления. Так что это зависит от ваших данных. Если Ваши строки состоят только из шестнадцатеричных цифр, например, они могут быть заменены 4-битными кодами.

Но в общем случае это невозможно. В конце концов, вы будете "хэшировать" каждый исходный ключ в себя.

Да. Он вызывается с использованием всей входной строки в качестве хэша.