Hash Functions

Overview

Hash functions transform input data of arbitrary size into fixed-size output values. These mathematical functions accept any data type—strings, integers, objects, or files—and produce a hash value, hash code, or digest. The output size remains constant regardless of input length.

Two primary categories exist: non-cryptographic hash functions optimize for speed in data structure operations, while cryptographic hash functions prioritize security properties for digital signatures, password storage, and data integrity verification. Non-cryptographic hashes power hash tables, checksums, and data partitioning. Cryptographic hashes provide one-way transformations resistant to reverse engineering and collision attacks.

The hash value acts as a compact representation or fingerprint of the input data. Applications range from hash tables in programming languages to blockchain technology and digital forensics. Ruby provides both categories through built-in hash table support and the Digest standard library.

# Non-cryptographic hash for object identity
"password".hash
# => 1879890712345678901

# Cryptographic hash for security
require 'digest'
Digest::SHA256.hexdigest("password")
# => "5e884898da28047151d0e56f8dc6292773603d0d6aabbdd62a11ef721d1542d8"

Key Principles

Hash functions operate on three fundamental principles: determinism, fixed output size, and efficient computation. Determinism requires identical inputs to always produce identical outputs. A hash function that generates different values for the same input violates this core requirement and cannot reliably map data.

The fixed output size principle constrains hash values to predetermined bit lengths regardless of input size. A function producing 256-bit output generates exactly 256 bits whether hashing a single character or an entire database. This property enables predictable memory allocation and uniform index distribution in hash tables.

Efficient computation demands hash functions execute quickly relative to input size. Linear time complexity O(n) represents the standard expectation, where n equals input length. Hash functions requiring polynomial or exponential time fail practical applications requiring millions of operations per second.

Additional properties distinguish quality hash functions. The avalanche effect describes how single-bit input changes should alter approximately half the output bits. This sensitivity prevents similar inputs from clustering in nearby hash values. A hash function mapping "password" and "passwore" to adjacent values exhibits poor avalanche characteristics.

require 'digest'

# Demonstrating avalanche effect
hash1 = Digest::SHA256.hexdigest("password")
hash2 = Digest::SHA256.hexdigest("passwore")

# Hashes differ completely despite one character change
hash1[0..10]
# => "5e884898da2"
hash2[0..10]
# => "b9b8f9b1ec3"

Uniform distribution requires hash values to spread evenly across the output space. Hash functions concentrating values in narrow ranges create performance bottlenecks in data structures. Statistical analysis measures distribution quality through chi-square tests and collision frequency examination.

Collision resistance matters for cryptographic applications. A collision occurs when two different inputs produce identical hash values. Non-cryptographic functions tolerate collisions and implement resolution strategies. Cryptographic functions must make collision discovery computationally infeasible—finding two inputs that hash to the same value should require brute-force attempts approaching 2^(n/2) operations for n-bit output.

The pigeonhole principle guarantees collisions exist. Infinite possible inputs mapping to finite output space ensures multiple inputs share hash values. A 32-bit hash function produces 4,294,967,296 possible values but accepts unlimited input variations. The distinction lies in collision probability and discovery difficulty.

Pre-image resistance prevents attackers from deriving input from output. Given hash value h, finding any input x where hash(x) = h should require exhaustive search. Second pre-image resistance strengthens this—given input x1 and hash(x1), finding different x2 where hash(x2) = hash(x1) must remain computationally infeasible.

Ruby Implementation

Ruby implements non-cryptographic hashing through the Object#hash method, which generates integer hash codes for equality comparison and hash table indexing. Every object inherits this method, and Ruby's Hash class relies on these values for key-value storage.

# Default hash implementation
"test".hash
# => 432398423789234

# Custom hash implementation
class Point
  attr_reader :x, :y
  
  def initialize(x, y)
    @x = x
    @y = y
  end
  
  def hash
    [@x, @y].hash
  end
  
  def eql?(other)
    other.is_a?(Point) && @x == other.x && @y == other.y
  end
