An efficient way to make hash maps with insertion ordering
blog.toit.io
blog.toit.io
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.
Certainly, having an ordering on the keys themselves (eg. alphabetical order) is an alternative to insertion order. I'm fine with that. But eg. the built-in maps in Go, Perl or JS don't support that.
So often you end up getting the keys, and then immediately sorting them before iterating. That's taking something that should be O(n) and making it O(n log n). I remember doing this all the time in Perl.
And often there's no order, so you have to create one for your key type. That's extra work, and it's just easier to use a data structure that doesn't require it.
I would be interested to see performance comparisons for maps where the keys are ordered without having to sort on each iteration. Often they have tree structures internally, which means cache-unfriendly pointer chasing, but probably you can remove most of this (and the log-n access time) with wider trees like B-trees.
export PERL_HASH_SEED=0; export PERL_PERTURB_KEYS=0;
The article doesn't mention why python and perl made the choice to add more randomness but ti's because there were attacks out there where people could determine which bucket keys would be put in ahead of time and calculate a set of keys to cause pathological behavior in anything that made a hash from user input, this was commonly url parameters or POST requests. This meant that a simple web request with the right information in it could cause your application to continually reallocate memory and expand the hash size to accomadate the inputs. Usually this just burned cpu time and made other requests time out but it could also result in excessive memory usage and the OOM killer ccoming into play.
The above environment variables work to set a known seed and then not mix any new randomness in, this doesn't get you an jnsertion order but it will make the hash itself as reproducible as possible (if you don't put the keys in in the same order your results will vary still). I uwe this in a now defunct (because of second/third/fourth system syndrome) fuzzer I had going to detect problems in the prerelease versions of perl.
Perl uses a system called XS to write C code that interacts with the perl interpreter. XS doesn't have a defined API other than "what the perl internals do", this is because it's not really a C api but in fact a way to extend the interpreter itself (you can replace parts of the parser and do some other shenanigans) and it exposes basically all of the fields, structures, and functions that are used inside the interpreter to all C extensions to the language. There are some nice modern alternatives to doing things this way, but the end result is that unless we want to break just about every library on CPAN that uses any native code some care has to be applied to not change too much of the API at any given time. That's also why there's Devel::PPPort that tries to wrap both new and old APIs/structures in a way to provide some amount of compatibility between perl versions where there is otherwise no compatibility.
Relying on this type of behavior when it isn't required is somewhat of an anti-pattern. And can often lead to mindlessly copying the results of an implementation in tests.
A quick aside: any sort of generic ordered container that supports O(n) iteration must necessarily require O(n log n) work to construct in the average case. So the asymptotic complexity is necessarily the same as sorting the keys of a hash map with undefined iteration order to artificially create a defined order.
It isn't too hard to simulate the behavior of insertion order iteration by maintaining an array alongside the hash map. And surprisingly enough, space and runtime complexity is practically identical to containers that implement insertion order iteration ;-)
This doesn't apply if the order you want is insertion order.
These hash maps are constructed in O(n) on average, just like any other hash maps.
Java's LinkedHashMap is also constructed in O(n).
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/1... shows how in Python this useful property also comes as a side effect of an optimization
This implies that {b:2,a:1} is a different data structure than {a:1,b:2}, which disagrees with my intuitions about how associative arrays ought to work.
If I wanted a data structure that cares about order, I could use [(b,2),(a,1)] and [(a,1),(b,2)]
Since order is unspecified, but when serializing the hash table you have to pick one, you might as well go for insertion order and make it easier for the programmer to read. Especially since this kind of hash table gets that “for free”
Equivalence checks on unordered containers are different, and any framework which cannot check equivalence of unordered containers are worthless. Forcing ordering on inherently unordered containers does have it's price, it's certainly not free. You can pay that price at serialization, or for testing, but it makes not much sense elsewhere.
Unordered maps don't hate you, you are just not equipped to deal with it. Insertion ordered maps were a thing in the 80s with lisp property lists, which did hold your environment of symbols properly. But since then everyone switched over to proper hashmaps already. Just some not yet: Emacs, python, PHP, ...
You cannot get rid of old sins easily
This comes up a lot in compilers where you don't want the output code to vary on each run.
This is specifically a big problem with Go, because maps use random iteration order so you don't depend on it. I feel that was a mistake. I would rather they took a page from Python and JavaScript and used insertion order. The reason they did not was to avoid painting themselves into a corner with respect to algorithms and options in the future - which is reasonable.
Rust uses a randomly seeded hash algorithm on purpose to defend against hash DOS attacks.
Hashing doesn't necessarily mean indeterminate, outside of Go and Rust, but it can be tricky to guarantee because it depends on the algorithm and the memory allocator (which is often multithreaded and can introduce non deterministic behavior.)
Rust has a ton of different collections types you can use. You can also replace the hashing and seeding algorithms. It's the most flexible of the lot out of necessity. Systems programming requires fine control over data structures.
I don't see how that was throwing rust under the bus. I didn't even state my opinion, just the fact that it makes this performance for safety tradeoff (an unusual one since most hash tables do not attempt to protect against hash DOS attacks.)
You can replace the hashing algorithm. The rust compiler does this.
But most people don't fiddle with the default, which makes it a questionable decision in my books.
I don't think that anyone really could do that. I am chuckling as I am writing this.
I agree, this is what java calls a "LinkedHashMap" and what python calls an "OrderedDictionary" - there are times when it's quite useful, but often it's simply not necessary, uses extra memory and shouldn't be the default when you just need a hashmap.
In Java, there is no default; you ask for a HashMap or a LinkedHashMap explicitly. In dynamic languages like Python or JS I prefer default insertion ordered maps because if I wanted tightly optimized code, I wouldn't use those languages in the first place.
(There's also some extra time requirements, too, to chase that additional pointer from the top table to the bottom one.)
¹N.b. in some languages those items will be references, but that doesn't matter for the comparison here.
In practice the compact dict does very well on space. Much better than Java's unordered bucket-based HashMap for example.
It's true that there's an extra pointer chase.
Deletes could still leave holes in the storage array, but I think I agree (and your article also states it) that the common case is likely fill table with data, and then perform lookups.
(And I had thought bucket-based hashmaps had very much fallen out of favor to the point where they really weren't the choice of standard libraries anymore, precisely because of the additional allocations & pointer chasing they required? I'm not a Java person.)
This stack overflow answer implies the Map.Entry objects are reused during iteration which means they don't need to exist the rest of the time and a flat KVKVKV backing array could be used. https://stackoverflow.com/questions/5455824/doesnt-that-iter...
Alternatively, new Entry objects are created for each step of the iteration, then heavy inlining could enable the JIT to eliminate that allocation again.
Otherwise it would be more or less a violation of the pigeonhole principle. The insertion order is information, if you don't need to store that anywhere but you promise to give it back anyway that's a hole in your information theory.
It's easy enough (including by accident) to deliver insertion ordered iterator behaviour for small hash maps that have never had any items removed, but after that things get sticky very quickly.
There is no reason for that. A sorted list doesn't need more memory than an unsorted list. And an insertion-sorted map doesn't need to use more memory than a map that doesn't keep the order.
Independently, some properties we deem valuable are often side-products of the way the data-structure works. For example, an efficient binary search tree will naturally tend to be balanced. In the case of efficient hash maps, it is now common to add the key/value pair at the end of an internal vector. Maintaining the insertion order this way doesn't add any cost.
Firstly, and this is orthogonal to my original point, whenever people say "Cost" they actually silently mean "... that I care about" and so we're involuntarily obliged to agree to stop caring about anything else. Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections.
But my main point is that the requirement for ordering forces you to dispose of otherwise permissible optimisations which could destroy the order. You actually ran head first into this in the article, when repeatedly removing and adding elements blows up by clogging your data structure with tombstones.
Swiss Tables wouldn't clog up with tombstones. Since they don't care about ordering they only need tombstones at all in uncommon special cases (specifically, if the entire rest of the group is full or tombstones), in most cases Swiss Tables get to just set removed (key, value) pairs as empty. But this optimisation isn't open to you.
>Because of Hyrum's law even if you don't promise ordering (as Python's "Compact Dict" developer proposes at one point) your users will rely upon it and you're stuck with whatever you implemented. This is a real cost for a language or standard library. Look at the sad state of C++ standard collections.
Yes but this cost goes away if you commit to it, and the alternative (like what go does) to force the order to change all the time also comes with a complexity cost vs. doing "nothing" and having the order be arbitrary and sometimes, but not actually, reliable.
It wouldn’t handle insertion order, probably best to do alphabetical by default then. Chrome dec tools does this for js objects (which are map-like) already, and I’ve never had complaints about it.
When you have a language that support keyword arguments (kwargs) like Ruby or Python more recently.
An insertion-ordered hashmap works really well for this without requiring any extra syntax or data beyond object literals.
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.
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.
That sounds like sorted key order would suffice just fine.
The article mentions Java's LinkedHashMap, which actually can do LRU. But as the name implies, they rely on a linked list, where move=to-front is natural.
But this superpower does not come for free: a Java-style linked hash map will use more memory than the technique described in the article.
It would require either worse than O(n) amortized iteration, or worse than O(1) expected insertion (A log n has to go somewhere to satisfy the theoretical lower bound for sorting).
If you want sorted, you're going to use a tree based structure.
I'm also not sure how you'd even naturally get sorted order into a hash table. I'm sure it's possible, but on the face of it it just seems bizarre.
Hashmap is what them get. The properties of it (only useful as a direct index) is too narrow for the kind of use that in Langs like python has, where a dictionary is used everywhere (like a vector).
How some argue a hash map must be used (only useful to get a direct index) is like saying "vector can be used to only get a positional index") and wonder why people iterate it.
In other words: Collection want to be iterated.
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});
print($hash{pipeEncode($keyPart1) . "|" . pipeEncode($keyPart2)});
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)])
The issue of mutable keys is a slightly different one. If you mutate any of the properties of your object that are used by the map you are going to have a bad time, so don't do that. And I guess if your maps are sufficiently simple (eg JS's object-identity maps) then the user can't make that mistake, but at what cost?
If they are generating strings as keys and they mutate the object after creating the string then this will also break so they haven't even really avoided the problem.
My point is that it's an even worse substitute than most programmers realize, because to use it properly you have to understand how to encode parameters. The thing that people usually use, string concatenation with some delimiter, is fundamentally flawed.
(My favorite... and, alas, I've inherited a system that uses this, though fortunately it hasn't surprised me yet... is using "underscore" as a delimiter, for values whose names routinely include underscores! Fortunately, nothing ever tries to extract the original values from the key programmatically, and it's not really in a place hackers are going to attack. But still... yeesh.)
The one exception I've sometimes made is that if you happen to be in an environment where you know a certain value will never be used, you can use that as the delimiter; I've used ASCII NUL for that a few times. But you have to be sure that it's not just a "weird" value that "nobody would ever use", but something truly excluded by the context, something that regardless of what is input by someone somewhere is completely impossible to ever get to your code. Generally, the characters you can type on a keyboard are not a good idea.
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.
>>> d = {}
>>> d[[1,2]] = 10
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
Go can be consistent in a simple way because of its type system, it can see if any part of a key has something in it that can't be hashed: https://play.golang.org/p/rf8IqPb76Em
Python, as befits Python, has default behavior for instances that I believe is "is" equivalency, but you can override that with various double-underscore methods to do whatever.
Python dicts consider two keys the same if they have the same hash value and are "=="-equal. So __eq__ and __hash__ are the dunder methods to finagle. Python's sets are the same way.
A useful example is with the pathlib library.
from pathlib import Path
p = Path('a.txt')
q = Path('a.txt').absolute()
p is q # False
{p, q} # Only one element
p = Path('a.txt')
q = Path('a.txt')
p is q # False
It's useful all over the damn place.
"isn't a insertion order hash map, basically just a list?"
No. They are different in the computational complexity of random access operations.
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.
A Frankenstein LinkedRandomTreeMap would pay the overhead of all approaches for an extremely exotic use case.
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.
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.
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.
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.
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.
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.
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).
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.
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
I'm curious about experiences with it if anyone's had the chance?
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
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
}With a Map, you can easily and efficiently associate data with DOM nodes without changing them.
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.
Use the right data structure for the job. Maps are an interface, not an implementation.
The default hash map visits the keys in arbitrary order (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.
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.
And JS maps are insertion ordered.
The hash map as described in the article doesn't seem to waste any memory.
The index table needs to be sparse (for the hashing to work), and thus has quite a few entries unused. It also wants to be small in memory to improve cache locality.
Therefore you want to have the entries in the index-table as small as possible.
As example, let's say you have n entries in your map which is 2/3 full. Let's assume the key and the value each take 1 word.
In the index+key+value case you would thus use: n1.5 words for the indexes, and n2 words for the keys/values. -> 3.5 words per stored key/value.
In the key+value case you would need (2n)1.5 words. -> 3 words per stored key/value.
However, that assumes that the index-table uses a full word per entry. That's usually not the case, as you can use smaller types while the map is small enough. On 64-bit machines, the index-table will rarely use more than 32-bit arrays. In that case you would only need 2.75 words per stored key/value.
That's not really fair, though, as the value/key table has some unused space, so that it doesn't reallocate/copy every time a new key/value is added. Implementations can play with how much extra space is allocated for those unused slots.
Also, the "hash" you mentioned can be combined with the redirecting index. For Toit (the map of the blog post), the index table uses 32 bits. In these 32 bits it stores both (part of) the hash code, as well as the redirecting index.
It might be the case that the hash+key+value approach uses less memory, but I would not be confident to say that it's always the case.
Hierarchies would not have to look like this: http://root.rupy.se/meta/user/task/563541707719927980
JSON objects, however, have unordered keys.
JSON != Javascript.
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.
"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.
Such an 2-array insertion order map turned out to be one of the fastest maps
I was a little bit surprised
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
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.
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.)
- I was into E in the 90s and this idea was new to me then.
- I vaguely remember reading someone online mentioning that E was the known prior art to Hettinger's reinvention of this. But this dim memory is not reliable, so I wanted to check it.
And yeah, storing the hashcode is a technique I saw in the wild earlier than I saw the insertion-ordered hashtable.