|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
22.02.2011, 13:53 | #1 |
Пользователь
Регистрация: 02.05.2010
Сообщений: 26
|
Хэш таблицы
Уважаемые коллеги программисты. Мне нужна ваша помощь. Дело в том что я сейчас работаю над одним модулем. В нем я выделяю динамически память. И все эти куски храню в хэш таблице. Проводил тест. Создал хэш таблицу из 100 000 элементов(округлял до простого числа в большую сторону). И выделял память для 100 000 указателей.
К хеш функции отправлял адресс выделенной памяти. Как работала хэш функция: Я переводил адресс в usigned long и брал остаток от деления. Вот что получилось 0 - 35555 1 - 38328 2 - 19205 3 - 5855 4 - 1175 5 - 173 6 - 22 7 - 0 8 - 0 9 - 0 10 - 0 то есть у меня 35555 свободных ячеек в хеш таблице и так далее. Согласитесь это очень не выгод. Больше 30% таблицы не используется. И эта цифра будет расти с увеличением хэш таблицы. Провывал использовать CRC. Вот результат с теми же данными 0 - 37003 1 - 36971 2 - 18320 3 - 6115 4 - 1543 5 - 300 6 - 56 7 - 4 8 - 1 9 - 0 10 - 0 Провыбал использовать MD4 вот результат 0 - 36906 1 - 37025 2 - 18454 3 - 6055 4 - 1529 5 - 290 6 - 44 7 - 9 8 - 0 9 - 1 10 - 0 хотя здесь работают непосредственно с битами. Помогите найти такую хэш функцию, которая хотя бы снизила количество неиспользуемых ячеек до 10%. Или направить на путь!!! Повторяюсь к хэш таблице приходят адресса памяти(к сведению они кратны 4) заранее спасибо!!! |
22.02.2011, 14:38 | #2 |
Пользователь
Регистрация: 02.02.2011
Сообщений: 92
|
Оптимальная загрузка хеш-таблицы (load factor) - 72%, у Вас 65%, что не так плохо. Если сделать больше - возрастает число коллизий и, как следствие, увеличивается время поиска.
Как подобрать правильную функцию - не знаю, коллизий у Вас многовато. Альтернативный путь - реализация ассоциативного массива на двоичных деревьях (std::map напр.) |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
хэш-функция N-хэш | Temka | Общие вопросы Delphi | 1 | 29.11.2010 21:11 |
хэш-таблицы в с++ | mephistophel | Помощь студентам | 0 | 24.04.2010 02:56 |
Постройка хэш-таблицы | Syalon | Общие вопросы C/C++ | 0 | 11.11.2009 02:14 |
Хэш таблицы | _Studentka_ | Общие вопросы по Java, Java SE, Kotlin | 3 | 04.11.2009 21:49 |
Почему размер хэш-таблицы обязательно простое число? | Zefick | Помощь студентам | 4 | 25.12.2008 13:42 |