end

p1 = Point.new(5, 10)
p2 = Point.new(5, 10)

# Same coordinates produce same hash
p1.hash == p2.hash
# => true

The hash method must maintain consistency with eql?. Objects comparing as equal must produce identical hash values. Violating this contract breaks hash table functionality, causing failed lookups and duplicate keys.

# Hash table behavior depends on hash/eql? consistency
hash_table = {}
point = Point.new(3, 7)

hash_table[point] = "location"
hash_table[Point.new(3, 7)]
# => "location" - retrieval works due to matching hash/eql?

Cryptographic hashing resides in the Digest library, offering multiple algorithms with varying security levels and performance characteristics. SHA-256 represents the current recommended standard for most applications, balancing security and speed.

require 'digest'

# SHA-256 - recommended for general use
Digest::SHA256.hexdigest("data")
# => "3a6eb0790f39ac87c94f3856b2dd2c5d110e6811602261a9a923d3bb23adc8b7"

# SHA-512 - higher security, larger output
Digest::SHA512.hexdigest("data")
# => "77c7ce9a5d86bb386d443bb96390faa120633158699c8844c30b13ab0bf92760..."

# MD5 - deprecated, shown for compatibility only
Digest::MD5.hexdigest("data")
# => "8d777f385d3dfec8815d20f7496026dc"

Binary digest output provides compact representation compared to hexadecimal strings. Security applications often use binary digests directly, while hexadecimal facilitates human-readable display and text-based protocols.

# Binary vs hexadecimal output
binary_digest = Digest::SHA256.digest("data")
binary_digest.bytesize
# => 32

hex_digest = Digest::SHA256.hexdigest("data")
hex_digest.length
# => 64

# Convert between formats
Digest::SHA256.hexdigest("data") == Digest::SHA256.digest("data").unpack1('H*')
# => true

Streaming interfaces handle large inputs without loading entire content into memory. This approach suits file hashing and processing data exceeding available RAM.

# Streaming hash computation for large files
def hash_file(path)
  digest = Digest::SHA256.new
  
  File.open(path, 'rb') do |file|
    while chunk = file.read(8192)
      digest.update(chunk)
    end
  end
  
  digest.hexdigest
end

# Hash 1GB file without loading into memory
hash_file('large_database.sql')
# => "a1b2c3d4..."

Password hashing requires specialized algorithms that intentionally slow computation to resist brute-force attacks. Ruby's bcrypt gem implements the industry-standard bcrypt algorithm with configurable work factors.

require 'bcrypt'

# Generate password hash with cost factor 12
password_hash = BCrypt::Password.create("user_password", cost: 12)
# => "$2a$12$K3Qj3Qj3Qj3Qj3Qj3Qj3QuK3Qj3Qj3Qj3Qj3Qj3Qj3Qj3Qj3Qj"

# Verify password
password_hash == "user_password"
# => true

password_hash == "wrong_password"
# => false

Practical Examples

Hash tables implement associative arrays through hash function-based indexing. Ruby's Hash class demonstrates this application, converting keys to array indices for constant-time average lookup.

# Hash table internals conceptual example
class SimpleHashTable
  def initialize(size = 16)
    @buckets = Array.new(size) { [] }
    @size = size
  end
  
  def set(key, value)
    index = key.hash % @size
    bucket = @buckets[index]
    
    # Update existing or append new
    entry = bucket.find { |k, v| k == key }
    if entry
      entry[1] = value
    else
      bucket << [key, value]
    end
  end
  
  def get(key)
    index = key.hash % @size
    bucket = @buckets[index]
    entry = bucket.find { |k, v| k == key }
    entry ? entry[1] : nil
  end
end

table = SimpleHashTable.new
table.set("name", "Alice")
table.set("age", 30)
table.get("name")
# => "Alice"

File integrity verification uses cryptographic hashes to detect corruption or tampering. Systems compare current file hash against known-good reference hash to confirm authenticity.

require 'digest'

