To be more picky, it's the SHA-1 hash of the public key, truncated to 10 bytes, then base 32'd which makes 16 chars. That's only for v2, v3 is a bit different.
And yes, v3 is a huge space. That is, several orders of magnitude larger than the IPv6 space. Which is itself humongous.
Edit: Oops. Got that very wrong. Onion v3 is orders of magnitude greater than IPv6 /64. But orders of magnitude less than IPv6 overall. It's like this, I think.
onion v2: ~1.84×10^19 [16^16]
IPv6 /64: ~1.84×10^19 (which is why OnionCat works)
For anyone curious, v3 is the 32-byte ed25519 pub key, then the first two bytes of the SHA3-256 hash of the key (w/ prepended fixed string and one byte appended), then one more const byte, and then all of those 35 bytes are base 32'd to make 56 chars. Some Go code to illustrate: https://github.com/cretz/bine/blob/f33268f0843a1b2b131a4cacf.... One benefit being that the entire pub key is right there in the hostname.
I'd forgotten that :(
And yes, v3 is a huge space. That is, several orders of magnitude larger than the IPv6 space. Which is itself humongous.
Edit: Oops. Got that very wrong. Onion v3 is orders of magnitude greater than IPv6 /64. But orders of magnitude less than IPv6 overall. It's like this, I think.
onion v2: ~1.84×10^19 [16^16]
IPv6 /64: ~1.84×10^19 (which is why OnionCat works)
onion v3: ~9.35×10^27 [56^16]
all IPv6: ~3.40×10^38