The two maps differ on one axis that decides everything else: ordering.

HashMap<K, V> — O(1) average lookup, insert and remove. Iteration order is arbitrary and deliberately randomised between runs. Requires K: Hash + Eq.

BTreeMap<K, V> — O(log n) for the same operations. Iteration is always in sorted key order, and it supports range queries: map.range("a".."m"). Requires K: Ord.