3 ms·
In my opinion, a hash map that needs to chase an extra pointer to do a lookup and uses insertion order to provide deterministic iteration order seems like a has
by pclmulqdq 5y ago
In my opinion, a hash map that needs to chase an extra pointer to do a lookup and uses insertion order to provide deterministic iteration order seems like a hash map that hates me. Using keys that aren't strings is also table stakes for hash tables these days.
If your desire is only deterministic iteration, just use a hash function that gives that to you. Many libraries randomize this in tests so you don't rely on it, but you can always set a custom hash function. This will give you a much faster happy path than something like this structure.
- glangdale 5y agoThank you. I think that the idea that a hash map that doesn't provide insertion order "hates me" is a bit overblown. Not that this isn't occasionally what you want, but that feels like an exotic new data structure, not that the original hash map is somehow wrong and user-hostile.
- comex 5y ago> If your desire is only deterministic iteration, just use a hash function that gives that to you. For one thing, even with a deterministic hash function, the keys still have to be hashable in some deterministic way - no using pointer values as hash codes. Making objects properly hashable is always possible to do, but in many languages it requires additional work, so people often don’t bother, at the cost of nondeterminism. Insertion-order maps make determinism ‘just work’. Even assuming you do have a deterministically hashable objects and a deterministic hash function, then sure, the map is deterministic in the sense that starting from an empty map and performing the exact same series of operations gives you the same iteration order. If you run the same program on the same inputs, you should get the same output. And often that is all you need. But sometimes you want one part of the program to be deterministic even if another part is changing, and nicely-behaved hash maps can make that easier. For example: both insertion-order maps and sorted maps, but not standard hash maps even with a deterministic hash function, share the property that adding a new element won’t change the relative order of two existing elements. If you’re mutating one part of a map and not another part, yet the latter part is changing order anyway, in some sense that part of the map is behaving nondeterministically. Similarly, they both share the property that a map->list->map round trip, or map->string->map round trip, results in an indistinguishable map. So it’s easier to guarantee that a program behaves deterministically even if you sometimes need to (nondeterministically) pause it, serialize its state to disk, and reload it later.
- masklinn 5y ago> In my opinion, a hash map that needs to chase an extra pointer to do a lookup and uses insertion order to provide deterministic iteration order seems like a hash map that hates me. In most cases it's the other way around: Python switched to compact hash map for performance reasons, the natural ordering was a side-effect of it: * The compact hashmap scheme has much better memory behaviour (as befits its name) because the the storage buffer is contiguous instead of being sparse so less space is wasted on empty cells, this is especially important in a language like Python where everything is a reference and each entry is 24 bytes * It can also be further optimised by making the indices in the array adaptive (Pypy does that though I don't think CPython does): if you have less than 255 entries (which is rather common especially in languages where most everything is a dict — again python) you can use an array of u8s instead of usize. * Finally the primary purpose of the compact hashmap for Python was iteration speed: in a normal hashmap unless you have a very high load factor the map is full of holes iteration needs to skip over, and furthermore the hole locations are basically random so the branch is completely impredictable, even with tombstoning the compact dict has a much better predictability.
- pclmulqdq 5y agoI suppose that most people don't ever erase anything from a Python dictionary? Erasing items would lower the effective load factor of the array (or be O(n) so you can do a big memcpy). It's interesting that this highlights how Python users use dictionaries very differently from how I use hash tables (as a C and C++ programmer). In the last few years, people have been designing hash tables to run at much higher load factors, but if the decision was made before ~2018, I can see why the iteration speed argument would result in a structure like this.
- masklinn 5y ago> I suppose that most people don't ever erase anything from a Python dictionary? It's the tombstoning mentioned in both my comment and the essay (tombstoning is basically the amortisation of deletion), however you need a lot of deletion to fuck up your branching as much as a middling-load-factor hashmap does. > Erasing items would lower the effective load factor of the array (or be O(n) so you can do a big memcpy). It will, however: * maps which get items deleted from are a minority, more so for those which both get items deleted from and get iterated * once enough items have been deleted, the buffer can be shrunk in order to remove the tombstones (converting it back to a very dense array).