可变hashmap键是危险的做法吗?

pu82cl6c  于 2021-06-29  发布在  Java
关注(0)|答案(8)|浏览(446)

使用可变对象作为hashmap键是一种不好的做法吗?当您尝试使用修改到足以更改其哈希代码的键从哈希Map中检索值时,会发生什么情况?
例如,给定

class Key
{
    int a; //mutable field
    int b; //mutable field

    public int hashcode()
        return foo(a, b);
    // setters setA and setB omitted for brevity
}

带代码

HashMap<Key, Value> map = new HashMap<Key, Value>();

Key key1 = new Key(0, 0);
map.put(key1, value1); // value1 is an instance of Value

key1.setA(5);
key1.setB(10);

如果我们现在打电话怎么办 map.get(key1) ? 这是安全的还是可取的?还是行为依赖于语言?

j13ufse2

j13ufse21#

正如其他人所解释的,这是危险的。
避免这种情况的一种方法是让const字段显式地给出可变对象中的散列(这样您就可以根据它们的“标识”而不是“状态”散列)。您甚至可以或多或少随机初始化该散列字段。
另一个窍门是使用地址。 (intptr_t) reinterpret_cast<void*>(this) 作为散列的基础。
在所有情况下,都必须放弃对对象不断变化的状态进行哈希处理。

yrdbyhpb

yrdbyhpb2#

许多备受尊敬的开发人员(如brian goetz和josh bloch)都注意到:
如果一个对象的hashcode()值可以根据其状态进行更改,那么在将这些对象用作基于哈希的集合中的键时,我们必须小心,以确保在将它们用作哈希键时不允许它们的状态更改。所有基于散列的集合都假定对象的散列值在用作集合中的键时不会更改。如果一个键的散列码在集合中发生变化,可能会产生一些不可预测和令人困惑的后果。这在实践中通常不是问题-在hashmap中使用列表之类的可变对象作为键不是常见的实践。

ac1kyiln

ac1kyiln3#

根据您对行为的期望,可变键可能会出现两个截然不同的问题。
第一个问题:(可能是最微不足道的——但它给了我一些我没有想到的问题!)
您正试图通过更新和修改同一个键对象将键值对放置到Map中。你可以这样做 Map<Integer, String> 简单地说:

int key = 0;
loop {
    map.put(key++, newString);
}

我在重复使用“对象” key 创建Map。这在java中工作得很好,因为每个新值 key 将自动装箱到新的整数对象。如果我创建了自己的(可变的)整数对象,那就行不通了:

MyInteger {
   int value;

   plusOne(){
      value++;
   }
}

然后尝试了同样的方法:

MyInteger key = new MyInteger(0);
loop{
   map.put(key.plusOne(), newString)
}

