2

背景资料:

在我的项目中,我将强化学习 (RL) 应用于 Mario 领域。对于我的状态表示,我选择使用带有自定义对象的哈希表作为键。我的自定义对象是不可变的,并且覆盖了 .equals() 和 .hashcode() (由 IntelliJ IDE 生成)。

这是生成的 .hashcode(),我在注释中添加了可能的值作为额外信息:

@Override
public int hashCode() {
    int result = (stuck ? 1 : 0);                // 2 possible values: 0, 1
    result = 31 * result + (facing ? 1 : 0);     // 2 possible values: 0, 1 
    result = 31 * result + marioMode;            // 3 possible values: 0, 1, 2
    result = 31 * result + (onGround ? 1 : 0);   // 2 possible values: 0, 1 
    result = 31 * result + (canJump ? 1 : 0);    // 2 possible values: 0, 1 
    result = 31 * result + (wallNear ? 1 : 0);   // 2 possible values: 0, 1 
    result = 31 * result + nearestEnemyX;        // 33 possible values: - 16 to 16
    result = 31 * result + nearestEnemyY;        // 33 possible values: - 16 to 16

    return result;
}

问题:

这里的问题是,上面代码中的结果可能会超过Integer.MAX_VALUE. 我在网上读过这不一定是问题,但在我的情况下是。这部分是由于使用的算法是 Q-Learning(一种 RL 方法)并且取决于存储在哈希表中的正确 Q 值。基本上我在检索值时不会有冲突。在运行我的实验时,我发现结果一点都不好,我 95% 确定问题在于从哈希表中检索 Q 值。(如果需要,我可以详细说明我为什么确定这一点,但这需要一些与问题无关的项目额外信息。)

问题:

有没有办法避免整数溢出,也许我在这里忽略了一些东西?或者是否有另一种方法(可能是另一种数据结构)来相当快地获得给定我的自定义键的值?

评论:

在阅读了一些评论后,我确实意识到我使用 HashTable 的选择可能不是最好的选择,因为我想要不会导致冲突的唯一键。如果我仍然想使用 HashTable,我可能需要正确的编码。

4

4 回答 4

8

您需要一个专用的 Key Field 来保证唯一性

.hashCode() 不是为您使用它的目的而设计的

.hashCode()旨在在分桶算法中提供良好的一般结果,可以容忍轻微的冲突。它并非旨在提供唯一的密钥。默认算法是时间和空间以及轻微冲突的权衡,它不应该保证唯一性。

完美哈希

您需要实现的是基于对象内容的完美哈希或其他一些唯一键。这在 an 的范围内是可能的,int但我不会.hashCode()用于这种表示。我会在对象上使用显式键字段。

唯一哈希

使用SHA1标准库中内置的散列的一种方法,对于小型数据集,这种方法的冲突几率极低。您发布的值不会出现巨大的组合爆炸,这SHA1将起作用。

您应该能够计算出一种方法来生成minimal perfect hash具有您在问题中显示的有限值的 a 。

最小完美散列函数是将 n 个键映射到 n 个连续整数的完美散列函数——通常是 [0..n−1] 或 [1..n]。一个更正式的表达方式是:让 j 和 k 是某个有限集 K 的元素。 F 是一个最小完美散列函数,当且仅当 F(j) =F(k) 意味着 j=k(内射性)并且存在一个整数a 使得 F 的范围是 a..a+|K|-1。已经证明,通用的最小完美散列方案至少需要 1.44 位/密钥。2目前最知名的最小完美散列方案使用大约 2.6 位/密钥。[3]

如果键以 a1, a2, ..., an 的顺序给出并且对于任何键 aj 和 ak, j,则最小完美散列函数 F 是保序的

一个最小完美散列函数 F 是单调的,如果它保持键的字典顺序。在这种情况下,函数值只是每个键在所有键的排序顺序中的位置。如果要散列的键本身存储在排序数组中,则可以将每个键的少量附加位存储在可用于快速计算散列值的数据结构中。 [6]

解决方案

请注意它在哪里谈论URL它可以是您从对象计算byte[]的任何表示。String

我通常会覆盖该toString()方法以使其生成独特的东西,然后将其提供给该UUID.nameUUIDFromBytes()方法。

Type 3 UUID 和 UUID.nameUUIDFromBytes() 一样有用

版本 3 UUID 使用通过 MD5 从 URL、完全限定域名、对象标识符、可分辨名称(轻量级目录访问协议中使用的 DN)或未指定名称空间中的名称派生 UUID 的方案。版本 3 UUID 的格式为 xxxxxxxx-xxxx-3xxx-yxxx-xxxxxxxxxxxx,其中 x 是任何十六进制数字,y 是 8、9、A 或 B 之一。

