PersistentHashMap

A Map is a collection that maps keys to values. Hash maps require keys that correctly support GetHashCode and Equals. Hash maps provide fast access (log32N hops). count is O(1). More details can be found in the API docs.

open FSharpx.Collections

// Create a new HashMap and add some items to it
let m = 
    PersistentHashMap.empty 
    |> PersistentHashMap.add 42 "hello"
    |> PersistentHashMap.add 99 "world"

seq [(99, "world"); (42, "hello")]

// lookup some items
PersistentHashMap.find 42 m

"hello"

PersistentHashMap.find 99 m

"world"

m.[99]

"world"

// Check no. of elements in the HashMap
PersistentHashMap.length m

2

PersistentHashMaps are immutable and therefor allow to create new version without destruction of the old ones.

let m' = 
    m 
    |> PersistentHashMap.add 104 "!" 
    |> PersistentHashMap.add 42 "hi" // replace existing value

PersistentHashMap.find 42 m'

"hi"

PersistentHashMap.find 104 m'

"!"

PersistentHashMap.find 42 m

"hello"

PersistentHashMap.length m

2

PersistentHashMap.length m'

3

// remove an element
let m'' = 
    m' |> PersistentHashMap.remove 104

PersistentHashMap.length m''

2

There a couple of interesting operations on HashMaps:

// Convert a sequence of key value pairs to a HashMap
let stringBasedMap = 
    PersistentHashMap.ofSeq [("a",1); ("b",2); ("c",3); ("d",4); ("e",5)]

seq [("e", 5); ("a", 1); ("b", 2); ("c", 3); ...]

// Square all values in a HashMap
let stringBasedMap' = 
    PersistentHashMap.map (fun x -> x * x) stringBasedMap
stringBasedMap'.["d"]

16

Using from C#

A Map is a collection that maps keys to values. Hash maps require keys that correctly support GetHashCode and Equals. Hash maps provide fast access (log32N hops). Count is O(1).

// Create an empty PersistentHashMap and add some elements
PersistentHashMap<int,string> map =
    PersistentHashMap<int, string>.Empty()
        .Add(42,"hello")
        .Add(99, "world");

Console.WriteLine(map[42]); // hello
Console.WriteLine(map[99]); // world

// Check no. of elements in the PersistentHashMap
Console.WriteLine(map.Length);  // 2

PersistentHashMaps are immutable and therefor allow to create new version without destruction of the old ones.

PersistentHashMap<int, string> map2 = 
    map
     .Add(104, "!")
     .Add(42, "hi");  // replace existing value

Console.WriteLine(map2[42]); // hi
Console.WriteLine(map[42]);  // hello            

Console.WriteLine(map.Length);  // 2
Console.WriteLine(map2.Length); // 3

// remove the last element from a PersistentHashMap
PersistentHashMap<int, string> map3 = map2.Remove(104);

Console.WriteLine(map3.Length); // 2

Performance Tests

Bulk operations on HashMaps use an internal TransientHashMap in order to get much better performance. The following scripts shows this:

open FSharpx.Collections

let trials = 5
let r = new System.Random()

