This was not the case in my benchmarks: the Rust spent 60% of its time doing regex matches, 25% allocating strings and less than 6% manipulating the map.

Not criticizing, just curious.

http://doc.rust-lang.org/std/collections/

    Use a HashMap when:
    
    - You want to associate arbitrary keys with an arbitrary value.
    - You want a cache.
    - You want a map, with no extra functionality.
    
    Use a BTreeMap when:
    
    - You're interested in what the smallest or largest key-value pair is.
    - You want to find the largest or smallest key that is smaller or larger
      than something
    - You want to be able to get all of the entries in order on-demand.
    - You want a sorted map.

I’ve updated the code and article with HashMap. It runs about 6~7% faster than BTreeMap.

B-trees are especially bad for string keys, because comparisons are expensive.

EDIT: From Rust docs: "Currently, our implementation simply performs naive linear search. This provides excellent performance on small nodes of elements which are cheap to compare". (emphasis mine)

http://doc.rust-lang.org/std/collections/struct.BTreeMap.htm...

I think the example used in the docs is your exact use case.

This bit:

  let found = match map.get_mut(..) {
    ..
  }
  if !found {
    ..
  }

  match map.entry(word) {
      Occupied(mut view) => { *view.get_mut() += 1; }
      Vacant(view) => { view.insert(1); }
  }