class FileVerifier
  def initialize(file_path)
    @path = file_path
    @stored_hash = nil
  end
  
  def compute_hash
    digest = Digest::SHA256.new
    
    File.open(@path, 'rb') do |file|
      while chunk = file.read(16384)
        digest.update(chunk)
      end
    end
    
    digest.hexdigest
  end
  
  def store_hash
    @stored_hash = compute_hash
  end
  
  def verify
    current_hash = compute_hash
    current_hash == @stored_hash
  end
end

verifier = FileVerifier.new('important_data.json')
verifier.store_hash

# Later, check if file changed
verifier.verify
# => true if unchanged, false if modified

Data deduplication identifies identical content across multiple files or data blocks. Hash-based comparison avoids byte-by-byte content comparison, reducing storage requirements and network bandwidth.

require 'digest'

class Deduplicator
  def initialize
    @hash_store = {}
  end
  
  def add_content(content)
    hash = Digest::SHA256.hexdigest(content)
    
    if @hash_store.key?(hash)
      # Duplicate detected
      @hash_store[hash][:count] += 1
      { status: :duplicate, hash: hash }
    else
      # New unique content
      @hash_store[hash] = { content: content, count: 1 }
      { status: :unique, hash: hash }
    end
  end
  
  def stats
    total_blocks = @hash_store.values.sum { |v| v[:count] }
    unique_blocks = @hash_store.size
    
    {
      total: total_blocks,
      unique: unique_blocks,
      duplicates: total_blocks - unique_blocks
    }
  end
end

dedup = Deduplicator.new
dedup.add_content("Block A")
# => { status: :unique, hash: "..." }
dedup.add_content("Block A")
# => { status: :duplicate, hash: "..." }
dedup.stats
# => { total: 2, unique: 1, duplicates: 1 }

Distributed systems use consistent hashing to map data across cluster nodes while minimizing reassignment during node additions or removals. This technique maintains cache efficiency and reduces rebalancing overhead.

require 'digest'

class ConsistentHash
  def initialize(nodes, virtual_nodes = 150)
    @ring = {}
    @nodes = nodes
    @virtual_nodes = virtual_nodes
    
    nodes.each { |node| add_node(node) }
  end
  
  def add_node(node)
    @virtual_nodes.times do |i|
      position = hash_position("#{node}-#{i}")
      @ring[position] = node
    end
  end
  
  def get_node(key)
    return nil if @ring.empty?
    
    position = hash_position(key)
    sorted_positions = @ring.keys.sort
    
    # Find first node position >= key position
    node_position = sorted_positions.find { |p| p >= position }
    node_position ||= sorted_positions.first
    
    @ring[node_position]
  end
  
  private
  
  def hash_position(key)
    Digest::MD5.hexdigest(key).to_i(16) % (2**32)
  end
end

# Distribute keys across cluster nodes
cluster = ConsistentHash.new(['node1', 'node2', 'node3'])
cluster.get_node('user:1234')
# => "node2"
cluster.get_node('session:abc')
# => "node1"

Security Implications

Cryptographic hash functions provide security guarantees through mathematical properties resistant to various attack vectors. Pre-image resistance prevents reverse computation—given hash output, attackers cannot feasibly determine original input. This property protects password storage by making stored hashes useless for password recovery.

Second pre-image resistance defends against substitution attacks. Given input x1 and its hash, attackers cannot find different input x2 producing the same hash. Without this protection, attackers could forge documents or substitute malicious content while maintaining valid signatures.

Collision resistance makes finding any two inputs producing identical hashes computationally infeasible. Birthday paradox mathematics reduces collision search complexity from 2^n to approximately 2^(n/2) operations for n-bit hashes. A 256-bit hash requires roughly 2^128 attempts to find collisions—currently impossible with existing computational resources.

require 'digest'

