406 Intermediate

406: Hash, Eq, and Ord Traits

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "406: Hash, Eq, and Ord Traits" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. To use a type as a `HashMap` key or in a `HashSet`, it needs `Eq + Hash`. Key difference from OCaml: 1. **Structural comparison**: OCaml's `compare` works structurally on any type without annotation; Rust requires explicit derives or implementations.

Tutorial

The Problem

To use a type as a HashMap key or in a HashSet, it needs Eq + Hash. To use it in a BTreeMap or sorted collection, it needs Ord. These traits form a coherence hierarchy: Eq: PartialEq, Ord: Eq + PartialOrd. Implementing them incorrectly — hashing a value differently than how it compares for equality — leads to incorrect collection behavior and subtle bugs (items can be inserted but never found). Rust's type system and derive macros make the common case correct, but custom implementations require careful adherence to the mathematical laws.

These traits underpin every collection in std: HashMap, HashSet, BTreeMap, BTreeSet, and sorting via sort_by.

🎯 Learning Outcomes

• Understand the trait hierarchy: PartialEq → Eq, PartialOrd → Ord, and the Hash requirement for hash maps

• Learn the critical law: if a == b then hash(a) == hash(b) (but not vice versa)

• See how #[derive(PartialEq, Eq, Hash)] satisfies the laws automatically for structs

• Understand how to implement custom Ord for domain-specific ordering (e.g., priority levels)

• Learn how BTreeMap (sorted) and HashMap (hashed) have different key requirements

Code Example

use std::cmp::Ordering;
use std::collections::BTreeMap;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Priority { Low, Medium, High, Critical }

impl Ord for Priority {
    fn cmp(&self, other: &Self) -> Ordering {
        self.value().cmp(&other.value())
    }
}

impl PartialOrd for Priority {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Priority {
    fn value(&self) -> u8 {
        match self { Self::Low => 0, Self::Medium => 1,
                     Self::High => 2, Self::Critical => 3 }
    }
}

fn main() {
    let mut map = BTreeMap::new();
    map.insert(Priority::High, "urgent");
    println!("{:?}", map.get(&Priority::High));
}

type priority = Low | Medium | High | Critical

let int_of_priority = function
  | Low -> 0 | Medium -> 1 | High -> 2 | Critical -> 3

let compare_priority a b =
  compare (int_of_priority a) (int_of_priority b)

module PriorityMap = Map.Make(struct
  type t = priority
  let compare = compare_priority
end)

let () =
  let map = PriorityMap.(empty |> add High "urgent") in
  match PriorityMap.find_opt High map with
  | Some v -> print_endline v
  | None -> ()

Key Differences

Structural comparison: OCaml's compare works structurally on any type without annotation; Rust requires explicit derives or implementations.

Hash coherence: Rust's type system doesn't enforce the Eq → Hash law — incorrect impls compile but cause runtime bugs; OCaml has the same risk.

Collection requirements: Rust's HashMap requires Eq + Hash; OCaml's Hashtbl uses polymorphic hash by default, requiring no annotation.

Ordered collections: Rust's BTreeMap requires Ord; OCaml's Map.Make takes an Ord module parameter at compile time.

OCaml Approach

OCaml uses the polymorphic compare : 'a -> 'a -> int for structural comparison and Hashtbl.hash : 'a -> int for hashing. Custom types get comparison for free since OCaml's comparison is structural by default. Map.Make(Ord) and Set.Make(Ord) create sorted collections using a provided comparator module. The ppx_compare and ppx_hash derivers generate type-specific compare/hash functions that OCaml's standard library uses.

Full Source

#![allow(clippy::all)]
//! Hash, Eq, and Ord Traits
//!
//! Traits for equality, ordering, and hashing — enabling HashMap/HashSet/BTreeMap keys.

use std::cmp::Ordering;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::hash::{Hash, Hasher};

/// A 2D point with derived Hash, Eq.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Point {
    pub x: i32,
    pub y: i32,
}

impl Point {
    pub fn new(x: i32, y: i32) -> Self {
        Point { x, y }
    }

    pub fn distance_squared(&self, other: &Point) -> i32 {
        let dx = self.x - other.x;
        let dy = self.y - other.y;
        dx * dx + dy * dy
    }
}

/// Priority levels with custom ordering.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Priority {
    Low,
    Medium,
    High,
    Critical,
}

impl Priority {
    fn value(&self) -> u8 {
        match self {
            Priority::Low => 0,
            Priority::Medium => 1,
            Priority::High => 2,
            Priority::Critical => 3,
        }
    }
}

