哈希表中字符串作为键

Question

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

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

如果此问题之前已经讨论过，我并不打算创建重复的帖子。如果我错过了包含所有答案的帖子，请指向它。如果没有，请用通俗易懂的语言解释上述问题，以便将来其他读者受益。请随意编辑我的帖子主题，以便将来任何人有类似的问题，都可以直接到达此处 :)

- rickygrimes

---

这应该可以回答你的问题 https://dev59.com/R3VC5IYBdhLWcg3wrDRd - Spencer

哈希码的不断变化破坏了HashMap的契约。在这种情况下，您可能想要按对象引用进行映射，或将地图转换为对象属性关系。 - S.D.

Answer 1

首先，HashMap是如何工作的？

基本上它有一个数组，当你将一个键值对放入map中时，它会存储在数组中的其中一个位置。数组中的位置是根据键的 hashCode() 传递给哈希方法后的结果来选择的。为什么是这样呢？因为如果你请求某个键的值，只需要重新计算出该键和其关联值的索引位置即可在数组中找到。 （需要一些更多的逻辑来处理映射到相同索引的键，但我只是试图让您了解基本机制）然后使用equals() 来验证计算出的索引位置上的键是否确实是所请求的键。

1. 从这里可以更清楚地看出为什么不可变键比可变键好。不可变键始终保持相同的hashCode() 值，哈希函数将再次找到正确的桶（= hashMap数组中的索引）。

   这并不意味着可变键无法工作。如果对键的修改不影响其哈希码，或者在使用hashMap时键根本没有被修改，那么可变键也是可以使用的。

2. 不可变键怎么会改变呢？嗯，键本身可能无法更改，但在业务逻辑中键值映射可能会发生变化。如果你创建一个map，使用地址作为键，那么你就依赖于商店地址不会更改的事实。如果商店地址发生变化，你将无法使用其新地址作为键在Map中找到它。你的经理说得有道理。

在Map中查找一个键的速度高度依赖于hashCode方法的执行速度。对于字符串类型的键，这个计算过程会遍历整个字符串，如果你使用比较长的字符串作为键并且有大量的Map访问，这可能会导致性能瓶颈。因此Java的字符串实现会缓存hashCode值，所以它只需要被计算一次。然而，你只能避免重新计算hashCode方法的结果如果你再次使用同一个String实例（新的实例将不会有缓存的值）。你可以通过调用intern()方法来使键变成可缓存的，但是只有当真正存在性能瓶颈时才应该这样做，因为使用String.intern()方法也有自己的开销。

如1所述：如果可变键的hashCode方法不受变化的影响，那么它们也可以正常工作。例如，使用一个Customer对象作为键，其中hashCode()方法仅基于顾客的姓名计算，在这种情况下，一个只允许姓名发生更改但允许其他值发生更改的Customer实现将是一个可靠的键。

- bowmore

---

非常好。谢谢Bowmore。 - rickygrimes

字符串的哈希码已经被缓存了... - assylias

我想象一下，如果您更改了可变键，则HashMap应该计算其新的hashCode()并重新定位它。我不知道Java中HashMap的实现方式，但我认为检查键是否已更改是合理的，如果是->计算新的hashCode()->重新定位元素并释放先前的位置。 - Anton Belev

一个 Map 实现（特别是一个通用的实现）如何知道键的哈希码已经改变？一个 Map 可以在每次 get 操作之前检查所有包含的键，但这显然违背了 Map 的目的：快速获取与一个键相关联的值。 - bowmore

Answer 2

1. 如果修改作为键使用的可变对象，可能会出现问题。即使该键存在，map.containsKey(modifiedKey)也可能返回false，您必须遍历键来查找它。因此，请尽量使用不可变对象或在其作为键时不要修改可变对象。

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

   String a = "A";

   String b = a.substring(0); // substring 会创建一个不改变a的"A"的副本。

   a = a + b; // a+b将创建一个新的字符串"AA"，而不会修改以前的字符串。

3. 这可能有帮助：caching-hashes-in-java-collections，同时这个很棒：why-are-immutable-objects-in-hashmaps-so-effective

4. String已经实现了equals和hashcode方法，除非您确信需要，否则无需发明另一个类来代替它。

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

- Tala

---

非常感谢您提供的链接 - https://dev59.com/A2kv5IYBdhLWcg3wzj41。它回答了我所有的问题。 - rickygrimes

当然可以。但是，我对第二点仍然不是很清楚。另外，请修改您对我的第四点的回答。我指的是不可变对象。 - rickygrimes

Answer 3

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)); //返回1
   
           //某个地方的某个人刚刚更改了pair的值
           pair.p = 20;
           //对象是相同的，某个地方的某个人刚刚更改了pair的值，现在您无法在map中找到它
           System.out.println(map.get(pair));
   
           //如果将p和q设置为final，则不可能进行此类修改。
          //字符串是不可变的，因此可以防止此类修改
       }
   }
   

3. 由于字符串是不可变的，因此一旦计算出哈希码值，就可以再次重用该值。哈希码是懒惰计算的。即在第一次调用哈希码时，哈希码的值被缓存。

- bsd

---

谢谢bsd。你能否再加上几行关于我经理所说的内容吗？我们从客户那里收到数据，格式为JSON字符串。因此他们肯定会更改地址。我想了解这如何影响我现有的逻辑？ - rickygrimes

不要将地址作为计算哈希码和相等性的一部分。常量字段可以是其唯一的10位身份证号码(可能是社会保险号)应该成为哈希码的一部分。名称可能会更改，地址也可能会更改。如果您可以找出Person对象中有什么变化，您可以从地图中删除该项，并重新插入具有新鲜值的项目。 - bsd

Answer 4

通常情况下，哈希映射中的键应该是不可变的。

请参见this

注意：如果使用可变对象作为映射键，则必须非常小心。如果在对象作为映射键时以影响等式比较的方式更改对象的值，则映射的行为未指定。

在插入期间计算您的键的哈希值一次，哈希映射存储它，并且一旦修改了您的键，它将不会自动更新。这就是为什么有一个假设键将是不可变的。

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

- Vadim

---

你能否回答我上面提出的每个问题吗？那真的会很有帮助。 - rickygrimes

Answer 5

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

2. 不可变性理想情况下意味着对象一旦初始化后就不能再更改。但是，如果我们具体讨论 HashMap，则所有用于 equals 和 hashcode 方法内部的变量，如果它们可以被修改，则不应将该对象用作键，否则可以将其用作键[但仍不建议]。

3. 这不仅仅涉及到 String，任何关于都会缓存其哈希码。几乎所有对象都会生成哈希码[我之所以说几乎是因为在某些情况下它可能会改变]。哈希码缓存在对象头中。

4. 如果要使用可变对象作为键，则应选择 IdentityHashMap。只需了解它们，它们在这种情况下可能很有用。

- Lokesh