It's as easy as a drop-in replacement for the std HashMap and HashSet implementation but i uses a faster hashing algorithm. The difference can be quite substantial.
A hashtable is fundamentally just "how do we fit bigger indexes into a smaller vec", though. So a hashtable -- of some sort -- is absolutely the correct thing for this situation.
Of course, that's what I've been suggesting since the start, it's just that there's no need to actually hash the index because it is just a number, not a string which needs to be converted to a number, not a struct or enum or whatever, so it can be just passed through. The hasher in a hashtable will procure a u64 and therefore std::mem::size_of::<usize>() <= std::mem::size_of::<u64>()
This looks like an opportunity to promote my crate RleVec. It provides a Vec-like interface but uses run length encoding to store the data. There is an O(log n) lookup price though.
You can use my sivec crate. You probably shouldn't: it's pretty untested, full of unsafe code, and likely pretty slow. But you could.
This crate provides a SIVec "self-initializing vector" type that retains indices and has O(1) initialization and O(1) access. On the other hand it's gross to use (because IndexMut is just not a good fit for this and other indexing problems) and uses address space proportional to the maximum index.