sql-server - SQL Server 中的 Checksum()、Binary_Checksum() 和 CHECKSUM_AVG() 函数使用哪种算法？

Question

Checksum()、Binary_Checksum() 和CHECKSUM_AVG() 函数由 SQL Server 提供，用于根据表达式构建哈希索引或列列表。
这有助于确定行是否已更改。然后可以使用该机制来识别记录是否已更新。

我发现了很多为不同值生成相同散列值的冲突示例。我们如何识别这些函数的碰撞条件。

有人想知道在没有散列冲突的情况下使用哪种算法或技术生成/计算散列吗？

Answer 1

根据CHECKSUM weakness explained关于 sqlTeam 的文章:

The built-in CHECKUM function in SQL Server is built on a series of 4 bit left rotational xor operations.

A forum post from 2006 (文章中也有链接)由 Peter Larsson 发布，其中包含计算校验和的 sql 用户定义函数。帖子的作者声称与 SQL Server 的内置功能 100% 兼容(我自己没有测试过)。

万一链接失效，这里是相关部分的副本:

With text/varchar/image data, call with SELECT BINARY_CHECKSUM('abcdefghijklmnop'), dbo.fnPesoBinaryChecksum('abcdefghijklmnop')With integer data, call with SELECT BINARY_CHECKSUM(123), dbo.fnPesoBinaryChecksum(CAST(123 AS VARBINARY))I haven't figured out how to calculate checksum for integers greater than 255 yet.

CREATE FUNCTION dbo.fnPesoBinaryChecksum
(
    @Data IMAGE
)
RETURNS INT
AS

BEGIN
    DECLARE @Index INT,
        @MaxIndex INT,
        @SUM BIGINT,
        @Overflow TINYINT

    SELECT  @Index = 1,
        @MaxIndex = DATALENGTH(@Data),
        @SUM = 0

    WHILE @Index <= @MaxIndex
        SELECT  @SUM = (16 * @SUM) ^ SUBSTRING(@Data, @Index, 1),
            @Overflow = @SUM / 4294967296,
            @SUM = @SUM - @Overflow * 4294967296,
            @SUM = @SUM ^ @Overflow,
            @Index = @Index + 1

    IF @SUM > 2147483647
        SET @SUM = @SUM - 4294967296
    ELSE IF @SUM BETWEEN 32768 AND 65535
        SET @SUM = @SUM - 65536
    ELSE IF @SUM BETWEEN 128 AND 255
        SET @SUM = @SUM - 256

    RETURN @SUM
END

Actually this is an improvement of MS function, since it accepts TEXT and IMAGE data.

CREATE FUNCTION [dbo].[fnPesoTextChecksum]
(
    @Data TEXT
)
RETURNS INT
AS

BEGIN
    DECLARE @Index INT,
        @MaxIndex INT,
        @SUM BIGINT,
        @Overflow TINYINT

    SELECT  @Index = 1,
        @MaxIndex = DATALENGTH(@Data),
        @SUM = 0

    WHILE @Index <= @MaxIndex
        SELECT  @SUM = (16 * @SUM) ^ ASCII(SUBSTRING(@Data, @Index, 1)),
            @Overflow = @SUM / 4294967296,
            @SUM = @SUM - @Overflow * 4294967296,
            @SUM = @SUM ^ @Overflow,
            @Index = @Index + 1

    IF @SUM > 2147483647
        SET @SUM = @SUM - 4294967296
    ELSE IF @SUM BETWEEN 32768 AND 65535
        SET @SUM = @SUM - 65536
    ELSE IF @SUM BETWEEN 128 AND 255
        SET @SUM = @SUM - 256

    RETURN  @SUM
END

另一个不错的读物是 Exploring Hash Functions In SQL Server作者 Thomas Kejser，作者检查了 sql server 中内置的哈希函数的速度和质量。