10 ms·

This is one of the reasons why many hashtable implementations introduce a random component into the algorithm. The order of elements changes on every run, so if

This is one of the reasons why many hashtable implementations introduce a random component into the algorithm. The order of elements changes on every run, so if you accidentally rely on the order, it's going to go wrong sooner rather than later. 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.

zarzavat 2y ago
Many implementations these days also go the opposite way, guaranteeing that hash tables always iterate in insertion order. 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.
- mort96 2y ago
  JavaScript is probably the most notable example of that. It used to not have a guaranteed iteration order, but browsers implemented it in such a way that the iteration order was the insertion order, and then that eventually got standardized because websites started depending on it. 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/ https://www.hyrumslaw.com/).
  - aranke 2y ago
    Python also, similar story.
  - pimeys 2y ago
    Rust has HashMap with random order and BTreeMap which is ordered by the key. Additionally one can use IndexMap crate if wanting to keep the order of insertion in the map. The issue with the latter is how much memory it can waste in the worst cases. A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string. 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.
    - masklinn 2y ago
      > A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string. 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).
      - pimeys 2y ago
        We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually. 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.
        masklinn 2y ago
        > We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually. 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.
        SkiFire13 2y ago
        Indexmap does reuse hashbrown. It consists of a hashtable containing `usize` indexes into a `Vec` which in turn contains the actual entries (keys and values), along with a cached hash for the key. In the end the overhead should only be that index and the hash.
        pimeys 2y ago
        It's pretty easy to try out: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=6bfcdc0a94fcbb45cc430ab139a962cb https://play.rust-lang.org/?version=stable&mode=debug&editio... 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.
  - masklinn 2y ago
    Javascript is kinda weird as the numerical keys have their own special ordering. 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.
    - Yoric 2y ago
      I remember that it actually broke a critical algorithm I was testing at the time. Fun times.
    - zbentley 2y ago
      Perl also changed its behavior, but in the other direction: a random seed was used per interpreter start after 5.18. https://www.perlmonks.org/?node_id=1005122 https://www.perlmonks.org/?node_id=1005122
      - masklinn 2y ago
        That's actually the first python transition I mentioned, per-process hash randomisation had the effect of making map iteration non-deterministic. I believe in both cases this was in response to the hashdos concern / attacks.
        zbentley 2y ago
        Ah, sorry I didn't read that closely. 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 https://github.com/rust-lang/rust/issues/16799 2: https://bugs.ruby-lang.org/issues/4579 https://bugs.ruby-lang.org/issues/4579 3: https://wiki.openssl.org/index.php/Random_fork-safety https://wiki.openssl.org/index.php/Random_fork-safety
  - tucnak 2y ago
    [flagged]
    - kortex 2y ago
      It probably started with Zipf's law in the 1930s and then Murphys law a few years later.
    - mort96 2y ago
      Americans? This is using "law" to mean something akin to "scientific law", such as Newton's three laws of motion or Mendel's three laws of inheritance; it's a description of what will happen. People were using "law" in this way since before the USA even was a country lol
  - hu3 2y ago
    PHP too. Its arrays, which also behave like hash maps, respect insertion order. https://www.php.net/manual/en/language.types.array.php https://www.php.net/manual/en/language.types.array.php
- thinkharderdev 2y ago
  Isn't that just a different data structure? How do you preserve insertion order in a hash map?
  - deleted 2y ago
    [deleted]
  - JonChesterfield 2y ago
    Kind of? It usually means you've compromised the data structure somehow but occasionally it shows up incidentally. 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.
  - layer8 2y ago
    > How do you preserve insertion order in a hash map? 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.
    - thinkharderdev 2y ago
      Ah yeah, I've implemented LRU caches this way (hash map with an intrusive linked list overlayed on the values) but didn't put 2 and 2 together :)
    - Sesse__ 2y ago
      > The overhead is rarely critical in practice. Depends; you add two extra pointers for each element, so your int → int hash table balloons in size.
      - layer8 2y ago