为了确定给定名称的版本 3 UUID,命名空间的 UUID(例如,域的 6ba7b810-9dad-11d1-80b4-00c04fd430c8)被转换为与其十六进制数字对应的字节串,并与输入名称连接, 用 MD5 散列产生 128 位。六位被固定值替换,其中四位表示版本,0011 表示版本 3。最后,固定哈希被转换回十六进制形式,连字符分隔其他 UUID 版本中相关的部分。

我首选的解决方案是 Type 5 UUID(Type 3 的 SHA 版本)

第 5 版 UUID 使用带有 SHA-1 散列的方案;否则,它与版本 3 中的想法相同。RFC 4122 指出版本 5 优于版本 3 基于名称的 UUID,因为 MD5 的安全性已受到损害。请注意,160 位 SHA-1 哈希被截断为 128 位以计算出长度。一个勘误表解决了 RFC 4122 附录 B 中的示例。

关键对象应该是不可变的

这样您就可以计算toString().hashCode()并在其中生成一个唯一的主键Constructor并设置它们一次,而不是一遍又一遍地计算它们。

这是一个惯用的不可变对象的稻草人示例,并根据对象的内容计算唯一键。

package com.stackoverflow;

import javax.annotation.Nonnull;
import java.util.Date;
import java.util.UUID;

public class Q23633894
{

    public static class Person
    {
        private final String firstName;
        private final String lastName;
        private final Date birthday;
        private final UUID key;
        private final String strRep;

        public Person(@Nonnull final String firstName, @Nonnull final String lastName, @Nonnull final Date birthday)
        {
            this.firstName = firstName;
            this.lastName = lastName;
            this.birthday = birthday;
            this.strRep = String.format("%s%s%d", firstName, lastName, birthday.getTime());
            this.key = UUID.nameUUIDFromBytes(this.strRep.getBytes());
        }

        @Nonnull
        public UUID getKey()
        {
            return this.key;
        }

        // Other getter/setters omitted for brevity

        @Override
        @Nonnull
        public String toString()
        {
            return this.strRep;
        }

        @Override
        public boolean equals(final Object o)
        {
            if (this == o) { return true; }
            if (o == null || getClass() != o.getClass()) { return false; }
            final Person person = (Person) o;
            return key.equals(person.key);
        }

        @Override
        public int hashCode()
        {
            return key.hashCode();
        }
    }
}
于 2014-05-13T14:26:19.350 回答
6

对于对象状态的唯一表示,总共需要 19 位。因此,可以用“完美哈希”整数值(最多 32 位)来表示它:

@Override
public int hashCode() {
    int result = (stuck ? 1 : 0); // needs 1 bit (2 possible values)
    result += (facing ? 1 : 0) << 1; // needs 1 bit (2 possible values)
    result += marioMode << 2; // needs 2 bits (3 possible values)
    result += (onGround ? 1 : 0) << 4; // needs 1 bit (2 possible values)
    result += (canJump ? 1 : 0) << 5; // needs 1 bit (2 possible values)
    result += (wallNear ? 1 : 0) << 6; // needs 1 bit (2 possible values)
    result += (nearestEnemyX + 16) << 7; // needs 6 bits (33 possible values)
    result += (nearestEnemyY + 16) << 13; // needs 6 bits (33 possible values)
}
于 2014-05-13T14:31:36.887 回答
2

而不是使用31你的幻数,你需要使用可能性的数量(归一化为 0)

@Override
public int hashCode() {
    int result = (stuck ? 1 : 0);                // 2 possible values: 0, 1
    result = 2 * result + (facing ? 1 : 0);      // 2 possible values: 0, 1 
    result = 3 * result + marioMode;             // 3 possible values: 0, 1, 2
    result = 2 * result + (onGround ? 1 : 0);    // 2 possible values: 0, 1 
    result = 2 * result + (canJump ? 1 : 0);     // 2 possible values: 0, 1 
    result = 2 * result + (wallNear ? 1 : 0);    // 2 possible values: 0, 1 
    result = 33 * result + (16 + nearestEnemyX); // 33 possible values: - 16 to 16
    result = 33 * result + (16 + nearestEnemyY); // 33 possible values: - 16 to 16

    return result;
}

这将为您提供 104544 个可能的 hashCodes() 顺便说一句,您可以通过使用一系列/%

于 2014-05-13T14:48:19.470 回答
-1

尝试 Guava 的hashCode()方法或 JDK7 的Objects.hash(). 这比自己写要好得多。不要自己重复代码(以及可以使用开箱即用解决方案的任何其他人):

于 2014-05-13T14:29:39.570 回答