13 ms·

An efficient way to make hash maps with insertion ordering

118 points by eatonphil 5y ago

ecshafer 5y ago
This is a weird article. It creates the idea that hash maps are uncommon? surprising? I am not really sure. Then makes the claim that you would expect them to be ordered by insertion order, and not just randomly which is the common usage of hash maps. Ordered Hash Maps exist, and isn't a insertion order hash map, basically just a list? But Hash Maps are so common and used absolutely everywhere its almost like its aiming at people who have used them but never any other data structures.
- EamonnMR 5y ago
  When I was first taught Java in college I didn't find out about hash maps for a while because it was considered too advanced for beginners (ohh scary templates!)
  - myphs 5y ago
    This is quite interesting. I wonder, why this was decided to be too advanced. In my uni we teach it from the very beginning.
- pydry 5y ago
  Python switching all dicts to being ordered is my favorite new feature from the last five years. It's useful all over the damn place.
- rob74 5y ago
  Hash maps are a fairly recent addition to the standard data structures "library", because they are relatively performance-intensive. They are of course very useful and therefore commonplace now, but I think that only came about after the rise of dynamic languages which have built-in hash maps (Javascript objects, PHP "associative arrays" etc.). So nowadays any new programming language which wants to attract web developers (e.g. Go) needs a built-in hash map.
  - mypalmike 5y ago
    Hash maps have been commonly used in C since just about forever. "isn't a insertion order hash map, basically just a list?" No. They are different in the computational complexity of random access operations.
    - benibela 5y ago
      But the standard C++ std::unordered_map only came with C++11
  - boardwaalk 5y ago
    Ehh, hash tables were invented in the 50s and were and are used wherever they are useful. I’m pretty sure a running joke is that every decently sized C program contains a half dozen hash table implementations. They’re not recent.
chris_st 5y ago
The surprising/interesting thing about this article is the notion that insertion order is the order that you want to iterate through a hash map. In my experience, I'm doing either (A) using them as associative memory (I want the value for a key) and I don't ever iterate, or (B) I don't care about order when I iterate (I'm summing values, say) or (C) I want the keys in some sorted order, that probably has nothing whatsoever to do with insertion order (counting keywords, then showing them in alphabetical order). So I'm curious why the insertion order is preferred, in your experience.
- macspoofing 5y ago
  >So I'm curious why the insertion order is preferred, in your experience. It's a little bit like asking what's the use of a linked list. A map which can iterate through keys in insertion order is just a data structure. A recent use-case for me was using timestamps as keys that map to captured state at that time.
  - recursive 5y ago
    > A recent use-case for me was using timestamps as keys that map to captured state at that time. That sounds like sorted key order would suffice just fine.
  - chris_st 5y ago
    > * It's a little bit like asking what's the use of a linked list.* Well, no, it's more like asking why you'd use data structure X instead of Y. I was asking why you'd want that property as part of your data structure, and pointing out that (AFAIR) I've never needed it. For your use case, I guess you wanted to be able to retrieve the data for specific time stamps? Otherwise I'd think you'd just put it into an array.
- __s 5y ago
  A result of insertion order is that when I print {b:2,a:1} I get "{b:2,a:1}". This can be nice for being able to store something like an HTML element's attributes as a dictionary while still serializing it back to the order it was declared with Sorted order also requires sortable keys-- not something that's required when hash maps only require hashing & equality A stable ordering is nice, without the ability to sort insertion order meets this ask. https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... shows how in Python this useful property also comes as a side effect of an optimization
noneeeed 5y ago
Curious to read this and not see a reference to Ruby. In Ruby hashes are ordered by insertion, can have any object as keys, but the hash key value can be defined on a class by class basis (by overriding the default `hash` method on the class). The ordering is one of those features that I need very infrequently, but when I do it significantly simplifies that bit of code. I've always found the usefulness and flexibilty of Ruby's hashes to be a double-edged sword though: they are extremely useful, but this leads people to use them in situations where defining a proper class might be better for long-term maintenance.
- weatherlight 5y ago
  I've used this feature of Ruby Hashes to create something that behaves like a a LRU cache :)
  - noneeeed 5y ago
    Interesting, I'm trying to work out how that would work. Would you mind giving a quick overview?
