Java实现Fibonacci Hash Function输出[0,1]区间值的问题求助

你的两个实现分别存在以下逻辑错误：

• 浮点版本：当hash * golden_ratio的结果超过Integer.MAX_VALUE（2^31-1）时，强制转int会固定返回Integer.MAX_VALUE，此时num - (int)num的结果必然大于1，完全不符合取小数部分的预期。同时浮点数乘法存在精度损失，大输入下哈希分布均匀性会明显下降。
• BigInteger版本：斐波那契哈希的核心逻辑是取整数乘法结果的高位，你使用了错误的mask值做按位与，且移位位数和位宽不匹配，才会输出超出范围的超大值。你用的魔数11400714819323198485本身是正确的，它是最接近2^64 / φ（φ为黄金分割比）的奇整数，是64位斐波那契哈希的标准魔数。

斐波那契哈希生成[0,1)区间值的标准逻辑是：将输入转为64位无符号整数，和魔数相乘得到128位乘积，取乘积的高64位，再缩放到[0,1)区间即可。

高性能版本（Java 8+ 推荐） #

直接使用JDK原生提供的64位无符号乘法高位计算方法，不需要BigInteger，性能极高：

public class FibonacciHash {
    // 64位斐波那契哈希标准魔数
    private static final long FIB_HASH_MAGIC = 11400714819323198485L;
    // 缩放系数：1 / 2^64，用于将64位无符号整数映射到[0,1)区间
    private static final double SCALE = 0x1.0p-64;

    public static double hash(int input) {
        // 将32位int输入转为无符号64位long，避免符号位干扰
        long unsignedInput = Integer.toUnsignedLong(input);
        // 计算两个64位整数相乘128位结果的高64位
        long highBits = Long.multiplyHigh(unsignedInput, FIB_HASH_MAGIC);
        // 翻转long的符号位，将有符号值映射为无符号等值，再缩放
        return (highBits + Long.MIN_VALUE) * SCALE;
    }
}

这个实现的输出范围严格在[0, 1)，最大值约为0.9999999999999999，永远不会返回大于等于1或小于0的结果，且哈希分布完全符合斐波那契哈希的均匀性要求。

兼容旧版本JDK的BigInteger版本 #

如果需要兼容Java 8以下版本，可以用BigInteger实现等价逻辑，注意不要额外加错误的mask：

import java.math.BigInteger;

public class FibonacciHash {
    private static final BigInteger FIB_HASH_MAGIC = new BigInteger("11400714819323198485");
    private static final BigInteger TWO_POW_64 = BigInteger.ONE.shiftLeft(64);

    public static double hash(int input) {
        BigInteger unsignedInput = BigInteger.valueOf(input & 0xFFFFFFFFL);
        BigInteger product = FIB_HASH_MAGIC.multiply(unsignedInput);
        // 取128位乘积的高64位
        BigInteger high64 = product.shiftRight(64);
        // 直接除以2^64映射到[0,1)区间
        return high64.doubleValue() / TWO_POW_64.doubleValue();
    }
}

• 不要使用浮点数直接乘黄金分割比取小数的方案，除了溢出问题，浮点数精度损失也会破坏哈希分布的均匀性，整数运算实现是工业界的标准做法。
• 如果需要和double类型的精度完全匹配，可以取乘积的高53位后除以2^53，分布效果一致，且不存在任何精度浪费。

内容的提问来源于stack exchange，提问作者Μιχάλης Αναστασίου