我的期望是,例如,我绘制Map 0 -> "a" 以及 1 -> "b" . 在第一个例子中,如果我改变 int key = 0 ,Map会(正确地)给我 "a" . 为了简单起见,我们假设 MyInteger 总是一样的 hashCode() (如果您能够设法为对象的所有可能状态创建唯一的hashcode值,这将不是问题,您应该获得奖励)。在这种情况下,我打电话给 0 -> "a" ,所以现在Map上有我的 key 并将其Map到 "a" ,然后修改 key = 1 试着把 1 -> "b" . 我们有麻烦了!这个 hashCode() 是相同的,hashmap中唯一的键是my MyInteger key 刚刚修改为等于的对象 1 ,因此它将覆盖该键的值,因此现在 0 -> "a" 以及 1 -> "b" ,我有 1 -> "b" 只是!更糟的是,如果我改回 key = 0 ,hashcode指向 1 -> "b" ,但由于hashmap的唯一键是my key对象,因此它满足等式检查并返回 "b" ,不是 "a" 一如预期。
如果你像我一样,成为这类问题的牺牲品,诊断起来就非常困难。为什么?因为如果你有一个像样的 hashCode() 函数,它将生成(大部分)唯一的值。在构造Map时,散列值将在很大程度上解决不等式问题,但是如果有足够的值,最终会在散列值上发生冲突,然后会得到意外的、基本上无法解释的结果。其结果是,它适用于较小的运行,但在较大的运行中失败。
建议:
要查找此类问题,请修改 hashCode() 方法,即使是微不足道的(即。 = 0 --显然,在执行此操作时,请记住,对于两个相等的对象,哈希值应该相同),并查看是否得到相同的结果——因为应该这样做,如果不这样做,则使用哈希表的实现可能会出现语义错误。
第二个问题:
这是一个大多数人似乎都在关注的问题,所以我将尽量简短。在这个用例中,我尝试Map一个键-值对,然后我对键做一些工作,然后想回来获取我的值。
期望值: key -> value Map,然后修改 key 试着 get(key) . 我想这会给我 value .
这对我来说似乎是很明显的,这是行不通的,但我以前也曾尝试过使用集合之类的东西作为键(而且很快就意识到它行不通)。它不起作用,因为 key 已经变了,所以你连正确的桶都找不到。
这就是为什么使用集合作为键是非常不可取的。我想,如果你这么做,你是想建立一种多对一的关系。所以我有一个班(在教学中),我想两个小组做两个不同的项目。我想要的是,给定一个团队,他们的项目是什么?很简单,我把班级一分为二 group1 -> project1 以及 group2 -> project2 . 但是等等!一个新来的学生来了,所以我把他们安置在家里 group1 . 问题是 group1 现在已被修改,可能其哈希值已更改,因此尝试执行以下操作 get(group1) 很可能会失败,因为它将在hashmap的错误或不存在的bucket中查找。
显然,解决上述问题的方法是将事物链接起来,而不是将组用作键,而是为它们提供指向组和项目的标签(不会更改): g1 -> group1 以及 g1 -> project1 等等。
附笔
请确保定义 hashCode() 以及 equals(...) 方法(eclipse,我假设大多数ide都可以为您这样做)。
代码示例:
下面是一个展示两种不同“问题”行为的类。在这种情况下,我尝试Map 0 -> "a" , 1 -> "b" ,和 2 -> "c" (每种情况下)。在第一个问题中,我通过修改同一个对象来实现,在第二个问题中,我使用唯一的对象,在第二个问题“修复”中,我克隆那些唯一的对象。之后我拿了一把“独一无二”的钥匙( k0 )并修改它以尝试访问Map。我想这会给我 a, b, c 以及 null 当钥匙是 3 .
但是,会发生以下情况:

map.get(0) map1: 0 -> null, map2: 0 -> a, map3: 0 -> a
map.get(1) map1: 1 -> null, map2: 1 -> b, map3: 1 -> b
map.get(2) map1: 2 -> c, map2: 2 -> a, map3: 2 -> c
map.get(3) map1: 3 -> null, map2: 3 -> null, map3: 3 -> null

第一个Map(“第一个问题”)失败,因为它只保存一个键,该键最后更新并放置为相等 2 ,因此它可以正确返回 "c" 什么时候 k0 = 2 但是回来了 null 对于其他两个(单个键不等于0或1)。第二个Map失败了两次:最明显的是它返回了 "b" 当我要求 k0 (因为它被修改了——这是“第二个问题”,当你做这样的事情时,它看起来很明显)。当它返回时会再次失败 "a" 修改后 k0 = 2 (我希望是 "c" ). 这更多的是由于“第一个问题”:有一个哈希代码冲突,而tiebreaker是一个相等检查——但Map保持不变 k0 ,它(显然对我来说——理论上对其他人来说可能不同)首先检查,然后返回第一个值, "a" 即使它一直在检查, "c" 也会是一场比赛。最后,第三个Map工作得很好,因为无论我做什么(通过在插入过程中克隆对象),我都强制Map保持唯一的键。
我想说清楚,我同意,克隆不是解决办法!我只是简单地添加了一个例子,说明了为什么Map需要唯一键,以及强制唯一键如何“修复”这个问题。

public class HashMapProblems {

   private int value = 0;

   public HashMapProblems() {
       this(0);
   }

   public HashMapProblems(final int value) {
       super();
       this.value = value;
   }

   public void setValue(final int i) {
       this.value = i;
   }

   @Override
   public int hashCode() {
       return value % 2;
   }

   @Override
   public boolean equals(final Object o) {
       return o instanceof HashMapProblems
            && value == ((HashMapProblems) o).value;
   }

   @Override
   public Object clone() {
       return new HashMapProblems(value);
   }

   public void reset() {
       this.value = 0;
   }

   public static void main(String[] args) {
       final HashMapProblems k0 = new HashMapProblems(0);
       final HashMapProblems k1 = new HashMapProblems(1);
       final HashMapProblems k2 = new HashMapProblems(2);
       final HashMapProblems k = new HashMapProblems();
       final HashMap<HashMapProblems, String> map1 = firstProblem(k);
       final HashMap<HashMapProblems, String> map2 = secondProblem(k0, k1, k2);
       final HashMap<HashMapProblems, String> map3 = secondProblemFixed(k0, k1, k2);

       for (int i = 0; i < 4; ++i) {
           k0.setValue(i);
           System.out.printf(
                "map.get(%d) map1: %d -> %s, map2: %d -> %s, map3: %d -> %s",
                i, i, map1.get(k0), i, map2.get(k0), i, map3.get(k0));
           System.out.println();
       }
   }