jerf 5y ago
"The other feature you quickly find yourself needing is the ability to use arbitrary objects as keys in a hash map. In languages that don’t support that (Perl, Python, Go, JavaScript until recently)" I don't think that's right. Python and Go do effectively support that. Each has their own take on the problem of being unable to use mutable keys, but I index by some sort of object all the time. Makes iteration over hashes substantially more useful when you get objects for both hashes and keys. Back in the Python 2.0 era, before it grew all the other features that were advantages over Perl, before Python even had generators/iterators, this was one of the big reasons I preferred Python over Perl. Only being able to index by strings wasn't necessarily a huge stopper in theory, but in practice it was very dangerous, because you really need to encode your keys. It was extremely common to see print($hash{$keyPart1 . "|" . $keyPart2}); when what you need is print($hash{pipeEncode($keyPart1) . "|" . pipeEncode($keyPart2)}); to be safe, where pipeEncode can be as simple as a routine to backslash encode pipe and backslash characters (although no simpler than that; you must do both of them to be safe, that's the minimum). This could result in non-trivial bugs and even security issues when you start encoding things like $object . "|" $permission and hackers start sticking pipes in the names of objects. But between the inconvenience of that if you know what you're doing, and the pile of code you'll encounter from developers who don't know why that's important (and may even argue in code review), it was definitely the sort of thing that grinds you down over time. In Python it was safe to print(hash[(keyPart1, keyPart2)]) and it was consistent and safe. Or use an object, etc.
- nemo1618 5y ago
  Go does not support using some types as map keys, including slices, channels, functions, and other maps. Slices are the most annoying, and I have seen plenty of code that uses fmt.Sprint(s) as a workaround. Fortunately the compiler now recognizes when you convert a []byte to a string for use as a map key, and will not allocate a new string.
  - arp242 5y ago
    In Go it depends if the type is "comparable"; i.e. if "==" works. You can use arrays in Go; e.g. map[[2]int]string, and you can also use channels; although I'm not sure what the rules for comparing channels are exactly off-hand (I'm struggling to come up with a scenario when this would be useful off-hand actually). The big problem with slices and maps is that they can be modified. That is, what happens if you modify a slice after you used it as a map key? In slices this is worse than with maps because the backing array can change if you run out of cap space. And also, do you compare by value or identity? And again, what happens if either changes? I'm not sure if it's possible to come up with a set of rules that wouldn't take people by surprise in at least some cases.
bullen 5y ago
I wish JavaScript had linked hash maps as default so that JSON would not require arrays to keep the order of objects! Hierarchies would not have to look like this: http://root.rupy.se/meta/user/task/563541707719927980 http://root.rupy.se/meta/user/task/563541707719927980
- ajanuary 5y ago
  Javascript already does retain insertion order (except for special casing of things like integer keys) JSON objects, however, have unordered keys. JSON != Javascript.
arsome 5y ago
Is there a proper way to use custom objects as keys in hashmaps in JS (well, ideally TypeScript compliant)? Coming out of the C++ world where this is trivial and something I use quite often this seems pretty infuriating. Maybe a general data structure package that's worth pulling in? EDIT: After doing a bit of research I found "tstl", looks interesting, their hashmap appears to support custom hashers and equality comparisons: https://tstl.dev/api/classes/std.hashmap.html https://tstl.dev/api/classes/std.hashmap.html I'm curious about experiences with it if anyone's had the chance?
- upzylon 5y ago
  If the problem is just that you want to use non-primitive keys, that's what Maps are for. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
  - arsome 5y ago
    I'm aware of them, but the problem with that is you can only compare an object by instance if I recall correctly. There's no way to override the hashing and equality check that I could find, meaning even for simple objects you're basically forced to serialize your keys in some way still, which is disgustingly inefficient and slow for no good reason.
    - doteka 5y ago
      So much this. I remember being so excited that Map and Set were added to the language, only to find that they were worse than useless for objects. At least Set can be handy in a pinch, but I have never seen an actual usecase for Map that isn’t solved better with plain old JS objects. Curious if anyone else has?
      - upzylon 5y ago
        There definitely are valid use cases for a Map, and even more now that we have WeakMaps (e.g. associating data DOM nodes). Or mapping functions to values, e.g. something like this: const returnCache = new Map<() => any, any>() const memoized = <T extends () => any>(f: T): ReturnType<T> => { if (returnCache.has(f)) return returnCache.get(f) const v = f() returnCache.set(f, v) return v }
