SQL Server中Checksum系列函数的算法及哈希碰撞识别方法咨询

Great question! Let's break this down clearly for you, since understanding how these SQL Server functions work (and their limitations) is key to using them safely for change tracking.

Microsoft doesn't publish the exact proprietary implementation details for these functions, but we can confirm their core behavior and algorithm families:

• CHECKSUM(): Generates a 32-bit integer hash using a CRC-like (Cyclic Redundancy Check) algorithm optimized for speed. It processes inputs sequentially:
  • For strings, it uses the database's collation to normalize values (so case-insensitive collations will treat 'Test' and 'test' as identical for checksum purposes).
  • NULL values are treated as 0, and intermediate results are combined via bitwise operations to produce the final 32-bit integer.
• BINARY_CHECKSUM(): Also a 32-bit integer hash, but it operates directly on the binary representation of inputs. This makes it:
  • Sensitive to case, accents, and raw byte differences in strings (unlike CHECKSUM()).
  • Dependent on exact data type storage (e.g., BINARY_CHECKSUM(CAST(1 AS INT)) may differ from BINARY_CHECKSUM(CAST(1 AS BIGINT))).
  • It also treats NULL as 0 and uses similar bitwise logic to combine results.
• CHECKSUM_AGG(): An aggregate function that computes a cumulative hash over a set of CHECKSUM values using simple bitwise XOR:
  • It iterates over non-NULL values in the group, XORing each value with a running total.
  • XOR's commutative/associative properties mean different value sets can produce identical results (e.g., XORing 1 and 3 gives 2, same as XORing 2 and 0).

Collisions (distinct inputs producing the same hash) are inevitable with 32-bit hashes (only ~4 billion possible values), but you can spot common scenarios and test for them:

Common Collision Scenarios #

• CHECKSUM()/BINARY_CHECKSUM():
  • Input order: Multi-column checksums like CHECKSUM(col1, col2) may match CHECKSUM(col2, col1) if bitwise combinations cancel out differences.
  • Collation equivalence: With case-insensitive collations, CHECKSUM('Apple') and CHECKSUM('apple') will match despite being distinct strings.
  • Natural value collisions: Some distinct numeric or string pairs will hash to the same 32-bit integer due to the algorithm's bitwise logic (many documented examples exist in SQL Server communities).
• CHECKSUM_AGG():
  • Even duplicates: A group with an even number of identical checksum values will XOR to 0 (e.g., two rows with checksum 5 cancel each other out), matching the result of another group that also XORs to 0.
  • Equivalent XOR combinations: Different value sets can produce the same cumulative result (e.g., a group with [1,2,3] may match a group with [0,1,2,3,0] since adding two 0s cancels out).

How to Test for Collisions #

• Direct comparison queries: Write simple tests to catch unexpected matches:

  -- Test CHECKSUM case sensitivity based on your collation
  SELECT CHECKSUM('Test'), CHECKSUM('test');
  -- Test BINARY_CHECKSUM binary sensitivity
  SELECT BINARY_CHECKSUM('Test'), BINARY_CHECKSUM('test');
  -- Find duplicate CHECKSUM_AGG results across different groups
  SELECT group_id, CHECKSUM_AGG(CHECKSUM(col1)) AS agg_hash
  FROM your_table
  GROUP BY group_id
  HAVING COUNT(DISTINCT agg_hash) < COUNT(group_id);
  

• Construct known collisions: Search community resources for documented collision pairs, or generate your own by iterating through values until you find matching hashes.
• Cross-verify changes: If using these functions for change detection, always cross-check with a full row comparison when a checksum match occurs to rule out false negatives from collisions.

Critical Note #

These functions are built for fast change detection, not cryptographic security or absolute uniqueness. For collision-resistant hashing, use HASHBYTES() with a strong algorithm like SHA2_256 instead.

内容的提问来源于stack exchange，提问作者Bheemsen Singh