collision.rb

require 'securerandom'

N = 1_000_000
M = 16

s = Array.new(N) { SecureRandom.hex(M) }
s.sort!

def lcs(a, b)
  M.times do |i|
    return i if a[i] != b[i]
  end
  return M
end

buckets = Hash.new(1)

s.each_cons(2) do |a, b|
  l = lcs(a, b)
  buckets[l] += 1
end

puts buckets.inspect