О, пока я водку пъянствовал дружище nOp меня опередедил. Ну да ладно, не пропадать же "домашнему заданию" и "музыкальному конкурсу", писанному в предпоследние часы уходящего года. Вота записки сумасшедшего, писаные сего года 30 декабря между рюмками "кофе": Эссе под шафе или Мысли вслух, адресованные самому себе и не имеющие прямого отношения к поставленному вопросу. В чем суть поиска по хэш-таблице ? При поиске и сортировке строк требуется сравнение либо самих строк, либо их хэшей. Время поиска ес-но зависит как от реализации самого сравнения, так и от количества требуемых сравнений, т.е. от алгоритма поиска. Что же нам дает поиск по хэш-таблице - ускорение сравнения или уменьшение числа сравнений ? В классическом варианте - именно уменьшение числа сравнений, а в идеале вообще отказ от сравнения. При использовании хэш-таблицы мы вместо поиска во всем множестве строк получаем прямой доступ к подмножеству, соответствующему данному значению хэша. По сути хэш выступает в роли индекса массива, в котором в том или ином виде хранятся ссылки на строки, соответсвующие данному хэшу. В идеальном варианте при отсутствии коллизий мы сразу получаем ссылку на найденную строку (или Null, если такой строки нет), т.е. по сути вообще никакие сравнения не требуются. При наличии коллизий значению хэша соответствует не одна строка, а некоторое множество и нужен поиск искомой строки в этом множестве. Проблема, как всегда, в компромиссе между затратами памяти (размер хэш-таблицы = числу значений хэша) и быстродействием (коллизии и необходимость поиска в подмножестве). Плюс компромисс между затратами на вычисление "хорошей", но "дорогой" хэш-функции с малой вероятностью коллизий и затратами на поиск в ограниченном подмножестве коллизий при использовании "простой" хэш-функции. В классическом варианте с прямым доступом 32-битные хэши типа CRC32 видимо "могут отдыхать" (массивчик >= 4х4Гб), хотя 16-битные наверное вполне приемлемы (4х64Кб). РЕЗЮМЕ: если не упираться лбом в отсутствие коллизий, то суть поиска по хэш-таблице сводится к разбивке всего массива строк на подмножества, к которым осуществляется прямой доступ по значению хэш-функции и затем производится поиск нужной строки в этом ограниченном подмножестве. Можно использовать такой подход для ускорения сортировки строк ? Ес-но. В простейшем случае берем в качестве хэша один или два первых символа строки и что получаем ? Если строки это бессвязный набор равновероятных символов, то наверное все нормально. А если не равновероятны ? Если из 64536 комбинаций двух символов встречается максимум несколько сотен или тысяч ? ...далее предполагалось "несколько слов" о важности учета статистики в теории информации вообще и сжатии и кодировании данных в частности, но тут пошла такая пьянка.. До того ль, голубчик, было в мягких муровах у нас ...
Гладко было на бумаге, да забыли про овраги Если сравнение показало: хэши не равны, то переставим их местами в таблице хэшей и поехали дальше.(При этом не мешало бы задуматься, что по хэшу не найти затем саму строку для итоговой переставки, об этом чуть ниже). А если равны? Где брать остальные элементы этих двух строк для сравнения? Искать в массиве строк по имеющемуся хэшу??? Каким образом? Ведь множество строк могут иметь первый совпадающий ворд. Какие две из них выбрать для продолжения сравнения??? Или сделать таблицу указателей и связать её с таблицей хэшей? И плюс к перестановке хэшей переставлять еще и указатели? Как это может ускорить сортировку? Только замедлит. Если сравнение хэшей не может однозначно ответить на вопрос: какая из строк больше, и в хэшах не содержится информация об адресе самой строки, работу они только замедлят. И сравняются скорости (для случая с хэшами и для случая с указателями) только в том случае, если хэшей, и дополнительных движений, связанных с ними, не будет. P.S. С таким же успехом для сортировки можно приспособить, допустим GWL_USERDATA и хранить в ней допустим адрес строки. И передвигать окна вверх-вниз (сортировать). Ерунда, что миллион статиков придётся создать, зато можно!
cresta Стоп. Какие перестановки хешей? Хеш-таблица имеет свои плюсы именно с того, что данные сразу упорядочены. Только критерий упорядоченности - хеш-значение. Зачем пытаться упорядочивать упорядоченный массив-то? Как уже было сказано, для сортировки массива по какому-либо критерию хеширование не подходит. Это практически другая опера.
Если нужна монотонная hash-функция(та, что сохраняет порядок), то есть некоторые туманные соображения, что лучше чем hash(s)=первые_несколко_символов_s не бывает. Вообще, если рассматривать строку как число(только так чтобы 1й символ строки был старшим байтом числа), то любая монотонная целочисленая ограниченная(разумно ограниченная) функция будет подходящим для сортировки хешем. ЗЫ Например, такой хеш можно использовать для предварительной сортировки чтобы уменьшить число инверсий.
n0p пардон, несколько коряво выразился. Пива тяпнул лишнего Результатом должен быть упорядоченный набор строк. С хэш же можно иметь только упорядоченный до некоторой степени набор. От произнесения волшебного слова "хэш" данные не выстроятся по порядку, все равно надо будет сортировать.
имхо - при построении хеша (с подхешами) с hash(s)=первые_несколко_символов_s сразу будет проиходить и сортирование. Только нужно укорачивать строки, а то памяти немерено съест. вот например : Код (Text): мама мыла раму мамаша мамашаня получим (при s=2) Код (Text): 1 2 3 ма-0 ма-0 ма-шаня0 мы-ла0 ра-му
