Это хороший подход для генерации хэш-кодов? - PullRequest
Новая
       21

Это хороший подход для генерации хэш-кодов?

3 голосов
/ 08 июля 2011

Я должен написать хеш-функцию при следующих двух условиях:

  • Я ничего не знаю о Object o, который передается методу - это может быть строка, иЦелое число или фактический пользовательский объект;
  • Мне вообще не разрешено вызывать hashCode().

Подход, который я сейчас использую, для вычисления хэш-кода:

  1. Запись объекта в байтовый поток;
  2. Преобразование байтового потока в байтовый массив;

  3. Циклическое преобразование байтового массива и вычисление хэша с помощью чего-то подобного:

    hash = hash * PRIME + byteArray [i]

Мой вопрос - это приемлемый подход и есть ли способ его улучшить?Лично я чувствую, что область действия этой функции слишком широка - нет информации о том, что это за объекты, но я мало что могу сказать в этой ситуации.

Ответы [ 5 ]

3 голосов
/ 08 июля 2011

Вы можете использовать HashCodeBuilder.reflectionHashCode вместо реализации собственного решения.

1 голос
/ 08 июля 2011

Подход сериализации работает только для объектов, которые на самом деле сериализуемы. Таким образом, для все типы объектов на самом деле невозможны.

Кроме того, это сравнивает объекты на и имеют эквивалентные графы объектов , которые не обязательно совпадают с равными .equals().

Например, объекты StringBuilder, созданные одним и тем же кодом (с одинаковыми данными), будут иметь одинаковый выходной сигнал OOS (т. Е. Также равный хеш), тогда как b1.equals(b2) равен false, а ArrayList и LinkedList с одинаковыми элементами будут зарегистрированы как отличается, в то время как list1.equals(list2) равно true.

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

class HashOutputStream extends OutputStream {

    private static final int PRIME = 13;
    private int hash;

    // all the other write methods delegate to this one
    public void write(int b) {
        this.hash = this.hash * PRIME + b;
    }

    public int getHash() {
        return hash;
    }
}

Затем оберните ваш ObjectOutputStream вокруг объекта этого класса.

Вместо вашего y = y*13 + x метода вы можете посмотреть другие алгоритмы контрольной суммы. Например, java.util.zip содержит Adler32 (используется в формате zlib) и CRC32 (используется в формате gzip).

0 голосов
/ 08 июля 2011

Взгляните на статью Боба Дженкина о некриптографическом хешировании. Он рассматривает несколько подходов и обсуждает их сильные и слабые стороны и компромиссы между скоростью и вероятностью столкновений.

Если ничего другого, это позволит вам обосновать свой алгоритм решения. Объясните своему инструктору, почему вы выбрали скорость вместо правильности или наоборот.

В качестве отправной точки попробуйте его Единовременный хеш : 

ub4 one_at_a_time(char *key, ub4 len)
{
  ub4   hash, i;
  for (hash=0, i=0; i<len; ++i)
  {
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return (hash & mask);
}

Это просто, но на удивление хорошо справляется с более сложными алгоритмами.

0 голосов
/ 08 июля 2011

Кроме того, если вы хотите избежать коллизий, вы можете использовать стандартизированную (криптографическую, если умышленные коллизии проблема возникает) хэш-функцию на шаге 3, как SHA-2 или около того?

Взгляните на DigestInputStream, что также избавит вас от шага 2.

0 голосов
/ 08 июля 2011

hash = (hash * PRIME + byteArray [i])% MODULO?

...