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

Question

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

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

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

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

3. Переберите байтовый массив и вычислите хеш, выполнив что-то вроде этого:

   hash = hash * PRIME + byteArray [i]

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

Answer 1

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

Answer 2

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

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

Например, объекты StringBuilder, созданные одним и тем же кодом (с одинаковыми данными), будут иметь одинаковый выходной сигнал OOS (то есть также равный хеш), в то время как b1.equals(b2) ложно, и 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 формат).

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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);
} 

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