# Password storage - secure approach
class PasswordManager
  def self.hash_password(password, salt = generate_salt)
    # Never store plain passwords
    combined = salt + password
    hash = Digest::SHA256.hexdigest(combined)
    salt + ':' + hash
  end
  
  def self.verify_password(password, stored)
    salt, stored_hash = stored.split(':')
    computed_hash = Digest::SHA256.hexdigest(salt + password)
    computed_hash == stored_hash
  end
  
  def self.generate_salt
    SecureRandom.hex(16)
  end
end

# Store hash, never plain password
stored = PasswordManager.hash_password("secret123")
# => "a1b2c3d4...:e5f6g7h8..."

PasswordManager.verify_password("secret123", stored)
# => true

Rainbow table attacks precompute hash values for common passwords, enabling instant password cracking through lookup. Salting defeats this attack by appending random data before hashing. Unique salts per password force attackers to recompute rainbow tables for each password.

require 'bcrypt'

# Bcrypt automatically handles salting
class SecureAuth
  def self.create_user(username, password)
    # Cost factor 12 = 2^12 iterations
    password_hash = BCrypt::Password.create(password, cost: 12)
    
    {
      username: username,
      password_hash: password_hash.to_s
    }
  end
  
  def self.authenticate(user_data, password)
    stored_hash = BCrypt::Password.new(user_data[:password_hash])
    stored_hash == password
  end
end

user = SecureAuth.create_user("alice", "correct_horse_battery_staple")
SecureAuth.authenticate(user, "wrong_password")
# => false
SecureAuth.authenticate(user, "correct_horse_battery_staple")
# => true

Timing attacks exploit measurement of hash comparison duration to leak information. Constant-time comparison prevents this by examining all bytes regardless of early mismatches.

# Vulnerable to timing attack
def insecure_compare(a, b)
  return false if a.length != b.length
  a.bytes.zip(b.bytes).all? { |x, y| x == y }  # Fails fast on mismatch
end

# Constant-time comparison
def secure_compare(a, b)
  return false if a.length != b.length
  
  result = 0
  a.bytes.zip(b.bytes).each { |x, y| result |= x ^ y }
  result == 0
end

# Ruby provides secure comparison
require 'openssl'

OpenSSL.secure_compare(hash1, hash2)
# => true or false, timing independent of content

Algorithm selection impacts security posture. MD5 and SHA-1 suffer from known vulnerabilities enabling collision attacks. Production systems must migrate to SHA-256 or SHA-3 family algorithms.

require 'digest'

# Deprecated algorithms - avoid in new systems
Digest::MD5.hexdigest("data")      # Collision attacks exist
Digest::SHA1.hexdigest("data")     # Collision attacks demonstrated

# Current recommendations
Digest::SHA256.hexdigest("data")   # Minimum standard
Digest::SHA512.hexdigest("data")   # Higher security margin
Digest::SHA3_256.hexdigest("data") # Latest standard (Ruby 2.5+)

Performance Considerations

Hash function performance directly impacts application throughput in data structures, caching systems, and security operations. Non-cryptographic hashes prioritize speed, typically processing gigabytes per second on modern processors. Cryptographic hashes trade performance for security, operating orders of magnitude slower.

Hash table operations achieve O(1) average complexity through efficient hash computation and distribution. Poor hash functions create clustering, degrading performance to O(n) as collision chains grow. Load factor—ratio of entries to buckets—affects performance; rehashing occurs when load exceeds thresholds, typically 0.75.

require 'benchmark'

# Compare hash function performance
Benchmark.bmbm do |x|
  data = "x" * 1_000_000  # 1MB string
  
  x.report("Object#hash:") do
    10_000.times { data.hash }
  end
  
  x.report("SHA-256:") do
    require 'digest'
    100.times { Digest::SHA256.hexdigest(data) }
  end
  
  x.report("SHA-512:") do
    100.times { Digest::SHA512.hexdigest(data) }
  end
  
  x.report("MD5:") do
    100.times { Digest::MD5.hexdigest(data) }
  end
end

# Typical results show 100x-1000x difference
# Object#hash: 0.001s for 10k ops
# SHA-256: 0.100s for 100 ops (much slower)

