Using a Map with a non-comparable object

Question

I have Job type, equality is defined as the Job's ID being equal. There should never be two jobs with the same ID. They aren't comparable though, one job isn't more or less than another, only equal or not.

type JobId = JobId of string

[<CustomEquality; NoComparison>]  
type Job = {
    Id: JobId
} with 
    interface System.IEquatable<Job> with 
        member x.Equals y = x.Id = y.Id

type Resource = { 
    Id: string
    Capacity: float
    Usage:  Map<Job,float>
}

The Map needs a comparison though.

1. Why does a Map need a comparison?
2. What structure should I use? (I assume I could use an IDictionary but I'm trying to stay functional.)

Answer 1

Internally, F#'s Map is implemented as a balanced binary tree (specifically, an AVL tree), which requires comparison of its key types to be able to decide where in the tree any item belongs. For a hash map that does not require comparison, the PersistentHashMap type from FSharpx.Collections is probably what you want.