Создание хорошей хеш-функции -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [3.145.52.86]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

Создание хорошей хеш-функции

amk

Сообщ. #16 , 20.06.17, 14:22

Guru

Профиль · PM

Поощрения: 4 Dgm

Рейтинг (т): 268

Цитата FasterHarder @ 18.06.17, 19:52

нет, используется хеш-таблица с открытой адресацией. Т е 1 карман предназначен для 1 объекта!

В таком случае делай размер таблицы хотя-бы на 25-30% больше числа записываемых в неё объектов. Или отказывайся от хэш-таблицы и пользуйся простым вектором.

Akina

Сообщ. #17 , 20.06.17, 17:40

Moderator

Профиль · PM

Поощрения: 35 Dgm

Рейтинг (т): 541

FasterHarder
Ну и вот тебе ещё ~~гвоздь~~ фактик на подумать. Хэш по определению есть детерминированная функция. В то время как твой подход требует, чтобы он ещё зависел от сторонних данных. Потому как вероятность отсутствия коллизий (для случайных входящих и 20 карманов) составляет порядка один к 43 миллионам, что вряд ли для тебя предел мечтаний... и не зависит от формулы хэширования при условии её равномерности.

amk

Сообщ. #18 , 21.06.17, 14:06

Guru

Профиль · PM

Поощрения: 4 Dgm

Рейтинг (т): 268

Подсчитал тут кое-что в обед

Размер	Заполнение	Поиск	Поиск 2
20	35.5525	2.77763	20.0
25	16.5149	1.825746	3.33333
30	11.2284	1.561420	1.66667
32	9.98593	1.499296	1.53846

Размер - число ячеек (карманов) в таблице
Заполнение - ожидаемое число коллизий при занесении таблицу 20 объектов
Поиск - ожидаемое число проверок при поиске объекта, находящегося в таблице
Поиск 2 - ожидаемое число проверок при поиске объекта, отсутствующего в таблице (до выяснения этого факта)

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

Страницы: (2) 1 [2] все

[ Script execution time: 0,0194 ] [ 16 queries used ] [ Generated: 19.04.24, 01:57 GMT ]