peterkelly 5y ago
Rust has HashMap and BTreeMap. You use the latter when you care about ordering. There's also a couple of options for dequeues. A good overview here explaining which one you'd choose depending on what oyu want to do: https://doc.rust-lang.org/std/collections/index.html https://doc.rust-lang.org/std/collections/index.html Use the right data structure for the job. Maps are an interface, not an implementation.
- floitsch 5y ago
  Rust has hash maps that hate you. The default hash map visits the keys in arbitrary order (https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.keys https://doc.rust-lang.org/std/collections/struct.HashMap.htm...). You could use a BTreeMap, but that's not insertion order and requires the user to come up with some sort of ordering.
  - IshKebab 5y ago
    They don't hate you. That's how it's supposed to work. Otherwise you get issues like the one discovered in the article. Would you say Rust has Vecs that hate you because prepend isn't O(1)? Or does JavaScript have Maps that hate you because they aren't sorted? There's no perfect container. It's all trade-offs.
    - ErikCorry 5y ago
      The article also explains how the issue discovered can be fixed. And JS maps are insertion ordered.
      - c-cube 5y ago
        The article doesn't expand much on the performance cost. Another comment mentions Swiss tables, which are what rust HashMap is based on these days, and it's unlikely that python's maps are as optimised. Not to mention the unavoidable memory overhead.
        5y ago
adrianmonk 5y ago
Having hashmaps be ordered is not always desirable. It's not necessarily meaningful for every application[1]. Also, it can have overhead. If the problem is that the developer doesn't get what they expect, often the solution is to require the developer to be explicit about what they ask for. I think that could work well here. Instead of having map.keys(), the API could have map.orderedKeys() and map.unorderedKeys(). (Or make it okeys() and ukeys() to be more concise.) Yes, it's slightly more typing, but to me that's a small price to pay to ensure you get what you want. --- [1] For example, maybe the order that's meaningful to me has something to do with the values rather than the keys. If the map represents git commits, maybe the order that's meaningful to me is a topological sort, and the map isn't going to provide that.
- stickfigure 5y ago
  This would be genuinely weird. The in-memory representation will make one or the other approach more efficient. If you want ordered, pick an ordered implementation (eg Java's LinkedHashMap). If you don't care, pick an implementation that doesn't care (eg HashMap). If you want some special ordering, pick something that can use a Comparator (eg TreeMap) or just sort the data when fetching. A Frankenstein LinkedRandomTreeMap would pay the overhead of all approaches for an extremely exotic use case.
  - adrianmonk 5y ago
    I suppose these ideas can be combined. An implementation that doesn't support ordering could be of a type that only has an unorderedKeys() and lacks orderedKeys(). Which is more explicit than having a keys() function that behaves differently than other types' keys() functions. Also, I guess you could define unorderedKeys() to mean "I'm not picky about the order" (rather than "it must not be ordered"). Then all types could have an unorderedKeys() function.
    - stickfigure 5y ago
      If unrderedKeys() isn't picky about the order, then there's no reason to have a separate method. Just keys() will do, and different implementations can have different behavior. Also note that relaxing the ordering requirement when obtaining keys does not necessarily improve performance; if you've already done the work of maintaining an ordered list (ie LinkedHashMap), it's actually faster to iterate in order. Furthermore, what exactly does orderedKeys() mean anyway? Insertion order? Does reinsertion change order? If some sort of natural ordering (eg, topological) then how do you configure that? I think the "state of the art" is basically correct here: An abstract Map interface that provides basic operations, and a variety of implementations all with different behaviors and performance profiles. Sorry.
usefulcat 5y ago
First off, WTF is up with disabling copying? That is seriously annoying. Now on to what I came here to say.. "When there are enough of these tombstones, the hash map gets rebuilt, but that’s OK. Due to the magic of amortized constant time, this doesn’t slow you down on average." If amortized time is all you care about, that's fine. But there are some applications where worst case time is more important, and unfortunately I've seen some hash map implementations that implicitly assume that the worst case never matters.
- prutschman 5y ago
  In some browsers you can get around this by selecting the text, keeping the mouse button down, hitting the keyboard shortcut for 'copy', then letting go. The selection will still be emptied, but the text is already in your clipboard.
AtlasBarfed 5y ago
Java is treated as the "prior art" like it is some sort of ancient script? That is amusing. Since Java was the first mainstream GC language with sufficient man-hours of engineering, and it was an opportunity after almost two decades of C/C++ libraries to start anew with the standard library, but its standard library always seemed simply evolutionary/"best practice" (not my favorite phrase, sorry) from what came before it. Is the hashmap impl in the JDK actually novel for its time? But
- ErikCorry 5y ago
  As I understood it, there was an implementation of "compact dictionaries" in Java, but it was not the implementation of any of the collections that were built into the language. It is "prior art" in that it was done before compact dictionaries were reinvented for Python.
  - abecedarius 5y ago
    IIRC it was for the collections library of the E language, whose first implementation was in Java (erights.org). The E designers had a self-imposed constraint that everything computational had to be deterministic. The standard way of doing iterable hashtables lacked this property. I tried to check my memory by following the link to the Raymond Hettinger talk, but he doesn't say just what prior work he was talking about, only that it was in Java.
    - cb321 5y ago
      "An Efficient Representation for Sparse Sets" by Preston Briggs & Linda Torczon dates from Rice in 1993 covers the case where the index can be a direct map (for small key universes - like, say, the range of `char` or `short`, where one can be sure of no collisions/need to handle them). The idea is simple enough that it could have been a subsection in some seminal early database work, but I also lack a reference for that. Storing some (or all) of the hash code in the hash index part as this article mentions is a good idea I had independently. This is especially true if you do linear probing on the hash table part and care about worst case latencies. (You will basically never have > 2 full cache misses if the CPU BP/prefetcher can recognize a linear scan.)
patrickthebold 5y ago
This reminds me of one bug I introduced a long time ago: This was a node backend, and there was some code that was recreating an object be reinserting all the key value pairs in a precise order so that that's how it would serialize in the json and then the UI depended on that order. But to me, it was just recreating the same object so I deleted that code, causing the bug. In retrospect, I should have at least asked the committer what they were trying to do. In my defense, this was before javascript guaranteed the insertion order would be the order kept.
dragontamer 5y ago
There's all sorts of application-specific assumptions in this post, that it isn't funny. Ex: Use of hash-tables with insertion ordering to handle a insert-once task queue (preventing "double tasking" if a task is ever somehow inserted twice?) Solvable with a Linked-list, circular buffer queue + hash table combined together (hash-table to prevent double-insertions. Linked-list / circular buffer queue for the FIFO functionality). If O(log(n)) insert/removes are sufficient and you have priorities associated with each element, a Heap data-structure works (all "repeats" will be next to each other, because max-heaps always keep the maximum element on the top) The goal isn't supposed to be to make a data-structure that magically works in all situations. The goal is to define standard library "components" that can be combined together in ways that matches the performance demands of a particular application. --------------- And this is all still single-threaded land. If you want a highly performant multithreaded data-structure, you're probably going to have to write your own from scratch (instead of using building blocks from the standard library). There's just too many performance assumptions that goes into a multithreaded data structure. Is it read-mostly / write-rarely? Read/write balanced? Single-producer / multi-consumer? Multi-producer / single-consumer? Multi-producer / multi-consumer? Is the data-structure able to "count the threads" that may access it and use thread-barriers (thread-pools may practically limit a data-structure to say 64-threads, which means a 64-thread barrier / semaphore can be a highly-performant solution to synchronization) ? Or is it a fully dynamic design where an unbounded number of threads may exist (unbounded number of threads means the sempahore method won't work). -------- I mean... most people don't care about performance. So a standard library data-structure with a mutex is just fine for well over 95% of applications. But if you care about performance, then suddenly things get complicated.
benibela 5y ago
I benchmarked dozens hashmaps when building my own programming language in Pascal Such an 2-array insertion order map turned out to be one of the fastest maps I was a little bit surprised
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 ago
  Thank 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.

118 points by eatonphil 5y ago

This is a weird article. It creates the idea that hash maps are uncommon? surprising? I am not really sure. Then makes the claim that you would expect them to be ordered by insertion order, and not just randomly which is the common usage of hash maps. Ordered Hash Maps exist, and isn't a insertion order hash map, basically just a list? But Hash Maps are so common and used absolutely everywhere its almost like its aiming at people who have used them but never any other data structures.

EamonnMR 5y ago
When I was first taught Java in college I didn't find out about hash maps for a while because it was considered too advanced for beginners (ohh scary templates!)
- myphs 5y ago
  This is quite interesting. I wonder, why this was decided to be too advanced. In my uni we teach it from the very beginning.
pydry 5y ago
Python switching all dicts to being ordered is my favorite new feature from the last five years. It's useful all over the damn place.
rob74 5y ago
Hash maps are a fairly recent addition to the standard data structures "library", because they are relatively performance-intensive. They are of course very useful and therefore commonplace now, but I think that only came about after the rise of dynamic languages which have built-in hash maps (Javascript objects, PHP "associative arrays" etc.). So nowadays any new programming language which wants to attract web developers (e.g. Go) needs a built-in hash map.
- mypalmike 5y ago
  Hash maps have been commonly used in C since just about forever. "isn't a insertion order hash map, basically just a list?" No. They are different in the computational complexity of random access operations.
  - benibela 5y ago
    But the standard C++ std::unordered_map only came with C++11
- boardwaalk 5y ago
  Ehh, hash tables were invented in the 50s and were and are used wherever they are useful. I’m pretty sure a running joke is that every decently sized C program contains a half dozen hash table implementations. They’re not recent.

chris_st 5y ago

The surprising/interesting thing about this article is the notion that insertion order is the order that you want to iterate through a hash map. In my experience, I'm doing either (A) using them as associative memory (I want the value for a key) and I don't ever iterate, or (B) I don't care about order when I iterate (I'm summing values, say) or (C) I want the keys in some sorted order, that probably has nothing whatsoever to do with insertion order (counting keywords, then showing them in alphabetical order). So I'm curious why the insertion order is preferred, in your experience.

