19

在过去的一个小时里，我已经阅读了很多帖子，但是对于在 Hashmap 中使用不可变对象作为键的概念，我仍然不是很清楚。我有一个哈希图，其键为字符串。哈希图中的值是 MyStore，其中 MyStore 表示有关我拥有的商店的信息。字符串代表地址。在我的代码中，我的逻辑是，我首先在映射中查找该键，如果存在 - > 获取它的值，如果它不存在则将其放入 hashmap 中。我的经理刚刚告诉我关键是将来会改变，那就是我的商店地址将来会改变。他说在那种情况下，我首先检查密钥是否存在的逻辑将不起作用。我不明白他在这里的意思。我想非常清楚地理解以下几点-

  1. hashmap 的可变键和不可变键之间的区别。
  2. 如果您使用可以更改的不可变密钥会发生什么？- 我知道这没有意义，但我想清楚地了解我的经理在这里所说的内容。
  3. 如果将字符串用作哈希映射中的键缓存它们的哈希码，一些帖子会谈论字符串 - 这是什么意思？
  4. 如果假设我在实现 hashcode 和 equals 的 hashmap 中使用可变对象作为键，那么它会起作用吗？我假设它会因为如果密钥发生变化，contains 方法将查看密钥是否存在。如果它不存在，它将放置条目，以便您将来获取它。

如果之前已经讨论过，我并不是要创建重复的帖子。如果我错过了阅读可以回答我所有问题的帖子，请指出我。如果没有，请用外行的方式解释我的上述问题，以便将来对其他读者有用:)。随意编辑我的帖子的主题，所以将来如果有人有类似的问题，他们会直接登陆这里:)

4

5 回答 5

29

第一：HashMap 是如何工作的？

基本上它有一个数组，当你在地图中放置一个键值对时，它存储在数组中的一个位置。数组中的位置是根据hashCode()传递给散列方法的键的结果来选择的。这是为什么？好吧，如果您请求某个键的值，则可以简单地重新计算查找该键的数组中的索引及其关联值，以再次查找该数组中的索引。（需要更多逻辑来处理映射到同一索引的键，但我只是想让您了解基本机制）然后equals()用于验证计算索引处的键是否确实是请求的键。

  1. 从这里应该更清楚为什么不可变键比可变键更好。不可变的键将始终保持相同的hashCode()值，并且散列函数将再次找到正确的存储桶（= hashMap 数组中的索引）。

    这并不意味着可变键不能工作。如果键上的突变不会影响哈希码，或者只要使用了 hashMap，键就不会发生突变，则可变键将起作用。

  2. 不可变密钥如何更改？好吧，键本身可能无法改变，但是键值映射可以改变业务逻辑。如果您创建地图，使用地址作为键，您依赖于商店地址不会更改的事实。如果商店的地址发生变化，您将无法在使用其新地址作为键的地图中找到它。你的经理有一个有效的观点。

  3. 在 Map 中找到键的速度很大程度上取决于计算 hashCode 的速度。对于字符串，此计算循环遍历字符串中的所有字符。如果您使用长字符串作为键并且拥有大量 Map 访问权限，这可能会导致性能瓶颈。因此，Java 的 String 实现会缓存哈希值，因此只会计算一次。但是，如果您String再次使用相同的实例，您只会避免计算哈希码（新实例将没有缓存值）。您可以intern()使用您使用的密钥，但只有在可以证明确实存在性能瓶颈时才考虑这一点，因为String实习确实有其自身的开销。

  4. 如 1 中所述：如果可变键的哈希码不受突变影响，则它们可以工作。例如，使用 Customer 作为键，其中hashCode()仅基于客户的姓名，然后一个只不允许更改名称但允许更改其他值的 Customer 实现是一个可靠的键。

