It seems to me that you need a simplified hash datastructure, where adding a tuple (hk,he) to the hash stores the he as a new hk in the hash table and makes the entries of both keys into pointers to each other. That structure would in fact be a hash consisting only of keys and pointers to keys.

This hash structure probably would consume considerably less memory space than a full featured perl hash, whilst being maybe even faster at lookup. Maybe it is feasible to set up such a thing via XS and (possibly misusing) perl macros. Looks interesting enough to try it...

update: I've made some meek attempts to cobble together such a thing and wormed myself through macros... but I didn't even scratch the surface, I'm afraid. For such a thing to be possible, a HE should be able to hold a single PV -and nothing more. But AFICS a hash value must be a SV, which means that even for undef hash values, the whole struct sv is allocated. Populating a hash with undef values makes no difference in size to populating it with integers.

Which leads me to think about a huge optimization possibility regarding memory consumption. Why do we need a whole struct SV for empty value fields? Shouldn't they be subject to autovivification?