impl PartialOrd for Priority {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Priority {
    fn cmp(&self, other: &Self) -> Ordering {
        self.value().cmp(&other.value())
    }
}

/// A task with custom ordering: higher priority first, then alphabetical.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Task {
    pub name: String,
    pub priority: Priority,
    pub id: u32,
}

impl Task {
    pub fn new(name: &str, priority: Priority, id: u32) -> Self {
        Task {
            name: name.to_string(),
            priority,
            id,
        }
    }
}

impl PartialOrd for Task {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Task {
    fn cmp(&self, other: &Self) -> Ordering {
        // Higher priority first (reverse), then alphabetical by name
        other
            .priority
            .cmp(&self.priority)
            .then(self.name.cmp(&other.name))
    }
}

/// A case-insensitive string wrapper.
#[derive(Debug, Clone)]
pub struct CaseInsensitive(pub String);

impl PartialEq for CaseInsensitive {
    fn eq(&self, other: &Self) -> bool {
        self.0.to_lowercase() == other.0.to_lowercase()
    }
}

impl Eq for CaseInsensitive {}

impl Hash for CaseInsensitive {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Hash the lowercase version for consistency with Eq
        self.0.to_lowercase().hash(state);
    }
}

/// Demonstrates HashMap with Point keys.
pub fn point_map_example() -> HashMap<Point, String> {
    let mut map = HashMap::new();
    map.insert(Point::new(0, 0), "origin".to_string());
    map.insert(Point::new(1, 0), "unit-x".to_string());
    map.insert(Point::new(0, 1), "unit-y".to_string());
    map
}

/// Demonstrates HashSet deduplication.
pub fn point_set_example(points: Vec<Point>) -> HashSet<Point> {
    points.into_iter().collect()
}

/// Sorts tasks by custom ordering.
pub fn sort_tasks(tasks: &mut [Task]) {
    tasks.sort();
}

/// Groups tasks by priority using BTreeMap.
pub fn group_by_priority(tasks: &[Task]) -> BTreeMap<Priority, Vec<String>> {
    let mut groups: BTreeMap<Priority, Vec<String>> = BTreeMap::new();
    for task in tasks {
        groups
            .entry(task.priority)
            .or_default()
            .push(task.name.clone());
    }
    groups
}

/// Demonstrates case-insensitive set.
pub fn case_insensitive_set(words: Vec<&str>) -> HashSet<CaseInsensitive> {
    words
        .into_iter()
        .map(|s| CaseInsensitive(s.to_string()))
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_point_eq() {
        let p1 = Point::new(1, 2);
        let p2 = Point::new(1, 2);
        let p3 = Point::new(2, 1);
        assert_eq!(p1, p2);
        assert_ne!(p1, p3);
    }

    #[test]
    fn test_point_hash_map() {
        let map = point_map_example();
        assert_eq!(map.get(&Point::new(0, 0)), Some(&"origin".to_string()));
        assert_eq!(map.get(&Point::new(1, 0)), Some(&"unit-x".to_string()));
    }

    #[test]
    fn test_point_set_dedup() {
        let points = vec![
            Point::new(1, 1),
            Point::new(2, 2),
            Point::new(1, 1), // duplicate
        ];
        let set = point_set_example(points);
        assert_eq!(set.len(), 2);
    }

    #[test]
    fn test_priority_ord() {
        assert!(Priority::Critical > Priority::High);
        assert!(Priority::High > Priority::Medium);
        assert!(Priority::Medium > Priority::Low);
    }

    #[test]
    fn test_priority_sort() {
        let mut priorities = vec![Priority::Medium, Priority::Critical, Priority::Low];
        priorities.sort();
        assert_eq!(
            priorities,
            vec![Priority::Low, Priority::Medium, Priority::Critical]
        );
    }

    #[test]
    fn test_task_sort_by_priority() {
        let mut tasks = vec![
            Task::new("Low task", Priority::Low, 1),
            Task::new("Critical task", Priority::Critical, 2),
        ];
        sort_tasks(&mut tasks);
        assert_eq!(tasks[0].name, "Critical task");
    }

    #[test]
    fn test_task_sort_alphabetical_within_priority() {
        let mut tasks = vec![
            Task::new("Zebra", Priority::High, 1),
            Task::new("Apple", Priority::High, 2),
        ];
        sort_tasks(&mut tasks);
        assert_eq!(tasks[0].name, "Apple");
    }

    #[test]
    fn test_group_by_priority() {
        let tasks = vec![
            Task::new("A", Priority::High, 1),
            Task::new("B", Priority::Low, 2),
            Task::new("C", Priority::High, 3),
        ];
        let groups = group_by_priority(&tasks);
        assert_eq!(
            groups.get(&Priority::High),
            Some(&vec!["A".to_string(), "C".to_string()])
        );
        assert_eq!(groups.get(&Priority::Low), Some(&vec!["B".to_string()]));
    }

    #[test]
    fn test_case_insensitive_eq() {
        let a = CaseInsensitive("Hello".to_string());
        let b = CaseInsensitive("HELLO".to_string());
        let c = CaseInsensitive("hello".to_string());
        assert_eq!(a, b);
        assert_eq!(b, c);
    }

    #[test]
    fn test_case_insensitive_set() {
        let set = case_insensitive_set(vec!["Hello", "HELLO", "World"]);
        assert_eq!(set.len(), 2); // "Hello" and "HELLO" are the same
    }

    #[test]
    fn test_btree_ordered_iteration() {
        let mut set = BTreeSet::new();
        set.insert(Priority::High);
        set.insert(Priority::Low);
        set.insert(Priority::Critical);
        let order: Vec<_> = set.into_iter().collect();
        assert_eq!(
            order,
            vec![Priority::Low, Priority::High, Priority::Critical]
        );
    }
}

