Java Hashcode提供整数溢出

Question

背景资料:

在我的项目中,我正在将强化学习(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,我可能需要一个正确的编码.

Answer 1

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

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

.hashCode()旨在在分组算法中提供良好的一般结果,这可以容忍轻微的冲突.它不是为提供唯一密钥而设计的.默认算法是时间和空间以及轻微碰撞的折衷,它不应该保证唯一性.

完美的哈希

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

独特的哈希

使用的一种方法是使用SHA1内置于标准库中的散列,该小型数据集的冲突几率极低.您发布的值不会发生巨大的组合爆炸SHA1.

您应该能够minimal perfect hash使用您在问题中显示的有限值来计算生成a的方法.

最小完美散列函数是一个完美的散列函数,它将n个键映射到n个连续的整数 - 通常为[0..n-1]或[1..n].更正式的表达方式是:设j和k是某个有限集K的元素.F是最小完美散列函数iff 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()方法.

类型3 UUID和UUID.nameUUIDFromBytes()一样有用

版本3 UUID使用从URL通过MD5派生UUID的方案,完全限定的域名,对象标识符,可分辨名称(轻量级目录访问协议中使用的DN)或未指定名称空间中的名称.版本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();
        }
    }
}

Answer 2

对于对象状态的唯一表示,总共需要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)
}