- dkersten 2y ago
  > Often if I think I need an unordered map it turns out to be wrong for some subtle reason. 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.
  - zarzavat 2y ago
    As a rule I’m happy to sacrifice cycles for determinism, because non-deterministic bugs are disproportionately wasteful of developer time. 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.
    - saagarjha 2y ago
      Picking a tool without thinking about it is a surefire way to get runtime bugs.
    - dkersten 2y ago
      I agree with sibling commenter. If I need determinism, I choose the deterministic container. If I don’t know whether I need determinism or not, I don’t understand the problem well enough yet. 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.
- anal_reactor 2y ago
  At my previous company my boss made me angry after I already handed in my two weeks notice so I stopped caring, and I wrote code that depended on the insertion order into a map. Of course I didn't document it. Have fun guys.
  - tzot 2y ago
    Your ex-boss made you angry and you left code that will make the life more difficult for whom? Only your ex-boss or more people? Who gets punished for what you perceive as one person's mistake?
    - anal_reactor 2y ago
      It was a company where 80% of employees were interns, I was one of them, the other 20% were people who couldn't get hired elsewhere, with just a handful of those who actually knew what they were doing. There was no leadership. 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".
      - saagarjha 2y ago
        We can expect a lot from you, but I guess you’re always free to let people down.
        anal_reactor 2y ago
        If I counted each time people let down me I'd definitely broaden my vocabulary of huge numbers.
  - CoastalCoder 2y ago
    Vengeful behavior can be gratifying in the short term, but in the long term I've never felt good about it. Maybe you'll find the same.
- IshKebab 2y ago
  > I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map. 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).
  - jlarocco 2y ago
    You can always use a library or roll your own.
- kccqzy 2y ago
  I don't understand this reasoning. If there is a subtle reason wouldn't you take the time to think through it carefully? Are you in such a rush that you don't have time to decide the required data structure (ordered vs unordered)? Or do you have insufficient control of downstream software that you fear for unknown bugs caused by this? And since insertion order is often related to some other ordering in the input, you are comfortable that downstream software completely rely on this ordering even when it's undocumented? Genuinely curious because this kind of reasoning is alien to me.
TacticalCoder 2y ago
> This is one of the reasons why many hashtable implementations introduce a random component into the algorithm. 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.

zarzavat 2y ago

Many implementations these days also go the opposite way, guaranteeing that hash tables always iterate in insertion order. 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.

mort96 2y ago
JavaScript is probably the most notable example of that. It used to not have a guaranteed iteration order, but browsers implemented it in such a way that the iteration order was the insertion order, and then that eventually got standardized because websites started depending on it. 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/ https://www.hyrumslaw.com/).
- aranke 2y ago
  Python also, similar story.
- pimeys 2y ago
  Rust has HashMap with random order and BTreeMap which is ordered by the key. Additionally one can use IndexMap crate if wanting to keep the order of insertion in the map. The issue with the latter is how much memory it can waste in the worst cases. A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string. 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.
  - masklinn 2y ago
    > A good example is the serde_json library, if enabling the ordering of the maps. If you deserialize JSON into its dynamic Value enum, the resulting object can be many times bigger than the original string. 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).
    - pimeys 2y ago
      We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually. 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.
      - masklinn 2y ago
        > We did measure significantly bigger memory usage with IndexMap and needed to revert back to HashMap eventually. 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.
        SkiFire13 2y ago
        Indexmap does reuse hashbrown. It consists of a hashtable containing `usize` indexes into a `Vec` which in turn contains the actual entries (keys and values), along with a cached hash for the key. In the end the overhead should only be that index and the hash.
        pimeys 2y ago
        It's pretty easy to try out: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=6bfcdc0a94fcbb45cc430ab139a962cb https://play.rust-lang.org/?version=stable&mode=debug&editio... 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.
