4

我正在使用 a HashMap，但我无法直接回答该get()方法在发生碰撞时的工作原理。

假设n > 1对象被放置在同一个key中。它们是否存储在LinkedList? 它们是否被覆盖，以便仅放置在该键中的最后一个对象不再存在？他们是否使用其他碰撞方法？

如果它们被放置在 a 中LinkedList，有没有办法检索整个列表？如果没有，是否有其他内置的Java地图我可以在其中执行此操作？

就我的目的而言，单独的链接将是理想的，就好像存在冲突一样，我需要能够查看列表并获取有关其中所有对象的信息。在Java中执行此操作的最佳方法是什么？

感谢你的帮助！

4

5 回答 5

8

Hashmap.put()的文档清楚地指出，“将指定的值与此映射中的指定键相关联。如果映射先前包含键的映射，则替换旧值”

如果您想要一个与键关联的对象列表，则将列表存储为值。

请注意，“冲突”通常是指 HashMap 的内部工作，其中两个键具有相同的哈希值，而不是对两个不同的值使用相同的键。

于 2012-10-18T01:43:20.597 回答
7

它们是否被覆盖，以便仅放置在该键中的最后一个对象不再存在？

是的，假设您使用同一个键放置多个值（根据Object.equals，而不是Object.hashCode。）这是在Map.putjavadoc中指定的：

如果映射先前包含键的映射，则旧值将替换为指定值。

如果你想将一个键映射到多个值，你可能最好使用像 Guava's 这样的东西ListMultimap，ArrayListMultimap具体来说，它将键映射到值列表。（披露：我为 Guava 做出了贡献。）如果你不能容忍第三方库，那么你真的必须有一个Map<Key, List<Value>>，尽管这可能会有点笨拙。

于 2012-10-18T01:43:23.580 回答
3

假设 n > 1 个对象被放置在同一个键中。它们是否存储在链表中？它们是否被覆盖，以便仅放置在该键中的最后一个对象不再存在？他们是否使用其他碰撞方法？

同一键可能有单个实例，因此最后一个会覆盖前一个

Map<String, Integer> map = new HashMap<String, Integer>();
map.put("a", 1);
map.put("a", 2);// it overrides 1 and puts 2 there

链接来自不同键的相同哈希值

看

于 2012-10-18T01:43:08.997 回答
0

引用：“假设 n > 1 个对象被放置在同一个键中。它们是否存储在链表中？它们是否被覆盖，以便仅放置在该键中的最后一个对象不再存在？它们是否使用其他碰撞方法？

是的，如果 hashmap 在此键下包含某些内容，它将覆盖它。

您可以实现自己的类来处理这个或更简单的使用 HashMap> 在其中 K 是您的 Key Object 而 V 是对象值。请记住，当您执行 map.get(K) 时，最后一个解决方案将检索一个列表或您选择的实现（即：ArrayList），因此该实现的所有方法都可供您使用，并且可能满足您的要求。例如，如果您使用 Arraylist，您有大小、trimToSize、removeRange 等。

于 2012-10-18T02:02:14.667 回答
-1

java中散列的冲突解决不是基于链接。据我了解，JDK 使用双散列，这是开放寻址的最佳方式之一。所以没有列表将与哈希槽相关联。

您可以将哈希函数解析为相同键的对象放入列表中，并且可以在表/映射中更新此列表。

package hashing;

import java.util.HashMap;
import java.util.Map;

public class MainAnimal {

    /**
     * @param args
     */
    public static void main(String[] args) {

        Animal a1 = new Animal(1);
        Animal a2 = new Animal(2);

        Map<Animal, String> animalsMap = new HashMap<Animal, String>();

        animalsMap.put(a1,"1");
        animalsMap.put(a2,"2");

        System.out.println(animalsMap.get(a1));

        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("a", 1);
        map.put("a", 2);// it overrides 1 and puts 2 there

        System.out.println(map.get("a"));       

    }

}


class Animal {

    private int index = 0;

    Animal(int index){
        this.index = index;
    }

    public boolean equals(Object obj){
        if(obj instanceof Animal) {
            Animal animal = (Animal) obj;
            if(animal.getIndex()==this.getIndex())
                return true;
            else
                return false;
        }
        return false;
    }

    public int hashCode() {
        return 0;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }


}

在上面的代码中，我展示了两个不同的东西。

案例 1 - 两个不同的实例解析为相同的 hashkey 案例 2 - 两个相同的实例充当两个不同条目的键。

动物实例 a1 和 a2 解析为相同的键。但它们不会被覆盖。散列机制通过散列槽进行探测，并将条目放置在不同的槽中。

对于第二种情况，键解析为相同的哈希键，并且 equals 方法也满足。因此发生了覆盖。

现在，如果在动物类中我以这种方式覆盖 equals 方法 -

    public boolean equals(Object obj){
//      if(obj instanceof Animal) {
//          Animal animal = (Animal) obj;
//          if(animal.getIndex()==this.getIndex())
//              return true;
//          else
//              return false;
//      }
//      return false;
        return true;
    }

覆盖发生。行为就像使用相同的实例。由于 a1 和 a2 在同一个桶中，并且 equals 也返回 true。

于 2012-10-18T02:05:29.783 回答