D
D
Denis Kuznetsov2019-06-17 20:03:50
Java
Denis Kuznetsov, 2019-06-17 20:03:50

How exactly does map work?

Hello, I wondered about the structure and operation of Map after reading several articles. I could not find the answers to these questions or missed them in a cursory reading.
I have such a key class

public class KeyClass {

    private int firstKeyValue;
    private String secondKeyValue;

    public KeyClass(int firstKeyValue, String secondKeyValue) {
        this.firstKeyValue = firstKeyValue;
        this.secondKeyValue = secondKeyValue;
    }

    public int getFirstKeyValue() {
        return firstKeyValue;
    }

    public void setFirstKeyValue(int firstKeyValue) {
        this.firstKeyValue = firstKeyValue;
    }

    public String getSecondKeyValue() {
        return secondKeyValue;
    }

    public void setSecondKeyValue(String secondKeyValue) {
        this.secondKeyValue = secondKeyValue;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) {
            return true;
        }

        if (obj == null || obj.getClass() != this.getClass()) {
            return false;
        }

        KeyClass o = (KeyClass) obj;

        return (firstKeyValue == o.firstKeyValue) && (secondKeyValue.equals(o.secondKeyValue));
    }

    @Override
    public int hashCode() {
        char[] array = secondKeyValue.toCharArray();

        int sum = 0;

        for(int i = 0; i < array.length; ++i){
            sum += array[i];
        }
        return firstKeyValue + sum;
    }
}

and own main method
public class Main {

    public static void main(String[] args) {
        KeyClass keyClass = new KeyClass(1, "one");

        Map map = new HashMap<KeyClass, String>();

        //завели бакет по этому ключу(номер бакета определяется по хешу)
        map.put(keyClass, "first");

        //поменяли ключ(надеемся на потерю значения)
        keyClass.setFirstKeyValue(23);
        keyClass.setSecondKeyValue(new String("one")); //чтобы даже не в пуле лежала а просто в хипе(чтоб наверняка :в )

        //выведет null (так как элемент утерян) Отлично!!!
        System.out.println("first value " + map.get(keyClass));

        //выведет null (так как такого элемента нет) Отлично!!!
        System.out.println("unexisted value " + map.get("str"));

        //размер 1 так как элемент все равно внтури (несмотря на то, что он утерян)
        //вроде по умолчанию же 16 должен быть???  load factor все дела ?!
        System.out.println("size " + map.size());

        //кладем в новый бакет(старый с "first" все еще существует)
        map.put(keyClass, "alien");
        System.out.println("basket with alien" + map.get(keyClass));

        //тут я решил посмотреть как будет работать хеш код с учетом неинтернированной строки
        System.out.println("hashCode1 : " + keyClass.hashCode());
        System.out.println("hashCode2 : " + new KeyClass(23, "one").hashCode());
        //хеш одинаковый так как по моему переопределению хешкода место в памяти никак не влияет (ну типа да я так и задумывал)
        // но, я в строке использую int значения кодировки символа так что надо рассмотреть следующее
        System.out.println("hashCode3 : " + new KeyClass(23, "eno").hashCode()); //ага!!!!!!(хеш такой же)
        System.out.println("equals method : "+ new KeyClass(23, "one").equals(new KeyClass(23, "eno"))); //дает false, значит я молодец

        //заводим новый бакет
        KeyClass anotherOne = new KeyClass(23, "two");
        map.put(anotherOne, "new");

        //заводим бакет который который будет всегда первым
        map.put(null, null);
        //значение перетерлось так как hashCode одинаков и equals вернул true
        map.put(null, "afterNull");

        //тут происходит перетерание по той же причине что и выше, я вообще рассчитывал на лист
        map.put(keyClass, "second");
        map.put(keyClass, "third");

        //и тут поидее я добавляю элемент в бакет с хешом как у keyClass переменной(тоесть "third" и "addToList" должны сформировать лист)
        map.put(new KeyClass(23, "eno"), "addToList");

        //и тут лежит только third ?!
        //Но ведь в случае если хеш одинаковый и equals true, эл-т затирается, а если hash одинаковый но equals false, то создается лист
        System.out.println("List : " + map.get(keyClass));

        //выведет [afterNull, new, first, third, addToList] но тут мы листа не видим ?!
        System.out.println(Arrays.toString(map.values().toArray()));

    }
}

1) why is the length value 1 and not the default one?
2) Are my reasonings described in the comments correct?
3) Why didn't I manage to get the sheet?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
D
Denis Zagaevsky, 2019-06-17
@DennisKingsman

size just returns how many keys are actually in the folder.
All your arguments about "started a bucket", "put in a new bucket" are wrong. You don't start anything, these are implementation details of the hash table. A bucket is a linked list containing key-value pairs whose key hash is modulo the number of buckets. This is the list you dream of getting, and it doesn't work that way. That is, you will not get it, because these are implementation details.
And further, you broke this implementation with your mutable keys. The list now contains a key whose hash does not match the list. Naturally, the map will not find anything by this key, as it will search in another list (bucket). Conclusion - never mutate keys.

//we start a bucket which will always be the first
map.put(null, null);
//value was overwritten because hashCode is the same and equals returned true
map.put(null, "afterNull");

No, it's not like that. Null is processed simply separately, under it a separate element, this is not a bucket.
When you put different values ​​into the map with the same key, the later one overwrites the old one. Simply because that's the essence of the hash table, and that's why it's implemented that way. Buckets do not store keys with the same hash, they store keys with hashes that are the same modulo the number of buckets.
How many buckets are currently in the map should not bother you at all.
Read code. It can be seen that somewhere you picked up an incorrectly (or poorly) chewed theory, and you are trying to get out of it. Most of your questions will be removed by hashmap sources and, in extreme cases, a debugger.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question