3 ms·

Interesting that there are so many ways to implement ordered sets and maps. V8 takes a very different approach when implementing ordered sets and maps. It works

• masklinn 5y ago
  > It works more like a linked list. After looking at it, it doesn't. The "linked list" bit is just that it uses closed addressing (separate chaining), but instead of having a linked list of buckets, all the buckets are part of the array and the links point back into the array. Raymond Hettinger's naturally ordered hashmap uses a similar "trick" for an open addressed map: a sparse array of hashes, and a separate dense array of actual data. In both cases, the ordering is preserved through a dense array and the sparse "hash map" indexes into that array, this is as opposed to the older method of ordering (e.g. LinkedHashMap or PHP's own implementation) where the map items would be augmented with a (usually doubly) linked list maintaining the ordering information. Of note: this order version can still be useful if the ordering information can be manipulated, manipulating ordering in the dense-array version would be expensive and convoluted. That's why even though CPython switched to the "hettinger map" back in 3.6 the OrderedDict collection still uses a doubly linked list to maintain its ordering information.
• fanf2 5y ago
  Note that there are two different meanings of “ordered” in this context. In an ordered hash map (like PHP, JavaScript, and Python) it means insertion order. But the article is talking about lexicographic order, for which you need a tree structure of some kind (binary tree, btree, trie, or this article’s fst).