If you haven't heard, libJudy from http://judy.sourceforge.net/ is really spiff, tiny and fast. I've got a module Judy::* which provides a perl API to it.
While I don't use this interface myself because tie() is ungodly slow, here, it's available. I figure to publish a version to CPAN soonish. It's newer on http://github.com/jbenjore/judy-hs/tree/master
Here's a cheap sample. It's an incredibly concise bit vector.
tie %vector, 'Judy::1'
Here's more. It's a HoHoH on the outside but really a Word->Word->Bits map on the inside.
tie %hohoh, Judy => 'L -> L -> 1'