Bernard Poulin wrote:
If you can not tune a HashMap it will be worse than an ordinary array.
It will take more space and more processing time.
This will of course depend on the size and usage - it *may* be more
efficient with hashmaps. Do you really think we can generalize being it
worse all the time?
I will not be far wrong. If your primary allocation is to small, many
array keys hash to the same spot and you have to search a long linked
list. It is is too big, you waste a lot of space. It is not trivial to
increase the size of the allocation dynamically since you must rehash
all of the entries.
Keeping an array "ordered" to be able to do binary searches can
statistically cost a lot of "copying" at insertion time.
You are only adjusting links unless you want a balanced tree.
Binary searches may involves a lot more string comparison. In a binary
search comparing the "string hash" value is of no use to know if the
value
is "greater" or "lower" (to decide for the next search direction). In
hashmaps, the lookup in the "chain" after the hash jump can, most of the
time, "skip" a string entry without even looking at the characters by
comparing the 32bit integer hashes.
String hashes are only useful for looking up a specific value. It is
unlikely that the hashes are even stored since once you store the
key/value you no longer have any need for the hash since the position in
the main table is known and you can follow the links in the overflow
back to the main table(usually).
If you are hashed into the overflow, you have to examine each key since
the hashes are identical for everyone in the list (otherwise they would
not be in the list - they would be in another list of collided hashes).
About Arrays (this is more than slightly OT) :-)
I still believe Arrays are implemented as associative arrays. But this is
just pure belief since I have no proof and it could easily change from
one
version of the VM to the other.
"Associative array" is not a physical description of the implementation.
It describes the logical way that an Actionscript programmer finds the
value associated with a key. The implementation of Array probably
involves a fairly simple linked list of key objects that point to value
objects. Whether the keys are linked as a tree structure to speed up
access is an interesting question which was raised earlier.
var a:Array;
a[0] = 'abc';
a[123456789] = 'high index value';
a["this is text"] = 'non-integer index';
trace(a.length); /// should output 123456790
Sidenote: I often use this "feature" of Arrays to make an "ordered
associative array" in one single object. This may look a bit like a
hack -
but it is perfectly valid. I can both traverse the keys in a fixed custom
order and lookup one item with its key directly. Also you can retrieve
quickly how many items there are using "length". For example, when
inserting
a new entry, I do something like:
a[key] = value;
a[a.length] = key;
I would really like to have insights into the flash VM implementation
so I
could do better choices regarding maps and arrays.
Agreed
regards,
B.
(--snip------rest of previous mail removed to keep it
shorter-------snip---)
_______________________________________________
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
