The "lists" are actually arrays, so access by index is constant-time. You can build a hashtable on top of that. I'd like to add built-in support for maps at some point, but it's one of a very large number of wishlist items...
The simplest implementation would be a sorted list with binary search for access. Segments create problems though.
I thought of the hashtable, but that means I have to keep the hash-table in RAM. By contrast, the entire capnproto structure itself could be memory mapped, thus not having any RAM constraints.
I'm thinking larger datasets here, large enough where overhead of e.g. JSON becomes a problem with RAM (on mobile devices), but not yet large enough to have to use SQLite.
I might be overthinking it, and could move to SQLite straight away. Just trying to keep my stuff as simple as possible. Conceptually simple, that is. Capnproto is conceptually simple: a tree dumped to disk, allowing on-demand memory mapped access to requested parts.
The capnp structure itself could be a hashtable, and doesn't need to be (entirely) loaded into RAM.
I'm saying you create a capnp list, and then you store elements into the list at position according to their hash -- i.e. how you'd build a hashtable, but the capnp list itself is the backing array.
You would have to do this at write time, of course, and make sure the hashing is consistent between runs.