let initFSharpMapAndPersistentMapFromList n =
    sprintf "Init with n = %d" n |> printInFsiTags
    
    let list = List.sortBy snd [for i in 1..n -> i,r.Next().ToString()]

    averageTime trials "  FSharp.Map.ofSeq" 
        (fun () -> Map.ofSeq list)

    let initPersistentHashMap list = 
        let m = ref PersistentHashMap.empty
        for (key,value) in list do
            m := PersistentHashMap.add key value !m
        !m

    averageTime trials "  Multiple PersistentHashMap.add" 
        (fun () -> initPersistentHashMap list)

    averageTime trials "  PersistentHashMap.ofSeq" 
        (fun () -> PersistentHashMap.ofSeq list)

    let initImmutableDictionary list = 
        let d = ref (System.Collections.Immutable.ImmutableDictionary<int,string>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  Multiple ImmutableDictionay.add" 
        (fun () -> initImmutableDictionary list)

    let initImmutableDictionary list = 
        let d = ref (System.Collections.Immutable.ImmutableSortedDictionary<int,string>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  Multiple ImmutableSortedDictionay.add" 
        (fun () -> initImmutableDictionary list)

let lookupInFSharpMapAndPersistentMap n count =
    sprintf "%d Lookups in size n = %d" count n |> printInFsiTags
    let list = [for i in 0..n-1 -> i.ToString(),r.Next()]
    let fsharpMap = Map.ofSeq list
    let map = PersistentHashMap.ofSeq list

    averageTime trials "  FSharp.Map" 
        (fun () -> for i in 1..count do fsharpMap.[r.Next(n).ToString()])

    averageTime trials "  PersistentHashMap" 
        (fun () -> for i in 1..count do map.[r.Next(n).ToString()])

    let dict =
        let d = ref (System.Collections.Immutable.ImmutableDictionary<string,int>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  ImmutableDictionay" 
        (fun () -> for i in 1..count do dict.[r.Next(n).ToString()])

    let dict' =
        let d = ref (System.Collections.Immutable.ImmutableSortedDictionary<string,int>.Empty)
        for (key,value) in list do
            d := (!d).Add(key,value)
        !d

    averageTime trials "  ImmutableSortedDictionay" 
        (fun () -> for i in 1..count do dict'.[r.Next(n).ToString()])

initFSharpMapAndPersistentMapFromList 10000
initFSharpMapAndPersistentMapFromList 100000
initFSharpMapAndPersistentMapFromList 1000000

[fsi:Init with n = 10000]
 [fsi:  FSharp.Map.ofSeq 6.4ms]
 [fsi:  Multiple PersistentHashMap.add 10.6ms]
 [fsi:  PersistentHashMap.ofSeq 10.4ms]
 [fsi:  Multiple ImmutableDictionay.add 22.6ms]
 [fsi:  Multiple ImmutableSortedDictionay.add 18.8ms]
 [fsi:Init with n = 100000]
 [fsi:  FSharp.Map.ofSeq 140.8ms]
 [fsi:  Multiple PersistentHashMap.add 184.4ms]
 [fsi:  PersistentHashMap.ofSeq 128.2ms]
 [fsi:  Multiple ImmutableDictionay.add 253.0ms]
 [fsi:  Multiple ImmutableSortedDictionay.add 174.4ms]
 [fsi:Init with n = 1000000]
 [fsi:  FSharp.Map.ofSeq 2798.2ms]
 [fsi:  Multiple PersistentHashMap.add 3459.0ms]
 [fsi:  PersistentHashMap.ofSeq 3071.0ms]
 [fsi:  Multiple ImmutableDictionay.add 4585.0ms]
 [fsi:  Multiple ImmutableSortedDictionay.add 3240.0ms]

lookupInFSharpMapAndPersistentMap 10000 10000
lookupInFSharpMapAndPersistentMap 100000 10000
lookupInFSharpMapAndPersistentMap 1000000 10000

[fsi:10000 Lookups in size n = 10000]
 [fsi:  FSharp.Map 3.0ms]
 [fsi:  PersistentHashMap 2.0ms]
 [fsi:  ImmutableDictionay 2.2ms]
 [fsi:  ImmutableSortedDictionay 12.0ms]
 [fsi:10000 Lookups in size n = 100000]
 [fsi:  FSharp.Map 4.8ms]
 [fsi:  PersistentHashMap 3.4ms]
 [fsi:  ImmutableDictionay 2.8ms]
 [fsi:  ImmutableSortedDictionay 15.2ms]
 [fsi:10000 Lookups in size n = 1000000]
 [fsi:  FSharp.Map 9.4ms]
 [fsi:  PersistentHashMap 6.0ms]
 [fsi:  ImmutableDictionay 6.4ms]
 [fsi:  ImmutableSortedDictionay 23.6ms]