- masklinn 2y ago
  Javascript is kinda weird as the numerical keys have their own special ordering. 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.
  - Yoric 2y ago
    I remember that it actually broke a critical algorithm I was testing at the time. Fun times.
  - zbentley 2y ago
    Perl also changed its behavior, but in the other direction: a random seed was used per interpreter start after 5.18. https://www.perlmonks.org/?node_id=1005122 https://www.perlmonks.org/?node_id=1005122
    - masklinn 2y ago
      That's actually the first python transition I mentioned, per-process hash randomisation had the effect of making map iteration non-deterministic. I believe in both cases this was in response to the hashdos concern / attacks.
      - zbentley 2y ago
        Ah, sorry I didn't read that closely. 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 https://github.com/rust-lang/rust/issues/16799 2: https://bugs.ruby-lang.org/issues/4579 https://bugs.ruby-lang.org/issues/4579 3: https://wiki.openssl.org/index.php/Random_fork-safety https://wiki.openssl.org/index.php/Random_fork-safety
- tucnak 2y ago
  [flagged]
  - kortex 2y ago
    It probably started with Zipf's law in the 1930s and then Murphys law a few years later.
  - mort96 2y ago
    Americans? This is using "law" to mean something akin to "scientific law", such as Newton's three laws of motion or Mendel's three laws of inheritance; it's a description of what will happen. People were using "law" in this way since before the USA even was a country lol
- hu3 2y ago
  PHP too. Its arrays, which also behave like hash maps, respect insertion order. https://www.php.net/manual/en/language.types.array.php https://www.php.net/manual/en/language.types.array.php
thinkharderdev 2y ago
Isn't that just a different data structure? How do you preserve insertion order in a hash map?
- deleted 2y ago
  [deleted]
- JonChesterfield 2y ago
  Kind of? It usually means you've compromised the data structure somehow but occasionally it shows up incidentally. 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.
- layer8 2y ago
  > How do you preserve insertion order in a hash map? 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.
  - thinkharderdev 2y ago
    Ah yeah, I've implemented LRU caches this way (hash map with an intrusive linked list overlayed on the values) but didn't put 2 and 2 together :)
  - Sesse__ 2y ago
    > The overhead is rarely critical in practice. Depends; you add two extra pointers for each element, so your int → int hash table balloons in size.
    - layer8 2y ago
dkersten 2y ago
> Often if I think I need an unordered map it turns out to be wrong for some subtle reason. 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.
- zarzavat 2y ago
  As a rule I’m happy to sacrifice cycles for determinism, because non-deterministic bugs are disproportionately wasteful of developer time. 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.
  - saagarjha 2y ago
    Picking a tool without thinking about it is a surefire way to get runtime bugs.
  - dkersten 2y ago
    I agree with sibling commenter. If I need determinism, I choose the deterministic container. If I don’t know whether I need determinism or not, I don’t understand the problem well enough yet. 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.
anal_reactor 2y ago
At my previous company my boss made me angry after I already handed in my two weeks notice so I stopped caring, and I wrote code that depended on the insertion order into a map. Of course I didn't document it. Have fun guys.
- tzot 2y ago
  Your ex-boss made you angry and you left code that will make the life more difficult for whom? Only your ex-boss or more people? Who gets punished for what you perceive as one person's mistake?
  - anal_reactor 2y ago
    It was a company where 80% of employees were interns, I was one of them, the other 20% were people who couldn't get hired elsewhere, with just a handful of those who actually knew what they were doing. There was no leadership. 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".
    - saagarjha 2y ago
      We can expect a lot from you, but I guess you’re always free to let people down.
      - anal_reactor 2y ago
        If I counted each time people let down me I'd definitely broaden my vocabulary of huge numbers.
- CoastalCoder 2y ago
  Vengeful behavior can be gratifying in the short term, but in the long term I've never felt good about it. Maybe you'll find the same.
IshKebab 2y ago
> I prefer this because it means I don’t have to decide whether I need an ordered map or an unordered map. 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).
- jlarocco 2y ago
  You can always use a library or roll your own.
kccqzy 2y ago
I don't understand this reasoning. If there is a subtle reason wouldn't you take the time to think through it carefully? Are you in such a rush that you don't have time to decide the required data structure (ordered vs unordered)? Or do you have insufficient control of downstream software that you fear for unknown bugs caused by this? And since insertion order is often related to some other ordering in the input, you are comfortable that downstream software completely rely on this ordering even when it's undocumented? Genuinely curious because this kind of reasoning is alien to me.

TacticalCoder 2y ago

> This is one of the reasons why many hashtable implementations introduce a random component into the algorithm. 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.