Right on. The shard id could be derived from the last few bits of the object id, leaving space for additional entropy in the object id itself.

Edit: you don't need an object id / shard id mapping. Each time you need to locate a shard for an object, you take the last few bits of the object id modulo the number of shards to get your shard id.