Как протестировать хеш-функцию?
Создайте JSONObject из строки. Затем получите значение из ключа ...
JSONObject jsonResponse = new JSONObject(response.toString());
String value = jsonResponse.getString("Key");
Обратите внимание, что строка должна быть правильно отформатирована JSON.
4 ответа
Необходимо протестировать хеш-функцию с помощью данных, оттянутых из того же (или подобный) распределение, что Вы ожидаете, что это продолжит работать. При рассмотрении хеш-функций на 64-разрядном longs хеш-функция Java по умолчанию превосходна, если входные значения оттянуты однородно из всех возможных длинных значений.
Однако Вы упомянули, что Ваше приложение использует длинное для хранения по существу двух независимых 32-разрядных значений. Попытайтесь генерировать образец значений, подобных тем, Вы ожидаете на самом деле использовать, и затем тестировать с этим.
Для самого теста, возьмите свои демонстрационные входные значения, хешируйте каждого и поместите результаты в набор. Считайте размер получающегося набора и сравните его с размером входного набора, и это скажет Вам количество коллизий, которые генерирует Ваша хеш-функция.
Для Вашего конкретного приложения, вместо просто XORing их вместе, попытка комбинировать 32-разрядные значения способами типичная хорошая хеш-функция объединила бы два indepenet ints. Т.е. умножьтесь началом, и добавьте.
Сначала я думаю, что необходимо определить то, что Вы подразумеваете под хорошим распространением себе. Вы имеете в виду хорошее распространение для всего возможного входа или просто хорошее распространение для вероятного входа?
, Например, при хешировании строк, которые представляют надлежащий полный (first+last) имена, Вы не идете в вероятную заботу о том, как вещи с числовыми символами ASCII хешируют.
Что касается тестирования, Ваш лучший выбор состоит в том, чтобы, вероятно, получить огромный или случайный входной набор данных, которые Вы ожидаете, и продвигаете его через хеш-функцию и видите, как распространение заканчивается. Там вряд ли будет волшебной программой, в которой может быть сказано "да, Это - хорошая хеш-функция для Вашего варианта использования".. Однако, если можно программно генерировать входные данные, необходимо легко смочь создать модульный тест, который генерирует существенное количество их, и затем проверьте, что распространение в рамках определения пользы.
Редактирование: В Вашем случае с 64 бита длиной, там даже действительно причина использовать карту хеша? Почему не только используют сбалансированное дерево непосредственно и используют длинное в качестве ключа непосредственно вместо того, чтобы перехешировать его? Вы платите немного штрафа в полном размере узла (2x размер для значения ключа), но можете закончить тем, что сохранили его в производительности.
На основе Вашего разъяснения:
я использовал длинные значения в Java таким способом, которым первые 32 бита закодировали идентификатор, и вторые 32 бита закодировали другой идентификатор. К сожалению, хеш Java длинных значений просто XORs первые 32 бита со вторыми 32 битами, который в моем случае, ведомом к очень низкой производительности при использовании в HashMap.
кажется, что у Вас есть некоторые несчастные "резонансы" между способом, которым Вы присваиваете эти два Значений идентификаторов и размеры Ваших экземпляров HashMap.
Вы явно калибровка Ваших карт или использование значений по умолчанию? Проверка QAD, кажется, указывает, что HashMap<Long,String> запускается со структуры с 16 блоками и удваивается на переполнении. Это означало бы, что только биты младшего разряда Значений идентификаторов на самом деле участвуют в выборе блока хеша. Вы могли попытаться использовать одного из конструкторов, который берет параметр начального размера, и создайте свои карты с главным начальным размером.
Поочередно, предложение L Dave определения Вашего собственного хеширования длинных ключей позволило бы Вам избегать проблемы зависимости младшего бита.
Другой способ посмотреть это - то, что Вы используете тип примитива (долго) в качестве способа постараться не определять реальный класс. Я предложил бы смотреть на преимущества, которых Вы могли достигнуть путем определения бизнес-классов и затем реализации хэширования, равенства и других методов как соответствующих на собственных классах для управления этой проблемой.
Если Ваше использование хеш-таблицы объединения в цепочку, о чем Вы действительно заботитесь, является количеством коллизий. Это было бы тривиально для реализации как простой счетчик на хеш-таблице. Каждый раз объект вставляется, и таблица должна объединить в цепочку, увеличить цепочечный счетчик. Лучший алгоритм хеширования приведет к более низкому количеству коллизий. Хорошая хеш-функция таблицы общего назначения для проверки: djb2