   private static HashMap<HashMapProblems, String> firstProblem(
        final HashMapProblems start) {
       start.reset();
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       map.put(start, "a");
       start.setValue(1);
       map.put(start, "b");
       start.setValue(2);
       map.put(start, "c");
       return map;
   }

   private static HashMap<HashMapProblems, String> secondProblem(
        final HashMapProblems... keys) {
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       IntStream.range(0, keys.length).forEach(
            index -> map.put(keys[index], "" + (char) ('a' + index)));
       return map;
   }

   private static HashMap<HashMapProblems, String> secondProblemFixed(
        final HashMapProblems... keys) {
       final HashMap<HashMapProblems, String> map = new HashMap<>();

       IntStream.range(0, keys.length)
            .forEach(index -> map.put((HashMapProblems) keys[index].clone(),
                    "" + (char) ('a' + index)));
       return map;
   }
}

注意事项:
在上述情况下,应注意 map1 因为我设置 hashCode() 功能是平分胜负。 k = 0 以及 k = 2 因此有相同的 hashCode0 .

bbuxkriu

bbuxkriu4#

如果在hashmap中存储了键值对(条目)之后,键的哈希代码发生了变化,则该Map将无法检索条目。
如果key对象是可变的,key的hashcode可以更改。hahsmap中的可变键可能导致数据丢失。

hc8w905p

hc8w905p5#

这既不安全也不可取。无法检索由键1Map到的值。在执行检索时,大多数哈希Map都会执行以下操作

Object get(Object key) {
    int hash = key.hashCode();
    //simplified, ignores hash collisions,
    Entry entry = getEntry(hash);
    if(entry != null && entry.getKey().equals(key)) {
        return entry.getValue();
    }
    return null;
}

在本例中,key1.hashcode()现在指向哈希表的错误bucket,您将无法使用key1检索value1。
如果你做过这样的事,

Key key1 = new Key(0, 0);
map.put(key1, value1);
key1.setA(5);
Key key2 = new Key(0, 0);
map.get(key2);

这也不会检索value1,因为key1和key2不再相等,所以此检查

if(entry != null && entry.getKey().equals(key))

会失败的。

aor9mmx1

aor9mmx16#

我不会重复别人说的话。是的,这是不可取的。但在我看来,文件中的表述并不明显。
您可以在Map界面的javadoc上找到它:
注意:如果使用可变对象作为Map键,则必须非常小心。当对象是Map中的键时,如果对象的值以影响equals比较的方式更改,则不指定Map的行为

bttbmeg0

bttbmeg07#

这行不通。您正在更改键值,因此基本上是将其丢弃。这就像创造一个现实生活中的钥匙和锁,然后改变钥匙,并试图把它放回锁。

u59ebvdq

u59ebvdq8#

哈希Map使用哈希代码和相等比较来标识具有给定密钥的某个键值对。如果hasMap保留键作为对可变对象的引用,那么它将在使用同一示例检索值的情况下工作。但是,请考虑以下情况:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances and 
// keyOne.equals(keyTwo) is true.

HashMap myMap = new HashMap();

myMap.push(keyOne, "Hello");

String s1 = (String) myMap.get(keyOne); // s1 is "Hello"
String s2 = (String) myMap.get(keyTwo); // s2 is "Hello" 
                                        // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap.get(keyOne); // returns "Hello"
s2 = myMap.get(keyTwo); // not found

如果密钥存储为引用,则上述情况成立。在java中通常是这样。例如,在.net中,如果键是值类型(总是按值传递),则结果将不同:

T keyOne = ...;
T keyTwo = ...;

// At this point keyOne and keyTwo are different instances 
// and keyOne.equals(keyTwo) is true.

Dictionary myMap = new Dictionary();

myMap.Add(keyOne, "Hello");

String s1 = (String) myMap[keyOne]; // s1 is "Hello"
String s2 = (String) myMap[keyTwo]; // s2 is "Hello"
                                    // because keyOne equals keyTwo

mutate(keyOne);

s1 = myMap[keyOne]; // not found
s2 = myMap[keyTwo]; // returns "Hello"

其他技术可能有其他不同的行为。然而,几乎所有的应用程序都会遇到这样的情况:使用可变键的结果是不确定的,这在应用程序中是非常糟糕的情况——很难调试,甚至更难理解。

相关问题