Равномерное распределение хэш-кода()

Я определяю свой класс как:

final class Key<T extends Comparable<T>> {
    private final T q;
    private final T o;
    public Key(T q1, T o1) {
        q = q1;
        o = o1;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj != null && obj instanceof Key) {
            Key<T> s = (Key<T>)obj;
            return q.equals(s.q) && o.equals(s.o);
        }
        return false;
    }

    @Override
    public int hashCode() {
        return Objects.hash(q,o);
    }
}

Я также определяю массив, содержащий ключ объекта. Например:

Object arr[] = new Object[100];
Key<String> k = new Key<>("a","b");
int h = k.hashcode();
...
arr[h+i % h] = k; //i from 1 to 10 for example

Проблема в том, что hashcode() может возвращать отрицательное значение, поэтому

arr[h+i % h] = k;

может вернуть ошибку из индекса массива. Вот почему я изменил свой код как (на основе моего поиска, чтобы избежать отрицательного значения hashcode()):

@Override
        public int hashCode() {
            return (Objects.hash(q,o)&0x7FFFFFFF);
        }

Итак, если я сделаю это таким образом, изменится ли равномерное распределение хэш-кода () или нет? Я имею в виду, что вероятность иметь одинаковое значение из двух разных объектов будет увеличена или нет?


java hashcode hash-collision
person nd07    schedule 15.04.2016    source источник
comment
Как вы можете создать объект ключа как Key‹String,String›. Это должно дать ошибку компилятора как неправильное количество аргументов для типа Key‹T›   -  person Roshan    schedule 15.04.2016
comment
Да, моя ошибка. Я также отредактировал его. Спасибо   -  person nd07    schedule 15.04.2016
comment
вы можете взглянуть на хэш бормотания, который имеет очень хорошее распространение. и не может быть отрицательным значением   -  person Ram Ghadiyaram    schedule 17.05.2016

Ответы (2)


arrow_upward
3
arrow_downward

Пожалуйста, загляните в Murmurhash и MurmurHash - что это такое? К счастью, в Google guava есть готовая реализация для этого.

Путь гуавы подобен приведенному ниже примеру. У нас есть следующие классы.

import com.google.common.hash.HashCode; import com.google.common.hash.HashFunction; import com.google.common.hash.Hashing;

используя приведенные выше классы, у меня есть метод для генерации хэш-кода, как показано ниже.

/**
     * getMurmur128Hash.
     * 
     * @param content
     * @return HashCode
     */
    public static HashCode getMurmur128Hash(String content) {
        final HashFunction hf = Hashing.murmur3_128();
        final HashCode hc = hf.newHasher().putString(content, Charsets.UTF_8).hash();
        return hc;
    }
    /**
     * getAbsMurmur128HashAsLongVal.
     * 
     * @param content
     * @return Long Absolute value of Long for the HashCode.
     */
    public static Long getAbsMurmur128HashAsLongVal(String content) {
        return Math.abs(getMurmur128Hash(content).asLong());
    }
person Ram Ghadiyaram    schedule 17.05.2016

arrow_upward
2
arrow_downward

Object.hash() имеет очень простой хэш-код, который не особенно однороден для простых примеров. например Objects.hash("B", "B") и Objects.hash("A", "a") имеют одинаковый хэш-код. (И, кстати, достаточно просто, чтобы я мог решить это в своей голове)

Также каждый между Objects.hashCode("a", "a") и Objects.hashCode("z", "z") находится между 4065 и 4865, что не выглядит особенно однородным, особенно для старших бит.

В этом контексте, я думаю, вы можете сказать, что не усугубляете ситуацию.

person Peter Lawrey    schedule 15.04.2016
comment
Если так. каким образом лучше избегать отрицательного значения hashcode() 1. как указано выше 2. избегать отрицательного значения на этом шаге: arr[h+i % h] = k. Я имею в виду, что использую Math.abs(h+i % h) для преобразования в положительное значение. - person nd07; 15.04.2016
comment
@ nd07 Вы хотите избежать здесь Math.abs, так как это может вернуть отрицательное число o_O (hash & 0x7FFF_FFFF) % buckets лучше. Примечание: Math.abs(Integer.MIN_VALUE) == Integer.MIN_VALUE которое вы вряд ли узнаете еще долго. - person Peter Lawrey; 15.04.2016