macspoofing 5y ago
>So I'm curious why the insertion order is preferred, in your experience. It's a little bit like asking what's the use of a linked list. A map which can iterate through keys in insertion order is just a data structure. A recent use-case for me was using timestamps as keys that map to captured state at that time.
- recursive 5y ago
  > A recent use-case for me was using timestamps as keys that map to captured state at that time. That sounds like sorted key order would suffice just fine.
- chris_st 5y ago
  > * It's a little bit like asking what's the use of a linked list.* Well, no, it's more like asking why you'd use data structure X instead of Y. I was asking why you'd want that property as part of your data structure, and pointing out that (AFAIR) I've never needed it. For your use case, I guess you wanted to be able to retrieve the data for specific time stamps? Otherwise I'd think you'd just put it into an array.
__s 5y ago
A result of insertion order is that when I print {b:2,a:1} I get "{b:2,a:1}". This can be nice for being able to store something like an HTML element's attributes as a dictionary while still serializing it back to the order it was declared with Sorted order also requires sortable keys-- not something that's required when hash maps only require hashing & equality A stable ordering is nice, without the ability to sort insertion order meets this ask. https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1... shows how in Python this useful property also comes as a side effect of an optimization

noneeeed 5y ago

Curious to read this and not see a reference to Ruby. In Ruby hashes are ordered by insertion, can have any object as keys, but the hash key value can be defined on a class by class basis (by overriding the default `hash` method on the class). The ordering is one of those features that I need very infrequently, but when I do it significantly simplifies that bit of code. I've always found the usefulness and flexibilty of Ruby's hashes to be a double-edged sword though: they are extremely useful, but this leads people to use them in situations where defining a proper class might be better for long-term maintenance.

