bash - Bash 中的 Java String.hashCode() 实现

Question

我正在尝试在 Bash 中实现 String.hashCode() 函数。我无法找出错误。

这是我的示例实现

function hashCode(){ #similar function to java String.hashCode()
foo=$1
echo $foo
h=0
for (( i=0; i<${#foo}; i++ )); do
    val=$(ord ${foo:$i:1})
    echo $val
    if ((31 * h + val > 2147483647)) 
    then
        h=$((-2147483648 + (31 * h + val) % 2147483648 ))

    elif ((31 * h + val < -2147483648))
    then
        h=$(( 2147483648 - ( 31 * h + val) % 2147483648 )) 
    else
        h=$(( 31 * h + val))
    fi
done
printf %d $h
}

function ord() { #asci to int conversion
    LC_CTYPE=C printf %d "'$1"
}

Java 函数如下所示

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

字符串“__INDEX_STAGING_DATA__0_1230ee6d-c37a-46cf-821c-55412f543fa6”的预期输出为“1668783629”，但输出为-148458597

注意 - 必须处理 java int 上溢和下溢。

Answer 1

Vinujan，您的代码正在使用您所包含的算法对给定字符串进行哈希处理。您不需要 ord 函数，因为您可以使用 printf -v val "%d""'${foo:$i:1}" 将文字转换为 ASCII 值code>(除非您需要 LC_CTYPE=C 来区分字符集)。

例如，只需对代码进行一些小的调整，它就会正确地散列字符串“hello”:

#!/bin/bash

function hashCode() {
    local foo="$1"
    local -i h=0
    for ((i = 0; i < ${#foo}; i++)); do

        printf -v val "%d" "'${foo:$i:1}"  # val is ASCII val

        if ((31 * h + val > 2147483647))   # hash scheme
        then
            h=$((-2147483648 + (31 * h + val) % 2147483648 ))
        elif ((31 * h + val < -2147483648))
        then
            h=$(( 2147483648 - ( 31 * h + val) % 2147483648 )) 
        else
            h=$(( 31 * h + val))
        fi
    done
    printf "%d" $h    # final hashCode in decimal
}

hash=$(hashCode "$1")

printf "\nhashCode: 0x%02x (%d decimal)\n" $hash $hash

示例使用/输出

$ bash hashcode.sh hello

hashCode: 0x5e918d2 (99162322 decimal)

你看起来有问题的地方在于散列算法本身。例如，像 password 这样的较长字符串将导致您的方案返回看起来可疑的负 64 位值，例如:

$ bash hashcode.sh password

hashCode: 0xffffffffb776462d (-1216985555 decimal)

这可能是您想要的哈希值，我没有什么可以比较该算法的。检查一遍，如果您仍然有问题，请编辑您的问题并准确描述问题/错误/等。当您运行脚本并将输出添加到您的问题时，您会得到。

---

编辑哈希函数以获得更好的行为

如果没有要实现的算法，我唯一能做的就是重新制定您提供的算法，以便在计算超过 INT_MAX/INT_MIN 时表现更好。看看您现有的算法，当遇到大量数字时，它似乎使问题变得更糟，而不是平滑值以确保它们保持在范围内。

坦率地说，在减少值模 2147483648 之前，您似乎省略了对 h 减去 INT_MIN 或添加 INT_MAX code> 当它超过/低于这些限制时。 (例如，您忘记了减法和加法周围的括号)简单地将其添加到哈希算法中似乎会产生更好的行为和您想要的输出。

我还将哈希计算的结果保存在 hval 中，这样就不会在每个循环中多次计算它，例如

function hashCode() {
    local foo="$1"
    local -i h=0
    for ((i = 0; i < ${#foo}; i++)); do

        printf -v val "%d" "'${foo:$i:1}"  # val is ASCII val

        hval=$((31 * h + val))

        if ((hval > 2147483647))   # hash scheme
        then
            h=$(( (hval - 2147483648) % 2147483648 ))
        elif ((hval < -2147483648))
        then
            h=$(( (hval + 2147483648) % 2147483648 ))
        else
            h=$(( hval ))
        fi
    done
    printf "%d" $h    # final hashCode in decimal
}

新值(value)观

请注意，"hello" 的哈希值保持不变(如您所料)，但 "password" 的值现在表现更好，并返回如下所示的值会是预期的，而不是一些符号扩展的 64 位值。例如，

$ bash hashcode2.sh hello

hashCode: 0x5e918d2 (99162322 decimal)

$ bash hashcode2.sh password

hashCode: 0x4889ba9b (1216985755 decimal)

请注意，它确实会产生您预期的输出:

$ bash hashcode2.sh "__INDEX_STAGING_DATA__0_1230ee6d-c37a-46cf-821c-55412f543fa6"

hashCode: 0x63779e0d (1668783629 decimal)

请告诉我这是否是您想要做的更多事情。