Dump hash data into a string using Data::Dumper. Take the resulting string and do s/^(.*?)undef(.*?)$//g. Un-serialize string back into a hash.

It's ugly hackery (two .*? in one regex? Yuk!), may or may not be better than O(n) (depends on how s///g is implemented and your un-serailizing algorithm), and is just generally offensive. Admittedly, I don't know the details, but I'd probably live with a O(n) solution rather than spend time that could be somewhere in between O(1) and O(n**2) (or worse).

----
I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
-- Schemer

Note: All code is untested, unless otherwise stated