于 2013-08-03T06:58:47.640 回答
2

  1. 如果您修改用作键的可变对象，则可能会出现问题。即使键在那里也map.containsKey(modifiedKey)可能返回，您必须遍历键才能找到它。false所以尽量使用 immutable 或者当它是 key 时不要修改 mutable。

  2. 不可变对象永远不会改变。有些方法看起来像是在更改对象，但实际上是创建了一个新副本。例子：

    字符串 a = "A";

    字符串 b = a.substring(0); // 子字符串创建了一个“A”的副本，其中 a 根本没有被修改。

    a = a + b; // a+b 创建一个新的字符串“AA”，不修改之前的字符串。

  3. 这可能有助于缓存-hashes-in-java-collections这也很好，为什么-are-immutable-objects-in-hashmaps-so-effective

  4. String 已经实现了equalsand hashcode，除非您绝对确定需要它，否则无需发明另一个类来代替它。

    如第 1 点所述，您可以这样做，但您必须小心，不要修改您的可变对象。不过，这不是一个很好的做法。

于 2013-08-03T06:25:17.117 回答
1

  1. 不可变的键不能改变。因此，在插入时计算的哈希码不会改变。因此，当您尝试从地图中获取元素时，要获取的对象的哈希码是根据已知的哈希码计算的。如果您的密钥是从外部更改的（它是可变的），新密钥的哈希码将与您插入的不同。

  2. 让我们看一个例子。对于（2和4）

    public class RandomPair {
    int p;
    int q;

    public RandomPair(int p, int q) {
        this.p = p;
        this.q = q;
    }
    @Override
    public int hashCode() {
        return 31 * p + q;
    }

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

        RandomPair other = (RandomPair) obj;
        if (p != other.p)
            return false;
        if (q != other.q)
            return false;
        return true;
    }

    public static void main(String[] args) {
        RandomPair pair = new RandomPair(10, 10);
        Map<RandomPair, Integer> map = new HashMap<RandomPair, Integer>();

        map.put(pair, 1);
        System.out.println(map.get(pair)); //returns 1

        //someone somewhere just changed the value of pair
        pair.p = 20;
        //the object was the same, someone somewhere just changed value of pair and now you can't 
        //find it in the map
        System.out.println(map.get(pair));

        //had you made p and q final, this sort of modification wouldn't be possible
       //Strings are immutable and thus prevent this modification
    }
}

  3. 由于字符串是不可变的，因此计算后的哈希码值可以再次重复使用。哈希码是惰性计算的。即在第一次调用 hashcode 时，hashcode 的值被缓存。

于 2013-08-03T06:48:36.820 回答
0

一般来说，hashmap 中的键应该是不可变的。

看到这个

注意：如果将可变对象用作映射键，则必须非常小心。如果对象的值以影响等于比较的方式更改，而对象是映射中的键，则不指定映射的行为。

您的密钥的哈希在插入期间计算一次，哈希映射存储它，一旦您的密钥被修改，它就不会自动更新。这就是为什么假设密钥是不可变的。

您的选择是： 1. 不要使用可变对象作为键。尝试找到另一个键，或使用以前的键对象的不可变部分 2. 不要在可变对象用作键时更改它们

于 2013-08-03T06:25:02.957 回答
0

  1. 可变键或对象意味着您可以修改对象[通过修改我的意思是您可以更改对象表示的值]。HashMap如果用 equals 和 hashcode 编写的逻辑使用这些可修改的值，这将影响其存储。

  2. 理想情况下，不变性意味着对象一旦初始化就不能再更改。但是，如果我们具体谈谈HashMap在 equals 和 hashcode 方法中使用的所有变量，如果它们可以修改，那么该对象不应该用作键，否则它可以用作键[但仍然不推荐]。

  3. 它不仅仅是 about String，任何 about 都会缓存其哈希码。几乎所有对象都会一次又一次地生成哈希码[我说几乎在某些情况下它可以改变是有原因的]。Hashcode 缓存在 Object 标头中。

  4. 如果您想使用可变对象作为键，那么您应该选择IdentityHashMap. 只需阅读它们，它们在这种情况下会很有用。

于 2013-08-03T07:04:09.983 回答