It also very nicely prevents security issues, since if the hashing algorithm is fixed, it can be exploited for denial of service by coming up with keys that all fall into the same bucket.
I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map. Often if I think I need an unordered map it turns out to be wrong for some subtle reason.
For general purpose hash maps in standard libraries, I think you ought to either randomize the iteration order so that it's different every time, or guarantee an iteration order. Leaving it unspecified but predictable in practice is a recipe to fall victim to Hyrum's Law (https://www.hyrumslaw.com/).
For immutable data that can fit to the CPU cache, utilizing a sorted vector can be many times faster and uses less memory compared to the maps.
Deserialized non-trivial objects are generally larger than the original serialised value.
IndexMap should not generally be significantly larger than a HashMap though, unless the key and value are very small (sub-word).
Deserializing into a defined struct does not waste as much memory as Value does. Especially due to the recursive nature of the Map variant, which can hold another Map.
That is strange and I’d assume the maintainers would be interested in the information.
By my reckoning HashMap would be consuming about capacity * 10/9 * (8 + sizeof key + sizeof value) while indexmap should be consuming capacity * 10/9 * 8 + capacity * (8 + sizeof key + sizeof value).
Unless indexmap reuses hashbrown directly in which case you’d get something like capacity * 10/9 (16 + sizeof key) + capacity * sizeof value.
Now, if you have an enum such as `serde_json::Value` which is kind of recursive with its `Map` variant, and you have a ton of dynamic JSON parsing in your code, these numbers really add up. And serde_json uses `BTreeMap` (I was wrong in my previous message) by default which is even smaller than `HashMap`.
The learning here is to avoid dynamic JSON parsing if you can. And if needing it, but not caring the insertion order, avoid the `preserve_order` feature flag.
The other learning here is that there is no map structure that fits to all purposes. They all have their pros and cons and you should choose the right one for the problem.
Python is probably the better known one, as it went through "arbitrary but deterministic" (before 3.3) to "wilfully non-deterministic" (from 3.3 to 3.6) to "insertion ordered" from 3.6, the latter of which was initially an implementation detail of improving the hashmap but was then made into the language spec starting 3.7.
One minor nit (which the Perl press releases also mess up): the randomisation is per-interpreter, not per-process.
That's not a pedantic distinction. I've seen a couple of bugs/bad behaviors caused by forking servers forgetting to call srand(3)/re-randomize the hash seed after fork(2) and then relying on more randomness than they actually have. Suddenly (for example) hashing rate limiters or bloom filters all operate in near-lockstep, which can cause significant issues at high volumes.
Forking has also caused randomness-related issues (though not necessarily specifically re: hashing) for Rust[1] and Ruby[2], and probably many other platforms. OpenSSL seems to sidestep[3] the issue by using the PID as part of its salt internally.
1: https://github.com/rust-lang/rust/issues/16799
Its arrays, which also behave like hash maps, respect insertion order.
For example, if you append the keys/values to an arena instead of inline in the hash you get a different set of performance tradeoffs. However insertion order is then available by walking the arena.
Appending to an arena in the background is a decent choice for variably sized data, as opposed to heap allocating everything one at a time. That probably has to store the size of each item, hence a forward iterator over the arena at zero cost. Minor quibbles around deleting and tombstones notwithstanding.
You enhance the stored elements to also be the nodes of a doubly linked list. The overhead is rarely critical in practice. It can be made more efficient if the hash map doesn’t need to support deletion.
Depends; you add two extra pointers for each element, so your int → int hash table balloons in size.
If your hash map uses chaining, then you weave an extra doubly linked list through your entries (see OpenJDK's OrderedHashMap, for a pretty readable open source example).
Huh. This hasn’t been my experience. I very rarely need maps to be ordered. In recent years, the only case I can remember is when serializing to TOML and wanting the keys to be written in a specific order. There have been the occasional other case where insertion order is what I wanted, but I almost never need ordering in map keys.
> I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map.
I’m the opposite, I prefer to be given a choice so I can make the tradeoffs when I want to or need to. If you don’t want to choose, you are free to always choose ordered map, but even if ordered map is the default, there should always be a choice to use unordered map. It’s been very rare that I started with the wrong one and had to change.
When I write python or JavaScript I typically don’t care and will just use whatever is the default, but when I write C++, I very much do care and the vast majority of cases use phmap’s flat_hash_map, which has superior space and speed over std::map and std::unordered_map. For ordered maps I use tsl::ordered_map but that still comes at a cost over flat_hash_map and its unordered variants.
As much as possible I want my code to give the same results from one run to the next.
Some sources of non-determinism are unavoidable, but e.g. unordered maps and unstable sorts both have deterministic alternatives that are almost as performant.
Maps are such a common data structure that eliminating unordered maps has a big impact on whole program reproducibility.
Regarding wanting your code to produce the same results from one run to the next, so do I, and I get this by using appropriate data structures. If iterating a map is producing non-deterministic results then I’m doing something wrong, because that means that the order of iteration matters. It’s just that it’s not that common in my code that this is the case. Where I need specific order, more often than not, a list (array/vector) has been a more appropriate structure. Sometimes an ordered map is indeed the correct structure, but ordered map doesn’t by itself give you the determinism you desire, you also need to ensure that the insertion order is itself deterministic and consistent between runs, and that the order is maintained during processing/data manipulation between insertion time and iteration time.
Typically a better approach, in my opinion, is to process the data in whatever form makes sense (eg unordered) and then when you reach a point where order matters, that’s where you sort by the order you require, rather than trying to make sure that you insert in the correct order and don’t lose that order somewhere in the process. Of course it’s valid to think about the steps and say “if I use an ordered map, this set of operations maintains the order, so I can omit the sorting” and that’s a good optimisation, but that should, in my opinion, be a conscious decision based on analysis if the problem, your solution, and your requirements.
I agree that I handled the situation unprofessionally, but I feel excused, considering the circumstances. Whether I'd do it again depends on who'd need to clear up this mess. If it's people I care about because I got to know them - I'd keep my cool. But if it's some abstract "organization" where I was just a random cogwheel with zero connection to other cogwheels, then you can't expect me to care about anything that doesn't include "me".
Maybe you'll find the same.
Well only if you happen to insert your elements in order. If you want a proper ordered map like `std::map` in C++ or `BTreeMap` in Rust then you are out of luck (at least in Python and Javascript).
If the random component is a seed that can be forced/stored/logged/reproduced then it's okay. Otherwise it's actually an horrible idea because it complicates debugging other issues.
Randomness is the enemy, not the friend.
> It also very nicely prevents security issues, since if the hashing algorithm is fixed, it can be exploited for denial of service by coming up with keys that all fall into the same bucket.
Yeah, 20 years ago this was a thing to attack Java webservers: crafting URL with parameters so that they'd all end up in the same bucket. Big denial-of-service one. IIRC PHP webservers suffered from the exact same security issue.
It was fixed by implementing a hash table with a seed and that seed was, of course, under the control of the dev because...
Randomness is the enemy, not the friend.