weatherlight 5y ago
I've used this feature of Ruby Hashes to create something that behaves like a a LRU cache :)
- noneeeed 5y ago
  Interesting, I'm trying to work out how that would work. Would you mind giving a quick overview?

jerf 5y ago

"The other feature you quickly find yourself needing is the ability to use arbitrary objects as keys in a hash map. In languages that don’t support that (Perl, Python, Go, JavaScript until recently)" I don't think that's right. Python and Go do effectively support that. Each has their own take on the problem of being unable to use mutable keys, but I index by some sort of object all the time. Makes iteration over hashes substantially more useful when you get objects for both hashes and keys. Back in the Python 2.0 era, before it grew all the other features that were advantages over Perl, before Python even had generators/iterators, this was one of the big reasons I preferred Python over Perl. Only being able to index by strings wasn't necessarily a huge stopper in theory, but in practice it was very dangerous, because you really need to encode your keys. It was extremely common to see print($hash{$keyPart1 . "|" . $keyPart2}); when what you need is print($hash{pipeEncode($keyPart1) . "|" . pipeEncode($keyPart2)}); to be safe, where pipeEncode can be as simple as a routine to backslash encode pipe and backslash characters (although no simpler than that; you must do both of them to be safe, that's the minimum). This could result in non-trivial bugs and even security issues when you start encoding things like $object . "|" $permission and hackers start sticking pipes in the names of objects. But between the inconvenience of that if you know what you're doing, and the pile of code you'll encounter from developers who don't know why that's important (and may even argue in code review), it was definitely the sort of thing that grinds you down over time. In Python it was safe to print(hash[(keyPart1, keyPart2)]) and it was consistent and safe. Or use an object, etc.

