Is map order arbitrary?

Evan_Reese

When I have an empty map and I add new entries, does it add them in any particular order? If not, can I force it to? For example if I do this:

var myMap = {};

myMap.one = 1;
myMap.two = 22;
myMap.three = 333;

print(myMap);

The printed result might look like this, which is out of order. I hoped it would always add the new one at the end.

{"two" : 22, "one" : 1, "three" : 333}

john_mcclary

I figured the map was based off of a hash table, or dictionary in other C-like languages.
Where each item in the map is assigned a random hash code that can be looked up quickly given the key.
So, it's position of an object in the map is irrelevant to function and becomes unsorted.

(103) 10. Dictionaries - YouTube
This video will teach you everything you want to know about dictionaries, but you can skip to about 50min, that's when it gets out of the theory and into a more practical view of it.

I'm not sure how Onshape handles the specifics, but I would assume the hash code is generated in the same way as the internal IDs in featurescript.
Or I could be completely wrong.

_anton

https://cad.onshape.com/FsDoc/relational.html

Iteration over FS maps should happen in key order. I expect to (and do) see
{ one : 1 , three : 333 , two : 22 }

Evan_Reese

Thanks, John! I'll check it out.

ilya_baran

@john_mcclary if you want details you can have them: FeatureScript maps are internally implemented as functional AVL trees (sorted, balanced binary trees), rather than hash tables.  This is to make the following kinds of code fast and memory-efficient:

println("Old value: " ~ x[3]);
println("New value: " ~ y[3]);var x = { large map };
var y = x;
y[3] = 5;

With a hash-table, we'd basically have to make a copy on either the second or third line, but with a tree, we can share almost the entire tree between x and y.  Plus I think that having the data in key order is nice.

john_mcclary

Cool, i'm going to have to learn more about avl trees to digest what you're throwing down. But that's good to know how the nuts and bolts work.