Люди, я написал хеш-класс, но при его сравнении с обычным массивом оказалось, что производительность обычных массивов намного больше, даже не знаю в чём дело, очень хочется разобраться в хешировании, люди, посмотрите прогу, скажите, что я не так делаю, если вам не трудно:
Hash.zip

Что значит производительность выше? Быстрее извлекают эл-т по его адресу? Быстрее чем массив на С++ для такой операции ты ничего не напишешь, разве что выполнить ту же операцию в асме.
Короче. Напиши, по каким критериям ты сравнивал и как.

Как это быстрее не напишешь, нафига тогда вообще хеш-таблицы нужны. Скачай пример и всё увидишь !

Цитата

Как это быстрее не напишешь, нафига тогда вообще хеш-таблицы нужны

Я говорил о скорости извлечения байтов по некоторому известному адресу.
А хеш-таблицы нужны в тех случаях, когда прежде чем извлекать число его необходимо найти в массиве или ином известном диапазоне. Если массив неизменный, и поиск некоторого числа уже выполнялся некоторое время назад (извиняюсь за тафтологию), то нет необходимости повторно осуществлять поиск. Это один из примеров использования хешей.
Поэтому я и прошу сказать, как ты тестировал свой класс.

Там в архиве есть и мой тест, скачай и увидишь, просто качаешь и запускаешь в VC++ 6.

Посмотрел маленько код:

1. Во многих случаях передавать переменные лучше по ссылке, а в некоторых случаях, по константной ссылке. Совершенно нет никакой необходимости копировать их по несколько раз, к тому же у тебя не пройдет такая операция: your_ht["Key"]=MyObject(20); То есть пройти то она пройдет, но измениться темпоральный объект, а не объект хранящийся в таблице. Так что лучше:

Код

UINT HT_CALL AddNode(const char *Key, const T& Val) ..... T& HT_CALL GetNode(const char *Key) .....

и т. д.

2. Таблица у тебя статического размера, то есть при сильном заполнении не растет. Что интересно, у тебя есть конструктор: СHashTable(int moder=HT_MODER), но переменную moder ты используетшь только для того, чтобы заполнить массив нулями, а сам массив остается размером 10.

3. Пользовательскую функцию хеширования надо передавать в конструкторе, потому как таблица должна существовать все время с одной и той же функцией. Если кто-то что-то запишит в таблицу, а потом поменяет хеш-функцию, получиться большой мусор.

4. Написанно многословно в некоторых местах. Вместо:

Код

int i = 0;  i = Hash(Key);  Node<T> *t;  t = HTNode[i];

вполне можно написать: Node<T> *t=HTNode[Hash(Key)];

Может хороший оптимизатор и сам привидет к такому виду, но выглядит все же понятнее.

5. Очень некрасиво смотрится все функции с возвращаемым значением. Это только голову пользователю морочить. Возвращать надо только то, что имеет смысл возвращать. Вместо кода ошибки лучше выбрасывать исключение, там где действительно может быть ошибка. Возвращение кода ошибки - это уже мертвый стиль: не удобный и мало понятный.

6. Тип ключа тоже лучше сделать шаблонным.

7. Все #define поменять на константы.

8. Не врубился зачем __stdcall. Не уверен, что с этим модификатором компилятор выполнит inline подстановку.


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


Это сообщение отредактировал(а) Fantasist - 28.4.2003, 17:45

2 Fantasist:
Спасибо большое, что посмотрел.
Все замечания приму к сведению, но я не уверен, что даже если я всё это исправлю, хеш будет быстрее пахать, ты видел тест, массив бустрее хеша на 500 ticks'ов, а это немало !!!

Да, еще. Все эти VC-шные замены типов совершенно излишни. Гораздо лучше писать на чистом С++. Все эти UINT, BOOL и т.д. лучше поменять на С++-шные типы. И NULL заменить на 0.

Это сообщение отредактировал(а) Fantasist - 28.4.2003, 17:50

Да, но у меня тест на 15000 элементов, а это не 5-6

Цитата

Да, но у меня тест на 15000 элементов

При размере таблицы в 10 элементов, хранение в не 15000 элементов очень не эффективно. К тому же, хранить записи таблицы тоже быстрее упорядоченным массивом, деревом, или хотябы упорядоченным списком.

Лучший для тебя тест - это сравнить с стандартным std::hash_map, хотябы с той же поставкой VC.