nemo1618 5y ago
Go does not support using some types as map keys, including slices, channels, functions, and other maps. Slices are the most annoying, and I have seen plenty of code that uses fmt.Sprint(s) as a workaround. Fortunately the compiler now recognizes when you convert a []byte to a string for use as a map key, and will not allocate a new string.
- arp242 5y ago
  In Go it depends if the type is "comparable"; i.e. if "==" works. You can use arrays in Go; e.g. map[[2]int]string, and you can also use channels; although I'm not sure what the rules for comparing channels are exactly off-hand (I'm struggling to come up with a scenario when this would be useful off-hand actually). The big problem with slices and maps is that they can be modified. That is, what happens if you modify a slice after you used it as a map key? In slices this is worse than with maps because the backing array can change if you run out of cap space. And also, do you compare by value or identity? And again, what happens if either changes? I'm not sure if it's possible to come up with a set of rules that wouldn't take people by surprise in at least some cases.

bullen 5y ago

I wish JavaScript had linked hash maps as default so that JSON would not require arrays to keep the order of objects! Hierarchies would not have to look like this: http://root.rupy.se/meta/user/task/563541707719927980 http://root.rupy.se/meta/user/task/563541707719927980

ajanuary 5y ago
Javascript already does retain insertion order (except for special casing of things like integer keys) JSON objects, however, have unordered keys. JSON != Javascript.

arsome 5y ago

Is there a proper way to use custom objects as keys in hashmaps in JS (well, ideally TypeScript compliant)? Coming out of the C++ world where this is trivial and something I use quite often this seems pretty infuriating. Maybe a general data structure package that's worth pulling in? EDIT: After doing a bit of research I found "tstl", looks interesting, their hashmap appears to support custom hashers and equality comparisons: https://tstl.dev/api/classes/std.hashmap.html https://tstl.dev/api/classes/std.hashmap.html I'm curious about experiences with it if anyone's had the chance?

upzylon 5y ago
If the problem is just that you want to use non-primitive keys, that's what Maps are for. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- arsome 5y ago
  I'm aware of them, but the problem with that is you can only compare an object by instance if I recall correctly. There's no way to override the hashing and equality check that I could find, meaning even for simple objects you're basically forced to serialize your keys in some way still, which is disgustingly inefficient and slow for no good reason.
  - doteka 5y ago
    So much this. I remember being so excited that Map and Set were added to the language, only to find that they were worse than useless for objects. At least Set can be handy in a pinch, but I have never seen an actual usecase for Map that isn’t solved better with plain old JS objects. Curious if anyone else has?
    - upzylon 5y ago
      There definitely are valid use cases for a Map, and even more now that we have WeakMaps (e.g. associating data DOM nodes). Or mapping functions to values, e.g. something like this: const returnCache = new Map<() => any, any>() const memoized = <T extends () => any>(f: T): ReturnType<T> => { if (returnCache.has(f)) return returnCache.get(f) const v = f() returnCache.set(f, v) return v }