Memory access patterns influence cache performance. Hash functions requiring multiple memory references suffer cache misses. Algorithms processing data sequentially maintain better cache locality than random access patterns.

Block-based streaming reduces memory overhead for large inputs. Loading entire files into memory before hashing wastes resources and fails for inputs exceeding available RAM. Buffer sizes between 4KB-64KB balance I/O efficiency with memory usage.

require 'digest'
require 'benchmark'

def hash_loaded(path)
  content = File.read(path)
  Digest::SHA256.hexdigest(content)
end

def hash_streamed(path, buffer_size = 16384)
  digest = Digest::SHA256.new
  
  File.open(path, 'rb') do |file|
    while chunk = file.read(buffer_size)
      digest.update(chunk)
    end
  end
  
  digest.hexdigest
end

# Compare memory and performance
Benchmark.bm do |x|
  x.report("Load entire file:") { hash_loaded('large_file.bin') }
  x.report("Stream 16KB chunks:") { hash_streamed('large_file.bin') }
end

# Streaming uses constant memory regardless of file size

Password hashing deliberately incorporates computational cost through iteration counts or memory-hard algorithms. Bcrypt's cost parameter controls work factor—cost 12 performs 2^12 iterations. Each cost increment doubles computation time, creating exponential defender advantage over attackers.

require 'bcrypt'
require 'benchmark'

# Demonstrate cost factor impact
Benchmark.bm(15) do |x|
  password = "test_password"
  
  x.report("Cost 4:") do
    BCrypt::Password.create(password, cost: 4)
  end
  
  x.report("Cost 8:") do
    BCrypt::Password.create(password, cost: 8)
  end
  
  x.report("Cost 12:") do
    BCrypt::Password.create(password, cost: 12)
  end
end

# Each increase doubles time
# Cost 4: ~0.001s
# Cost 8: ~0.016s (16x slower)
# Cost 12: ~0.256s (16x slower again)

Parallelization accelerates batch hashing operations. Independent hash computations distribute across CPU cores without synchronization overhead. Ruby's thread pool or process-based parallelism exploits multi-core processors.

require 'digest'
require 'concurrent-ruby'

# Parallel file hashing
def hash_files_parallel(file_paths)
  pool = Concurrent::FixedThreadPool.new(4)
  promises = file_paths.map do |path|
    Concurrent::Promise.execute(executor: pool) do
      digest = Digest::SHA256.new
      
      File.open(path, 'rb') do |file|
        while chunk = file.read(16384)
          digest.update(chunk)
        end
      end
      
      [path, digest.hexdigest]
    end
  end
  
  promises.map(&:value).to_h
ensure
  pool.shutdown
  pool.wait_for_termination
end

# Process 100 files using 4 cores
results = hash_files_parallel(Dir['data/*.json'])
# => { "data/file1.json" => "a1b2c3...", "data/file2.json" => "d4e5f6..." }

Common Pitfalls

Hash collisions in custom implementations often result from poor hash function design. Summing character codes or using multiplication by small primes creates clustering. Languages provide tested implementations—avoid writing custom hash functions without understanding collision probability mathematics.

# Poor hash function - high collision rate
class BadPoint
  attr_reader :x, :y
  
  def initialize(x, y)
    @x, @y = x, y
  end
  
  def hash
    @x + @y  # Many different points produce same sum
  end
end

# Better hash function
class GoodPoint
  attr_reader :x, :y
  
  def initialize(x, y)
    @x, @y = x, y
  end
  
  def hash
    [@x, @y].hash  # Ruby's tested implementation
  end
end

# Demonstrate collision problem
bad_points = [BadPoint.new(1, 5), BadPoint.new(2, 4), BadPoint.new(3, 3)]
bad_points.map(&:hash)
# => [6, 6, 6] - all collide

good_points = [GoodPoint.new(1, 5), GoodPoint.new(2, 4), GoodPoint.new(3, 3)]
good_points.map(&:hash)
# => [23423, 45645, 78978] - well distributed

Hash and equality method inconsistency breaks hash table functionality. Objects comparing as equal must produce identical hashes. Modifying eql? without updating hash causes hash table lookup failures.

# Broken implementation
class BrokenKey
  attr_accessor :value
  
  def initialize(value)
    @value = value
  end
  
  def eql?(other)
    other.is_a?(BrokenKey) && @value == other.value
  end
  
  # Forgot to override hash - uses default Object#hash
end

hash_table = {}
key1 = BrokenKey.new(42)
hash_table[key1] = "stored"

key2 = BrokenKey.new(42)
key1.eql?(key2)
# => true

hash_table[key2]
# => nil - lookup fails despite equality

Mutable keys in hash tables cause lookup failures after modification. Hash values compute from key content at insertion time. Changing keys after insertion orphans values at old hash positions.

# Mutable key problem
key = [1, 2, 3]
hash_table = { key => "value" }

hash_table[key]
# => "value" - works initially

key << 4  # Modify key
hash_table[key]
# => nil - fails because hash changed

# Solution: freeze keys or use immutable objects
key = [1, 2, 3].freeze
hash_table = { key => "value" }

key << 4
# => FrozenError: can't modify frozen Array

Password storage using fast cryptographic hashes enables brute-force attacks. SHA-256 computes billions of hashes per second on GPUs, allowing rapid password guessing. Password hashing requires deliberate computational cost through algorithms like bcrypt, scrypt, or Argon2.

# Insecure password storage
class InsecureAuth
  def self.hash_password(password)
    Digest::SHA256.hexdigest(password)  # Too fast
  end
end

# Secure password storage
require 'bcrypt'

class SecureAuth
  def self.hash_password(password)
    BCrypt::Password.create(password, cost: 12)  # Deliberately slow
  end
end

# Attack scenario simulation
require 'benchmark'

Benchmark.bm do |x|
  x.report("SHA-256 1M hashes:") do
    1_000_000.times { Digest::SHA256.hexdigest("guess") }
  end
  
  x.report("Bcrypt 100 hashes:") do
    100.times { BCrypt::Password.create("guess", cost: 12) }
  end
end

# SHA-256: ~1 second for 1M attempts
# Bcrypt: ~25 seconds for 100 attempts (250,000x slower per hash)

Salt reuse across passwords enables parallel rainbow table attacks. Each password requires unique random salt. Storing salt separately from hash leaks no information—salts protect against precomputation, not discovery.

# Wrong - same salt for all passwords
GLOBAL_SALT = "app_wide_salt"

def insecure_hash(password)
  Digest::SHA256.hexdigest(GLOBAL_SALT + password)
end

# Correct - unique salt per password
require 'securerandom'

def secure_hash(password)
  salt = SecureRandom.hex(16)
  hash = Digest::SHA256.hexdigest(salt + password)
  { salt: salt, hash: hash }
end

Truncating cryptographic hashes reduces security proportionally. Using first 64 bits of SHA-256 output provides only 32-bit collision resistance, not 128-bit. Applications requiring shortened hashes must account for reduced security guarantees.

# Truncation reduces collision resistance
full_hash = Digest::SHA256.hexdigest("data")
# => "3a6eb0790f39ac87..." (256 bits)

truncated = full_hash[0..7]
# => "3a6eb079" (32 bits) - only 2^16 collision resistance

Reference

Common Hash Algorithms

Ruby Hash Method Signatures

Performance Characteristics

Security Properties

Hash Table Configuration

Ruby Standard Library Digest Algorithms

require 'digest'

# Available algorithms
Digest::MD5
Digest::SHA1
Digest::SHA256
Digest::SHA384
Digest::SHA512
Digest::SHA3_256    # Ruby 2.5+
Digest::SHA3_384    # Ruby 2.5+
Digest::SHA3_512    # Ruby 2.5+

# File hashing helper
Digest::SHA256.file('path/to/file.txt').hexdigest

Bcrypt Cost Recommendations

Common Pitfalls Reference