Пример столкновения Java HashMap не работает - PullRequest
Новая
       9

Пример столкновения Java HashMap не работает

0 голосов
/ 10 августа 2011

Насколько я понимаю, реализация HashMap на Java использует «сегменты», которые указывают на список значений для обработки коллизий, и что объект будет переопределен только в том случае, если hashCode () для ключа И equals () для объекта ОБА одинаковы для добавляемого объекта и объекта, с которым он сталкивается.

Я пытался поиграть с HashMap, чтобы попытаться увидеть поведение столкновения в действии, но независимо от того, что я делаю, оно всегда переопределяется.

Что я здесь не так делаю (обратите внимание, что я намеренно оставил "count" вне методов hashCode и equals)? 

public class HashMapTest {

public static void main(String[] args) {
    HashMapTest test = new HashMapTest();
    test.execute();
}

public void execute() {
    HashMap<String, Node> nodeMap = new HashMap<String, Node>();
    Node node1 = new Node("data1", 1);
    Node node2 = new Node("data2", 2);

    String key = "1";

    System.out.println("node1 hash: " + node1.hashCode());
    System.out.println("node2 hash: " + node2.hashCode());
    System.out.println("node1 hash == node2 hash? " + (node1.hashCode() == node2.hashCode() ? "true" : "false"));
    System.out.println("node1.equals(node2)? " + (node1.equals(node2) ? "true" : "false"));

    nodeMap.put(key, node1);
    System.out.println("added node1 to hash map");
    System.out.println("hash map size: " + nodeMap.size());
    System.out.println("hash map entry set size: " + nodeMap.entrySet().size());
    System.out.println("hash map contains node1? " + (nodeMap.containsValue(node1) ? "true" : "false"));
    System.out.println("hash map contains node2? " + (nodeMap.containsValue(node2) ? "true" : "false"));

    nodeMap.put(key, node2);
    System.out.println("added node2 to hash map");
    System.out.println("hash map size: " + nodeMap.size());
    System.out.println("hash map entry set size: " + nodeMap.entrySet().size());
    System.out.println("hash map contains node1? " + (nodeMap.containsValue(node1) ? "true" : "false"));
    System.out.println("hash map contains node2? " + (nodeMap.containsValue(node2) ? "true" : "false"));
}

protected class Node {

    private String data;

    private Integer count;