peterkelly 5y ago

Rust has HashMap and BTreeMap. You use the latter when you care about ordering. There's also a couple of options for dequeues. A good overview here explaining which one you'd choose depending on what oyu want to do: https://doc.rust-lang.org/std/collections/index.html https://doc.rust-lang.org/std/collections/index.html Use the right data structure for the job. Maps are an interface, not an implementation.

floitsch 5y ago
Rust has hash maps that hate you. The default hash map visits the keys in arbitrary order (https://doc.rust-lang.org/std/collections/struct.HashMap.html#method.keys https://doc.rust-lang.org/std/collections/struct.HashMap.htm...). You could use a BTreeMap, but that's not insertion order and requires the user to come up with some sort of ordering.
- IshKebab 5y ago
  They don't hate you. That's how it's supposed to work. Otherwise you get issues like the one discovered in the article. Would you say Rust has Vecs that hate you because prepend isn't O(1)? Or does JavaScript have Maps that hate you because they aren't sorted? There's no perfect container. It's all trade-offs.
  - ErikCorry 5y ago
    The article also explains how the issue discovered can be fixed. And JS maps are insertion ordered.
    - c-cube 5y ago
      The article doesn't expand much on the performance cost. Another comment mentions Swiss tables, which are what rust HashMap is based on these days, and it's unlikely that python's maps are as optimised. Not to mention the unavoidable memory overhead.
      - 5y ago

adrianmonk 5y ago

Having hashmaps be ordered is not always desirable. It's not necessarily meaningful for every application[1]. Also, it can have overhead. If the problem is that the developer doesn't get what they expect, often the solution is to require the developer to be explicit about what they ask for. I think that could work well here. Instead of having map.keys(), the API could have map.orderedKeys() and map.unorderedKeys(). (Or make it okeys() and ukeys() to be more concise.) Yes, it's slightly more typing, but to me that's a small price to pay to ensure you get what you want. --- [1] For example, maybe the order that's meaningful to me has something to do with the values rather than the keys. If the map represents git commits, maybe the order that's meaningful to me is a topological sort, and the map isn't going to provide that.

stickfigure 5y ago
This would be genuinely weird. The in-memory representation will make one or the other approach more efficient. If you want ordered, pick an ordered implementation (eg Java's LinkedHashMap). If you don't care, pick an implementation that doesn't care (eg HashMap). If you want some special ordering, pick something that can use a Comparator (eg TreeMap) or just sort the data when fetching. A Frankenstein LinkedRandomTreeMap would pay the overhead of all approaches for an extremely exotic use case.
- adrianmonk 5y ago
  I suppose these ideas can be combined. An implementation that doesn't support ordering could be of a type that only has an unorderedKeys() and lacks orderedKeys(). Which is more explicit than having a keys() function that behaves differently than other types' keys() functions. Also, I guess you could define unorderedKeys() to mean "I'm not picky about the order" (rather than "it must not be ordered"). Then all types could have an unorderedKeys() function.
  - stickfigure 5y ago
    If unrderedKeys() isn't picky about the order, then there's no reason to have a separate method. Just keys() will do, and different implementations can have different behavior. Also note that relaxing the ordering requirement when obtaining keys does not necessarily improve performance; if you've already done the work of maintaining an ordered list (ie LinkedHashMap), it's actually faster to iterate in order. Furthermore, what exactly does orderedKeys() mean anyway? Insertion order? Does reinsertion change order? If some sort of natural ordering (eg, topological) then how do you configure that? I think the "state of the art" is basically correct here: An abstract Map interface that provides basic operations, and a variety of implementations all with different behaviors and performance profiles. Sorry.

usefulcat 5y ago

First off, WTF is up with disabling copying? That is seriously annoying. Now on to what I came here to say.. "When there are enough of these tombstones, the hash map gets rebuilt, but that’s OK. Due to the magic of amortized constant time, this doesn’t slow you down on average." If amortized time is all you care about, that's fine. But there are some applications where worst case time is more important, and unfortunately I've seen some hash map implementations that implicitly assume that the worst case never matters.

prutschman 5y ago
In some browsers you can get around this by selecting the text, keeping the mouse button down, hitting the keyboard shortcut for 'copy', then letting go. The selection will still be emptied, but the text is already in your clipboard.

AtlasBarfed 5y ago

Java is treated as the "prior art" like it is some sort of ancient script? That is amusing. Since Java was the first mainstream GC language with sufficient man-hours of engineering, and it was an opportunity after almost two decades of C/C++ libraries to start anew with the standard library, but its standard library always seemed simply evolutionary/"best practice" (not my favorite phrase, sorry) from what came before it. Is the hashmap impl in the JDK actually novel for its time? But

ErikCorry 5y ago
As I understood it, there was an implementation of "compact dictionaries" in Java, but it was not the implementation of any of the collections that were built into the language. It is "prior art" in that it was done before compact dictionaries were reinvented for Python.
- abecedarius 5y ago
  IIRC it was for the collections library of the E language, whose first implementation was in Java (erights.org). The E designers had a self-imposed constraint that everything computational had to be deterministic. The standard way of doing iterable hashtables lacked this property. I tried to check my memory by following the link to the Raymond Hettinger talk, but he doesn't say just what prior work he was talking about, only that it was in Java.
  - cb321 5y ago
    "An Efficient Representation for Sparse Sets" by Preston Briggs & Linda Torczon dates from Rice in 1993 covers the case where the index can be a direct map (for small key universes - like, say, the range of `char` or `short`, where one can be sure of no collisions/need to handle them). The idea is simple enough that it could have been a subsection in some seminal early database work, but I also lack a reference for that. Storing some (or all) of the hash code in the hash index part as this article mentions is a good idea I had independently. This is especially true if you do linear probing on the hash table part and care about worst case latencies. (You will basically never have > 2 full cache misses if the CPU BP/prefetcher can recognize a linear scan.)

patrickthebold 5y ago

This reminds me of one bug I introduced a long time ago: This was a node backend, and there was some code that was recreating an object be reinserting all the key value pairs in a precise order so that that's how it would serialize in the json and then the UI depended on that order. But to me, it was just recreating the same object so I deleted that code, causing the bug. In retrospect, I should have at least asked the committer what they were trying to do. In my defense, this was before javascript guaranteed the insertion order would be the order kept.

dragontamer 5y ago

There's all sorts of application-specific assumptions in this post, that it isn't funny. Ex: Use of hash-tables with insertion ordering to handle a insert-once task queue (preventing "double tasking" if a task is ever somehow inserted twice?) Solvable with a Linked-list, circular buffer queue + hash table combined together (hash-table to prevent double-insertions. Linked-list / circular buffer queue for the FIFO functionality). If O(log(n)) insert/removes are sufficient and you have priorities associated with each element, a Heap data-structure works (all "repeats" will be next to each other, because max-heaps always keep the maximum element on the top) The goal isn't supposed to be to make a data-structure that magically works in all situations. The goal is to define standard library "components" that can be combined together in ways that matches the performance demands of a particular application. --------------- And this is all still single-threaded land. If you want a highly performant multithreaded data-structure, you're probably going to have to write your own from scratch (instead of using building blocks from the standard library). There's just too many performance assumptions that goes into a multithreaded data structure. Is it read-mostly / write-rarely? Read/write balanced? Single-producer / multi-consumer? Multi-producer / single-consumer? Multi-producer / multi-consumer? Is the data-structure able to "count the threads" that may access it and use thread-barriers (thread-pools may practically limit a data-structure to say 64-threads, which means a 64-thread barrier / semaphore can be a highly-performant solution to synchronization) ? Or is it a fully dynamic design where an unbounded number of threads may exist (unbounded number of threads means the sempahore method won't work). -------- I mean... most people don't care about performance. So a standard library data-structure with a mutex is just fine for well over 95% of applications. But if you care about performance, then suddenly things get complicated.

benibela 5y ago

I benchmarked dozens hashmaps when building my own programming language in Pascal Such an 2-array insertion order map turned out to be one of the fastest maps I was a little bit surprised

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 ago
Thank 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.