Только полноправные пользователи могут оставлять комментарии. TM Feed Хабрахабр Geektimes Тостер Мой круг Фрилансим. Хабрахабр Публикации Пользователи Хабы Компании Песочница. Часто на собеседованиях приходится спрашивать про функцию hashCode. Я не буду здесь перечислять все свойства этой функции и ее связь с другой, не менее важной функцией equals. Данная информация есть во всех учебниках по Java и я не вижу смысла ее здесь повторять. Мне бы хотелось остановиться лишь на одном свойстве: Мне бы хотелось, чтобы меня поправили, если я где-то ошибся в рассуждениях. Спросим у Гуру Вначале я решил обратиться к Java документации на Object. Как каждый может убедиться, там нет информации, которая нас интересует. После этого я пошел к Гуру. Джошуа Блох поступил лучше: Я не могу не удержаться от цитирования: The multiplier 37 was chosen because it is an odd prime. Никто из авторов не удосужился провести анализ приведенного алгоритма и доказать его корректность. Алгоритм в вольном пересказе 1 Взять число, отличное от нуля, к примеру Для удобства, назовем его p. Эти правила, нас сейчас не очень интересуют, они не влияют на результат. Для простоты будем работать с целыми числами int и будем принимать hashCode равным самому значению числа… 3 Скомбинировать result и полученный hashCode с: Анализ алгоритма Сначала сделаем несколько допущений: То есть мы не будем работать с отрицательными значениями. Будем использовать только небольшие исходные значения. Запишем hash функцию для точки P1 x1, y1: Теперь я хочу рассмотреть какую-нибудь другую точку P2 x2, y2 у которой будет такая же hash функция. То есть это как раз случай коллизии: Можно предложить такой вариант: Теперь рассмотрим случай n переменных, независимо изменяющихся от 0 до некоторого M. Хотелось бы найти максимальное значение M, такое, что хорошо написанная функция hashCode не имела бы коллизий на промежутке от 0 до M по всем n переменным. После недолгих раздумий, получаем значение для M: Для случая точек на плоскости M принимает значение Похоже, что формула, приведенная Блохом, будет давать приемлемое распределение hash кодов для случая 8 и более переменных. Рассмотрим теперь точки в трехмерном пространстве. Напишем небольшую программу, которая в тройном цикле перебирает точки от 0 до всего миллион точек и считает количество коллизий. Код этой программы элементарный, поэтому не буду его здесь приводить. Получается, что Блох, под видом hash функции, предложил функцию для получения коллизий? Хороший hashCode для случая двух переменных Теперь попробуем построить хороший алгоритм для случая двух переменных x1, y1. Чтобы равномерно раскидать значения x1 и y1 на числовой плоскости, воспользуемся умножением: Пока не будем накладывать на p и q никаких условий. Для получения значения hash функции, сложим эти произведения: Из последней формулы и из того факта, что мы работаем с целыми числами, следует: Отсюда следует, что p и q должны быть меньше К примеру и Тут следует напомнить о нашем допущении: Когда произойдет переполнение при сложении, мы окажемся в отрицательной части числовой оси. Предлагаю читателям поразмыслить над этим самостоятельно Выводы Как писал Дональд Кнут в главе про генератор псевдослучайных последовательностей, если алгоритм выглядит сложно и запутанно, это еще не означает, что он работает правильно недословное изложение. Те кто используют реализацию hash функции от Джошуа Блоха, но имеют большое количество хешируемых переменных, могут спать спокойно. Так же могут не волноваться те, у кого различного рода Hash-коллекции не являются узким местом в производительности. Если же вы бьетесь за производительность своего кода, учитываете все возможные мелочи, то вам, пожалуй, следует взглянуть на свои реализации hashCode свежим взглядом. Учитывая, что хешируемые значения, могут быть не равномерно распределены для вашей конкретной бизнес области, вы сможете написать hash функцию с лучшим распределением hash кодов, чем любой сгенерированный вариант. Переписав hashCode , вам, возможно, следует взглянуть на equals: Спасибо тем, кто дочитал до конца. Python авторов , 1,8k публикаций. Программирование 2,9k авторов , 6,5k публикаций. Разработка мобильных приложений 1k авторов , 2,8k публикаций. Open source 1k авторов , 2,3k публикаций. Алгоритмы 1,3k авторов , 2,3k публикаций. Машинное обучение авторов , публикаций. Разработка веб-сайтов 4,1k авторов , 9,6k публикаций. Разработка под Linux авторов , публикаций. Информационная безопасность 2,4k авторов , 6,4k публикаций. Qt авторов , публикации. Яндекс открывает технологию машинного обучения CatBoost 3,7k Добавить в закладки По-моему там будет достаточно равномерное распределение. В этом случае Вам будет тяжело по hash коду различить даже 1, 0 и 0, 1. Единственное четное простое число это 2…. Поэтому на малых x,y плотность коллизий большая, и поэтому на малых значениях лУчший результат показывает выбор бОльшего простого множителя, который разносит соседние значения дальше. Есть подозрение, что если проверить диапазон , — результат может заметно измениться. Но вообще — да, конечно, если нужно выжимать максимум, нужно внимательно смотреть на хэшфункции. Но тогда уж и на реализацию хэштаблицы нужно смотреть очень внимательно. Руслан, я проверял этот диапазон. Прошу прощения, промахнулся с ответом. Первый вопрос — а как вы думаете, почему в стандартной библиотеке используется chaining HashMap, когда open addressing, вообще говоря, в разы быстрее и в разы компактнее? Мое предположение — как раз потому, что chaining более толерантен к плохой хэш-функции. Тут уже правильно замечали — однократные коллизии мало что меняют, их практически нереально избежать для хэш-функции общего вида. Важно, чтобы не было явно выделенных точек, вокруг которых кучкуются значения хэша. Вы берете просто количество коллизий — это ок для прикидки, но не вполне понятно, как это скажется на реальной работе. По-хорошему качество хэша надо проверять так: Брать другую хэш-функцию, делать то же самое. Я так буквально недавно выбирал хэш-функцию для справочников. Еще ближе был бы эксперимент с последующим чтением некой подвыборки ключей, и подсчетом среднего количества проб — тут прямая хоть и не обязательно точная оценка именно производительности — того, что, в конечном счете, и нужно от хорошего хэша. Над конкретной задачей я бы работал примерно таким образом. Для 3-х переменных степень при 37 будет равна трем. Понятно, что после переполнения этот промежуток тоже будет использован, но как-то не очень красиво. Собственно, подобную ошибку допустил и я в своем примере. Правильная hash функция будет иметь вид: Если не ошибаюсь, то про использование простого числа как основание хэша написал Дональд Кнут в третьем томе про сортировку и поиск вроде как и это не является какой-то магией. Универсальная реализация, предложенная Блохом, на то и универсальная, чтобы не делать никаких предположений относительно значений ваших полей. В случае с int считается, что любое значение равновероятно. Было бы не очень красиво, если бы универсальная функция снижала число коллизий в диапазоне Или идут с каким-нибудь хитрым шагом? Для любой хэш-функции можно подобрать неподходящие данные. И наоборот — если вы знаете о данных наперёд, ничто не мешает подобрать подходящую хэш-функцию. Универсальная реализация может быть хорошая, а может быть и не очень. Для примера из 3 short полей как у Блоха эта реализация не очень удачная. Если человеку нужно реализовать hashCode , то он, обычно, или сгенерирует его с средствами IDE или обратиться к Блоху или Эккелю. И получит не очень хороший результат. Меня смущает, что Блох не проводит оценки качества своего алгоритма. И не заостряет внимание на то, что этим нужно заняться, если у вас высоконагруженная система. Коллизии — это, конечно, интересно. Но более интересно, все-таки, распределение. Если одинаковый хэш будет у 3х элементов — это не страшно. А вот если у , то это гораздо хуже. Дальше, Вы рассматриваете сплошной интервал, а это не отражает реальности. Если вам надо обращаться по значению в сплошном интервале или в почти заполненном, легче воспользоваться массивами или другими более продвинутыми структурами, которые дадут быстрый доступ к нужному элементу. В реальности интересен такой вопрос: Есть еще другой аспект — скорость вычисления хэш-функции. Найти элемент в списке из 3х может быть легче, чем вычислить сложную хэш-функцию, которая не будет давать коллизий. Ну и, естественно, бросаться переписывать хэш-функции стоит только тогда когда вы точно знаете, что причина низкой производительности в них. Своей статьёй я хотел поднять вопрос, который особо нигде не обсуждается. Множим первое значение на просто число. Множим второе значение на простое число. И так со всеми значениями. Даёт результат близкий к оптимальному. Простые числа вбираются так, чтобы они были максимально равномерно распределены в диапазоне Быстро, хорошо, удобно, теоретически обосновано. И на всякий случай, вариант без умножения таки довольно тяжёлая операция: Пространство хеш-функции делим пропорцинально кол-ву составляющий. В нашему случае - 32 бита хеш-функция делится на два диапазона по 16 бит. Да, кстати, каюсь и посыпаю голову пеплом — это не хэш-функция в чистом виде. Это скорее многопоточный генератор псведослучайных чисел. Подсмотрен, если не ошибаюсь, в каких-то исходниках Java, где использовался в качестве генератора хэш-значения по-умолчанию для объектов чистую хэш функцию от адреса использовать нельзя, так как из-за работы сборщика мусора, выравнивания и сжатия указателей высока вероятность того, что объекты будут выделяться по одним и тем же адресам и вызывать коллизии. В результате там есть такой алгоритм. Один из параметров — threadID. Второй — адрес объекта. Позволяет генерировать псевдослучайный хэш независимо для каждого потока. В нынешней Java-машине есть ключ, который этот режим включает по-идее, повышает производительность если создаётся много объектов. Не разделяю я любовь отечественных программистов к функции XOR. В промежутке от 0 до — нет коллизий. В промежутке от 0 до получаем уже коллизии. Заменяем XOR на обычное сложение — коллизий не будет и в более широком промежутке. Есть мнение, что равномерность распределения тоже важна. Почему до рассматриваете? В общем случае, если у нас какие-то достаточно случайные значения на входе, то коллизий будет примерно одинаково, но xor даст более равномерное распределение хэшей. Хотя, это все довольно спицифично для задачи. А любовь растет, на сколько я понимаю, из мнения, что две различные операции уменьшают вероятность коллизий при дальнейшей обработке. Интервал до я взял просто для примера чтобы не долго считалось. Если Ваш алгоритм вычисление хеша имеет коллизии на таком интервале, то он будет иметь их и на большем интервале. А для моего алгоритма есть теоретическое обоснование отсутствия коллизий на интервале от 0 до 2 Я не предлагаю сейчас начинать спор о допустимости использования функции XOR. Для двух переменных это не очень оправдано, а, возможно, для 10 — будет в самый раз. Только вот для HaspMap не так уж требуются хэши в диапазоне Одно дело иметь хорошую hash функцию и осознанно не использовать всех ее свойств, и совсем другое дело думать, что имеешь хорошую hash функцию, но ошибаться. С точки зрение чего она хорошая? Вы посмотрите в исходники HashMap — там полученное от объекта значение хэш-код ещё раз трансформируется метод hash , так что там, где у вас коллизий не было, в таблице они могут быть. Только нужно понимать, что если у Вас в исходной hash функции не было коллизий, то HashMap может странсформирует Ваш hashCode в коллизию для другого hash кода, а может и нет. А если у Вас изначально есть коллизия, то и в результате коллизия будет гарантирована. Для тех, кто все еще не верит, что hash функция от Блоха не очень хороша, проведем небольшой эксперимент. Возьмем промежуток от 0 до 2 16 , возьмем случайную точку на плоскости примерно из середины этого промежутка. Переберем все точки на заданном промежутке и посчитаем коллизии. У меня получилось Много это или мало — пусть каждый решает сам. Метки лучше разделять запятой. Сейчас Вчера Неделя Основы CQRS 1,4k Муда брака 12,4k Интересные публикации Хабрахабр Geektimes. Как снизить риски GT. Бот для Telegram за 48 часов на Perl или как купить кошачий корм не выходя из чата. Яндекс открывает технологию машинного обучения CatBoost. Как устроено расписание электричек. Занимательные факты о бетоне GT. Cisco Meeting Server — теперь вся видео-конференц-связь из одного места. Ночные контактные линзы для тех, кто не носит очки, но боится при этом коррекции GT. Разделы Публикации Хабы Компании Пользователи Песочница. Информация О сайте Правила Помощь Соглашение Конфиденциальность. Услуги Реклама Тарифы Контент Семинары.
Новости газпром добыча
Прыгать без скакалки можно похудеть
Хеш-таблица
Как повесить шторы на шторной ленте видео
Present perfect festival
Видеорегистратор х5 инструкция
Статьи 437 2 гражданского кодекса рф
Барьер к осмос
Кресты в колпино карта
Диагностическая карта для осаго в ясенево
Период республики в истории рима
Огурец зозуля f1 описание
Хеш-таблица
Аквамарис спрей для носа инструкция по применению
Что делает оператор эвм
Город где живет дед мороз
Научная работа основные характеристики
Флюгер из дисков своими руками фото чертежи
Хеш-таблица
Акбар перевод на русский с арабского
Автобус 62 химки маршрут расписание
Статистика основные понятияи формулы
Заявление на возмещение расходов на представителя образец