Хэш-карты и хэш-код, которые изменяются, как сказать набору, что объект изменился?

вопрос по хэш-картам и хэш-кодам

Имейте POJO, переписанный хэш-код и равные, чтобы помочь с конкретным компаратором (здесь не показано)

package coll.hset;

public class Dat {

    private String name;
    private String dat;
    private int aa;//some business reason not used in hashcode and equals

    public int hashCode(){
        int h = 0 ;
        if(name != null){
            h += name.hashCode();
        }
        if(dat != null){
            h += dat.hashCode();
        }
        return h;
    }

    public boolean equals(Object o){
        if(o instanceof Dat){
            Dat oo = (Dat)o;
            if(this.name ==null && oo.name != null){
                return false;
            }else if(!name.equals(oo.name)){
                return false;
            }

            if(this.dat ==null && oo.dat != null){
                return false;
            }else if(!dat.equals(oo.dat)){
                return false;
            }
            return true;
        }
        return false;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getDat() {
        return dat;
    }

    public void setDat(String dat) {
        this.dat = dat;
    }

    public int getAa() {
        return aa;
    }

    public void setAa(int aa) {
        this.aa = aa;
    }

}

Пользовательское приложение:

    package coll.hset;

import java.util.HashSet;
import java.util.Random;

public class App {

    final static int SZ = 2 ^ 8;

    /**
     * @param args
     */
    public static void main(String[] args) {
        Random rndm = new Random();// to create random data
        Dat dd;// reference while filling up set
        Dat[] d2 = new Dat[500];// save a few here for later ops
        int fills = 0;
        HashSet<Dat> dats = new HashSet<Dat>();// set
        for (int i = 0; i < 10000; i++) {
            dd = new Dat();
            dd.setAa(i);
            // fill random dat and name.
            char v = (char) (65 + rndm.nextInt(26));
            dd.setDat("a " + v);
            v = (char) (65 + rndm.nextInt(26));
            char v1 = (char) (65 + rndm.nextInt(26));
            char v2 = (char) (65 + rndm.nextInt(26));
            char v3 = (char) (65 + rndm.nextInt(26));
            char v4 = (char) (65 + rndm.nextInt(26));
            dd.setName(v + " " + v1 + v2 + v3 + v1 + v + v4);
            dats.add(dd);
            if (i % 60 == 0) {
                d2[fills++] = dd;
            }

        }
        Dat ref = d2[0];
        int hash = hash(ref.hashCode());
        int idx = indexFor(hash, SZ);
        boolean has1 = dats.contains(d2[0]);
        System.out.println("has d 0 :" + has1 + ", name :" + ref.getName() + ", hash :" + ref.hashCode() + ". hash2 :" + hash + ", idx :" + idx + ", when size of table :" + SZ);

        d2[0].setName(ref.getName() + "l");
        // d2[0].setName(ref.getName() + "l");
        d2[0].setName("Tony G");
        // ref.setDat("sd=");
        hash = hash(ref.hashCode());
        // if you run this many times will see that for some cases the table is the same, so a quicker rehash, instead of remove and add back after change is what I'm after
        idx = indexFor(hash, SZ);
        has1 = dats.contains(d2[0]);
        System.out.println("has d 0 after name change :" + has1 + ", name :" + ref.getName() + ".");
        System.out.println("has d 0 :" + has1 + ", name :" + ref.getName() + ", hash :" + ref.hashCode() + ". hash2 :" + hash + ", idx :" + idx + ", when size of table :" + SZ);
        System.out.println(" at : " + new java.util.Date());

    }

    static int hash(int h) {
        // From Sun Java impl
        /*
         * / This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor).
         */
        h ^= (h >>> 20) ^ (h >>> 12);

        return h ^ (h >>> 7) ^ (h >>> 4);

    }

    static int indexFor(int h, int length) {
        return h & (length - 1);
    }
}

Как и ожидалось, 2-й поиск говорит, что объект d2[0] отсутствует в наборе, даже если он есть. Я знаю, как это исправить - один из способов - удалить, изменить и снова добавить. Есть ли другой способ сообщить набору, что мы мутируем конкретный объект?

Из http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.remove%28java.lang.Объект%29

Можно увидеть, как Oracle/Sun Java HashMap перефразирует себя. Вопрос в том, можем ли мы добавить новый метод, который сообщает набору - пожалуйста, перефразируйте этот объект, вместо того, чтобы удалять и добавлять его обратно, чтобы он был более эффективным.

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


person tgkprog    schedule 24.04.2014    source источник
comment
Код очень трудно читать из-за ваших не говорящих переменных. Например. Было бы лучше, если бы имя rr было random.   -  person Absurd-Mind    schedule 24.04.2014
comment
Просто: Не меняйте его!   -  person Seelenvirtuose    schedule 24.04.2014
comment
Так что скажите нашим бизнес-пользователям - эй, пожалуйста, не меняйте свое имя или текущий адрес? думаю, нет   -  person tgkprog    schedule 24.04.2014
comment
@tgkprog Кто сказал вашим бизнес-пользователям не менять имя или адрес? Что я имел в виду: просто не меняйте объект, который используется в качестве ключа в HashMap или помещается в HashSet. Точка. Кстати, для этого лучше всего использовать неизменяемые объекты. Если вы чувствуете, что должны изменить это, у вас действительно проблема с дизайном.   -  person Seelenvirtuose    schedule 24.04.2014


Ответы (2)


Хэш объекта считается постоянным в течение всего срока службы объекта, поэтому строгий ответ на ваш вопрос: нет. Когда вы изменяете свой объект таким образом, что его хэш-код изменяется, вам лучше удалить его с карты и снова добавить.

person Kirill Gamazkov    schedule 24.04.2014
comment
Правильно, я сказал это в самом вопросе, мне было интересно, есть ли более быстрый способ, чтобы для большего набора он мог тратить меньше времени на удаление (перефразирование) - person tgkprog; 24.04.2014
comment
Я не думаю, что есть более быстрый способ. Как следует из структуры данных хэш-карты, измененный хеш потребует перемещения объекта из одного сегмента в другой. Такой ход фактически является повторным добавлением объекта на карту. - person Kirill Gamazkov; 24.04.2014

Всякий раз, когда функция hashcode() вызывается для одного и того же объекта более одного раза во время выполнения приложения Java, метод hashCode должен постоянно возвращать одно и то же целое число, при условии, что никакая информация, используемая в сравнениях на равенство для объекта, не изменяется. Это целое число не обязательно должно оставаться согласованным от одного выполнения приложения к другому выполнению того же приложения. Поэтому @kiril предложил удалить его с карты и снова добавить.

person Sanjay Rabari    schedule 24.04.2014