    public Node(String data, Integer count) {
        this.data = data;
        this.count = count;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((data == null) ? 0 : data.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node other = (Node) obj;
        if (data == null) {
            if (other.data != null)
                return false;
        }
        else
            if (!data.equals(other.data))
                return false;
        return true;
    }


    public String getData() {
        return data;
    }


    public void setData(String data) {
        this.data = data;
    }


    public Integer getCount() {
        return count;
    }


    public void setCount(Integer count) {
        this.count = count;
    }

}

}

Это выводит: 

node1 hash: 95356390
node2 hash: 95356391
node1 hash == node2 hash? false
node1.equals(node2)? false
added node1 to hash map
hash map size: 1
hash map entry set size: 1
hash map contains node1? true
hash map contains node2? false
added node2 to hash map
hash map size: 1
hash map entry set size: 1
hash map contains node1? false
hash map contains node2? true

Ответы [ 4 ]

3 голосов
/ 10 августа 2011

Ключи в хэш-карте хешируются, а не значения.В вашем случае вы звоните put(key, node), а ключ постоянен, поэтому второй put переопределит первый.Если бы ключ был узлом, то у вас было бы две записи.

2 голосов
/ 10 августа 2011

Вы должны смотреть на ключ, а не на значение.

1 голос
/ 10 августа 2011

Если вы прочитаете javadoc для HashMap , вы заметите, что метод put() определяется следующим образом:

put (ключ объекта, значение объекта)

Связывает указанное значение с указанным ключом на этой карте.

При двойном вызове put() с одним и тем же ключом оно переопределяет исходное значение, связанное с этим ключом.

Кроме того, в таблице используется хеш ключа , а не значение, для поиска правильного сегмента.

Кроме того, ваше понимание классаэто правильно.

Однако я не верю, что вы можете просматривать коллизии из общедоступного API, поскольку это, скорее всего, рассматривается в классе.

0 голосов
/ 10 августа 2011

Вот обновленный код, который использует HashMap . Я также изменил метод equals (), чтобы включить поле count, но исключил его из метода hashCode (). Это успешно создает столкновение, и если вы посмотрите на HashMap с помощью отладчика, вы увидите список, который он строит в корзине, в которой произошло столкновение: 

public class HashMapTest {

public static void main(String[] args) {
    HashMapTest test = new HashMapTest();
    test.execute();
}

public void execute() {
    HashMap<Node, Node> nodeMap = new HashMap<Node, Node>();
    Node node1 = new Node("data1", 1);
    Node node2 = new Node("data2", 2);
    Node node3 = new Node("data1", 2);
    Node node4 = new Node("data1", 1);

    System.out.println("node1 hash: " + node1.hashCode());
    System.out.println("node2 hash: " + node2.hashCode());
    System.out.println("node3 hash: " + node3.hashCode());
    System.out.println("node1 hash == node2 hash? " + (node1.hashCode() == node2.hashCode() ? "true" : "false"));
    System.out.println("node2 hash == node3 hash? " + (node2.hashCode() == node3.hashCode() ? "true" : "false"));
    System.out.println("node1 hash == node3 hash? " + (node1.hashCode() == node3.hashCode() ? "true" : "false"));
    System.out.println("node1.equals(node2)? " + (node1.equals(node2) ? "true" : "false"));
    System.out.println("node2.equals(node3)? " + (node2.equals(node3) ? "true" : "false"));
    System.out.println("node1.equals(node3)? " + (node1.equals(node3) ? "true" : "false"));
    System.out.println("");

    nodeMap.put(node1, node1);
    System.out.println("added node1 to hash map");
    System.out.println("hash map size: " + nodeMap.size());
    System.out.println("hash map entry set size: " + nodeMap.entrySet().size());
    System.out.println("hash map contains node1? " + (nodeMap.containsValue(node1) ? "true" : "false"));
    System.out.println("hash map contains node2? " + (nodeMap.containsValue(node2) ? "true" : "false"));
    System.out.println("hash map contains node3? " + (nodeMap.containsValue(node3) ? "true" : "false"));
    System.out.println("node1's count from map: " + nodeMap.get(node1).getCount());
    System.out.println("");

    nodeMap.put(node2, node2);
    System.out.println("added node2 to hash map");
    System.out.println("hash map size: " + nodeMap.size());
    System.out.println("hash map entry set size: " + nodeMap.entrySet().size());
    System.out.println("hash map contains node1? " + (nodeMap.containsValue(node1) ? "true" : "false"));
    System.out.println("hash map contains node2? " + (nodeMap.containsValue(node2) ? "true" : "false"));
    System.out.println("hash map contains node3? " + (nodeMap.containsValue(node3) ? "true" : "false"));
    System.out.println("node1's count from map: " + nodeMap.get(node1).getCount());
    System.out.println("");

    // note that if node4 is used then it replaces the value that stored node1
    nodeMap.put(node3, node3);
    System.out.println("added node3 to hash map");
    System.out.println("hash map size: " + nodeMap.size());
    System.out.println("hash map entry set size: " + nodeMap.entrySet().size());
    System.out.println("hash map contains node1? " + (nodeMap.containsValue(node1) ? "true" : "false"));
    System.out.println("hash map contains node2? " + (nodeMap.containsValue(node2) ? "true" : "false"));
    System.out.println("hash map contains node3? " + (nodeMap.containsValue(node3) ? "true" : "false"));
    System.out.println("node1's count from map: " + nodeMap.get(node1).getCount());
}

protected class Node {

    private String data;

    private Integer count;

    public Node(String data, Integer count) {
        this.data = data;
        this.count = count;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + getOuterType().hashCode();
        result = prime * result + ((data == null) ? 0 : data.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node other = (Node) obj;
        if (!getOuterType().equals(other.getOuterType()))
            return false;
        if (count == null) {
            if (other.count != null)
                return false;
        }
        else
            if (!count.equals(other.count))
                return false;
        if (data == null) {
            if (other.data != null)
                return false;
        }
        else
            if (!data.equals(other.data))
                return false;
        return true;
    }


    public String getData() {
        return data;
    }


    public void setData(String data) {
        this.data = data;
    }


    public Integer getCount() {
        return count;
    }


    public void setCount(Integer count) {
        this.count = count;
    }

    private HashMapTest getOuterType() {
        return HashMapTest.this;
    }

}

}

Это выводит: 

node1 hash: 1077170390
node2 hash: 1077170391
node3 hash: 1077170390
node1 hash == node2 hash? false
node2 hash == node3 hash? false
node1 hash == node3 hash? true
node1.equals(node2)? false
node2.equals(node3)? false
node1.equals(node3)? false

added node1 to hash map
hash map size: 1
hash map entry set size: 1
hash map contains node1? true
hash map contains node2? false
hash map contains node3? false
node1's count from map: 1

added node2 to hash map
hash map size: 2
hash map entry set size: 2
hash map contains node1? true
hash map contains node2? true
hash map contains node3? false
node1's count from map: 1

added node3 to hash map
hash map size: 3
hash map entry set size: 3
hash map contains node1? true
hash map contains node2? true
hash map contains node3? true
node1's count from map: 1
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Похожие темы

...