(* Hash, Eq, Ord in OCaml *)

(* Custom ordered type *)
type priority = Low | Medium | High | Critical

let int_of_priority = function
  | Low -> 0 | Medium -> 1 | High -> 2 | Critical -> 3

let compare_priority a b =
  compare (int_of_priority a) (int_of_priority b)

let string_of_priority = function
  | Low -> "Low" | Medium -> "Medium" | High -> "High" | Critical -> "Critical"

type task = {
  name: string;
  priority: priority;
  id: int;
}

let compare_task a b =
  let pc = compare_priority a.priority b.priority in
  if pc <> 0 then -pc  (* Higher priority first *)
  else compare a.name b.name

module TaskMap = Map.Make(struct
  type t = task
  let compare = compare_task
end)

let () =
  let tasks = [
    {name="Fix bug"; priority=Critical; id=1};
    {name="Write docs"; priority=Low; id=2};
    {name="Review PR"; priority=High; id=3};
    {name="Deploy"; priority=High; id=4};
  ] in
  let sorted = List.sort compare_task tasks in
  Printf.printf "Tasks by priority:\n";
  List.iter (fun t ->
    Printf.printf "  [%s] %s\n" (string_of_priority t.priority) t.name
  ) sorted

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_point_eq() {
        let p1 = Point::new(1, 2);
        let p2 = Point::new(1, 2);
        let p3 = Point::new(2, 1);
        assert_eq!(p1, p2);
        assert_ne!(p1, p3);
    }

    #[test]
    fn test_point_hash_map() {
        let map = point_map_example();
        assert_eq!(map.get(&Point::new(0, 0)), Some(&"origin".to_string()));
        assert_eq!(map.get(&Point::new(1, 0)), Some(&"unit-x".to_string()));
    }

    #[test]
    fn test_point_set_dedup() {
        let points = vec![
            Point::new(1, 1),
            Point::new(2, 2),
            Point::new(1, 1), // duplicate
        ];
        let set = point_set_example(points);
        assert_eq!(set.len(), 2);
    }

    #[test]
    fn test_priority_ord() {
        assert!(Priority::Critical > Priority::High);
        assert!(Priority::High > Priority::Medium);
        assert!(Priority::Medium > Priority::Low);
    }

    #[test]
    fn test_priority_sort() {
        let mut priorities = vec![Priority::Medium, Priority::Critical, Priority::Low];
        priorities.sort();
        assert_eq!(
            priorities,
            vec![Priority::Low, Priority::Medium, Priority::Critical]
        );
    }

    #[test]
    fn test_task_sort_by_priority() {
        let mut tasks = vec![
            Task::new("Low task", Priority::Low, 1),
            Task::new("Critical task", Priority::Critical, 2),
        ];
        sort_tasks(&mut tasks);
        assert_eq!(tasks[0].name, "Critical task");
    }

    #[test]
    fn test_task_sort_alphabetical_within_priority() {
        let mut tasks = vec![
            Task::new("Zebra", Priority::High, 1),
            Task::new("Apple", Priority::High, 2),
        ];
        sort_tasks(&mut tasks);
        assert_eq!(tasks[0].name, "Apple");
    }

    #[test]
    fn test_group_by_priority() {
        let tasks = vec![
            Task::new("A", Priority::High, 1),
            Task::new("B", Priority::Low, 2),
            Task::new("C", Priority::High, 3),
        ];
        let groups = group_by_priority(&tasks);
        assert_eq!(
            groups.get(&Priority::High),
            Some(&vec!["A".to_string(), "C".to_string()])
        );
        assert_eq!(groups.get(&Priority::Low), Some(&vec!["B".to_string()]));
    }

    #[test]
    fn test_case_insensitive_eq() {
        let a = CaseInsensitive("Hello".to_string());
        let b = CaseInsensitive("HELLO".to_string());
        let c = CaseInsensitive("hello".to_string());
        assert_eq!(a, b);
        assert_eq!(b, c);
    }

    #[test]
    fn test_case_insensitive_set() {
        let set = case_insensitive_set(vec!["Hello", "HELLO", "World"]);
        assert_eq!(set.len(), 2); // "Hello" and "HELLO" are the same
    }

    #[test]
    fn test_btree_ordered_iteration() {
        let mut set = BTreeSet::new();
        set.insert(Priority::High);
        set.insert(Priority::Low);
        set.insert(Priority::Critical);
        let order: Vec<_> = set.into_iter().collect();
        assert_eq!(
            order,
            vec![Priority::Low, Priority::High, Priority::Critical]
        );
    }
}

