swapping two entries of a HashMap

Question

i have a simple HashMap; say HashMap<char, char>.

is there a way to swap two elements in this hashmap using std::mem::swap (or any other method)?

Of course there is the simple way getting the values with get and then replace them with insert - but that would trigger the hasher twice (once for getting then for inserting) and i was looking for a way to side-step the second hasher invocation (more out of curiosity than for performance).

what i tried is this (in several versions; none of which worked - and as remarked in the comments: entry would not do what i expect even if i got this past the compiler):

use std::collections::HashMap;
use std::mem::swap;

let mut hash_map: HashMap<char, char> = HashMap::default();
hash_map.insert('A', 'Z');
hash_map.insert('B', 'Y');

swap(&mut hash_map.entry('A'), &mut hash_map.entry('B'));

now the compiler complains (an i understand why it should)

error[E0499]: cannot borrow `hash_map` as mutable more than once at a time
   --> tests.rs:103:42
    |
103 |      swap(&mut hash_map.entry('A'), &mut hash_map.entry('B'));
    |      ----      --------                  ^^^^^^^^ second mutable borrow occurs here
    |      |         |
    |      |         first mutable borrow occurs here
    |      first borrow later used by call

also just getting the two values this way fails in more or less the same way:

let mut a_val = hash_map.get_mut(&'A').expect("failed to get A value");
let mut b_val = hash_map.get_mut(&'B').expect("failed to get B value");
swap(&mut a_val, &mut b_val);

is there a way to simply swap two entries of a HashMap?

Flounce

entry() method creates instance of Entry{} which contains the references of key and value. Doing a mem swap on these two instance in the enclosing scope might not do any effect. – Algia

@ÖmerErden oh, you are correct. but get returns a reference according to the doc. any idea how i could swap those elements? – Flounce

can you say why you want swap two values of a hashmap ? what is the algorithm ? We are curious. – Uvula

@Uvula as an exercise i am converting a demo i had previously made in python to rust. the demo shows how to attack a substitution cipher with simulated annealing. the key for the cipher is a hashmap (the substitution table) and i need to be able to swap elements. – Flounce

Answer 1

I can't see any safe way to do it:

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert('A', 'Z');
    map.insert('B', 'Y');

    let a = map.get_mut(&'A').unwrap() as *mut char;
    let b = map.get_mut(&'B').unwrap() as *mut char;
    unsafe {
        std::ptr::swap(a, b);
    }

    assert_eq!(map.get(&'A'), Some(&'Y'));
    assert_eq!(map.get(&'B'), Some(&'Z'));
}

Zackzackariah

ha, just came up with the same code (while comparing with the source of slice::swap). thanks! – Flounce

if this is safe I don't see why it doesn't exist in the std – Uvula

@Uvula i do not think that this is used very often... (but i may be wrong). – Flounce

Answer 2

There is one completely safe way I can think of to do this safely, but it's super inefficient: what you want is to get two &mut values, which means borrowck needs to know they're nonoverlapping. Missing a builtin along the lines of split_mut (or the collection being handled specially), the only way I see is to mutably iterate the entire collection, keep refs to the items you're interested in, and swap that:

    let mut h = HashMap::new();
    h.insert("a", "a");
    h.insert("b", "b");

    let mut it = h.iter_mut();
    let e0 = it.next().unwrap();
    let e1 = it.next().unwrap();
    std::mem::swap(e0.1, e1.1);
    println!("{:?}", h);

It requires a linear traversal of the map until you've found the entries whose values you want to swap though. So even though this has the advantage of not hashing at all edwardw's is answer is probably more practical.

Abundant

thanks for your answer! but yes, linear transversal is what you want to avoid when working with hashmaps. – Flounce

Note that there is not way to implement the mutable iterator purely with safe code, for the same reason: The borrow checker can't figure out that the mutable references the next() method is handing out are all non-overlapping. So this "solution" leverages the unsafe code from the mutable iterator implementation to get the two mutable references with safe code. – Sexcentenary

@SvenMarnach that is technically true, but AFAIK the unsafe code within safe stdlib APIs is never taken in account when looking at the "unsafeness" of a codebase, otherwise there would be no "safe rust" codebase as almost everything ultimately ends up in syscalls (unsafe) or raw pointers (also unsafe). – Abundant

I didn't mean to contradict anything you said. I just meant to add some context. You are perfectly right, using safe APIs is safe code. – Sexcentenary

I only used the scare quotes for "solution" since I don't think this answer actually solves anything, as you note yourself. :) – Sexcentenary

Technically it does solve the problem, inefficiently, inconveniently and verbosely. – Abundant

@Abundant good solution also your answer might be more safe with the code like this: play.rust-lang.org/…, but this triggers hasher for n time, which OP wants to avoid triggering(that's the reason why OP wants to use mem::swap) – Algia