Deep Comparison

OCaml vs Rust: Hash, Eq, and Ord Traits

Side-by-Side Code

OCaml — Module-based comparison

type priority = Low | Medium | High | Critical

let int_of_priority = function
  | Low -> 0 | Medium -> 1 | High -> 2 | Critical -> 3

let compare_priority a b =
  compare (int_of_priority a) (int_of_priority b)

module PriorityMap = Map.Make(struct
  type t = priority
  let compare = compare_priority
end)

let () =
  let map = PriorityMap.(empty |> add High "urgent") in
  match PriorityMap.find_opt High map with
  | Some v -> print_endline v
  | None -> ()

Rust — Trait-based comparison

use std::cmp::Ordering;
use std::collections::BTreeMap;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum Priority { Low, Medium, High, Critical }

impl Ord for Priority {
    fn cmp(&self, other: &Self) -> Ordering {
        self.value().cmp(&other.value())
    }
}

impl PartialOrd for Priority {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Priority {
    fn value(&self) -> u8 {
        match self { Self::Low => 0, Self::Medium => 1,
                     Self::High => 2, Self::Critical => 3 }
    }
}

fn main() {
    let mut map = BTreeMap::new();
    map.insert(Priority::High, "urgent");
    println!("{:?}", map.get(&Priority::High));
}

Comparison Table

Aspect	OCaml	Rust
Equality	Structural by default	`PartialEq` / `Eq` traits
Ordering	`compare` function	`PartialOrd` / `Ord` traits
Hashing	`Hashtbl.hash`	`Hash` trait
HashMap key	Any type (structural)	Must impl `Hash + Eq`
BTreeMap key	Needs `compare` via functor	Must impl `Ord`
Derivable	No (write compare manually)	`#[derive(Hash, Eq, Ord)]`

The Trait Hierarchy

PartialEq  →  Eq (total equality, no NaN-like values)
     ↓
PartialOrd →  Ord (total ordering)

• PartialEq: == and !=

• Eq: Marker trait indicating reflexivity (a == a always true)

• PartialOrd: <, <=, >, >=, returns Option<Ordering>

• Ord: Total ordering, returns Ordering directly

Hash Consistency Rule

If you implement Hash, it must be consistent with Eq:

// RULE: a == b implies hash(a) == hash(b)

impl PartialEq for CaseInsensitive {
    fn eq(&self, other: &Self) -> bool {
        self.0.to_lowercase() == other.0.to_lowercase()
    }
}

impl Hash for CaseInsensitive {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Must hash the same thing we compare!
        self.0.to_lowercase().hash(state);
    }
}

5 Takeaways

**#[derive(PartialEq, Eq, Hash)] covers most cases.**

Use derive unless you need custom semantics.

**Ord requires Eq; PartialOrd requires PartialEq.**

The trait hierarchy ensures consistency.

OCaml uses functors; Rust uses trait bounds.

Map.Make(...) vs BTreeMap<K: Ord, V>.

Hash must be consistent with Eq.

Equal values must hash to the same value.

**Ord is for BTreeMap; Hash + Eq is for HashMap.**

Different collections require different traits.

Exercises

Case-insensitive key: Create CaseInsensitiveStr(String) implementing Eq and Hash based on the lowercase version. Use it as a HashMap key and verify that "Foo" and "foo" resolve to the same entry.

Ranked task: Implement a Task { priority: Priority, name: String, id: u64 } with Ord that orders by priority (descending), then name (alphabetical), then id. Use it in a BTreeSet to maintain a sorted task queue.

Law verification: Write property-based tests (or manual tests) that verify the Hash coherence law for your custom type: generate pairs of equal values and assert their hashes are equal, and generate unequal values to estimate the hash distribution.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust