The tree would make sense. The garbage collection for an associative
array is an interesting problem with variable key and value lengths.
Ron
Scott Hyndman wrote:
Well, yes.
Now that I think about it my test didn't make much sense, since there would be
no way of determining how keys are generated by insertions alone...I was
assuming a uniform distribution, and it can't be done without knowing more.
But I believe that the Flash uses a tree to implement its map, for some of the
same reasons you mentioned. It's just a way more efficient structure to use if
your data is unknown, grows well, and stays balanced.
Scott
-----Original Message-----
From: [EMAIL PROTECTED] on behalf of Ron Wheeler
Sent: Sat 5/13/2006 2:25 PM
To: Flashcoders mailing list
Cc:
Subject: Re: [Flashcoders] HashMap?
Wouldn't it be true to say that hash maps will get slower as the
probability of collisions increase? As the primary area fills up, there
will be more occasions when the new key to be added, hashes to a storage
location already occupied and a link structure will be needed to store
the key(s) in the overflow.
Similarly, lookups will start to hit links rather than data which will
require that the links into the overflow area be followed.
This is where tuning comes in.
The fact that there are no tuning options makes it unlikely that hashing
is used.
Defaults would be hard to set without wasting space or turning the whole
thing into a small set of linked lists which work be long to search.
It would not be seem to be a very good choice for a default
implementation of Arrays.
Ron
Scott Hyndman wrote:
You could figure out how it's implemented by doing some experiments.
Dynamic hash maps have constant insertion (amortized) and lookup time. If the
map is implemented using a B-Tree, then you'll see O(log(n)) times (so just see
if the more properties you add increase the amount of time it takes to add
them).
Scott
-----Original Message-----
From: [EMAIL PROTECTED] on behalf of Ron Wheeler
Sent: Sat 5/13/2006 10:43 AM
To: Flashcoders mailing list
Cc:
Subject: Re: [Flashcoders] HashMap?
Bernard Poulin wrote:
I cannot say for AS3 implementation because I never tried it. (Which
is the
original subject of this topic.)
In AS1, AS2 and javascript, I am pretty sure that all objects (including
Arrays) are key/value maps. (i.e. Associative arrays)
http://en.wikipedia.org/wiki/Associative_array#JavaScript
It is very possible that the internal implementation is not a "hashmap",
but I still think it is a highly efficient map of some sort because
this is
so central to the language.
I would hope that it is efficient but hashing adds a lot of overhead and
wasted space for small arrays and really needs to be tuned to get the
desired results for larger arrays.
If the arrays are stored in sorted order, then the normal key lookup can
be done as a binary lookup which will be a lot quicker than an
exhaustive search. The price is paid when a new associative entry is added.
Nothing is free.
None of my work has required has involved large associative arrays where
hashing would add a significant improvement in speed but it would be
nice to have such a class available for those who need it.
In the early days (1960s) when I was taking Computer Science at
University, we spent a lot of time worrying about these things since
memory was scarce (64K word (36 bits per word) computer cost a million
dollars and supported 16 users) and CPU speeds where not very fast (a
1MIP computer was state of the art).
"If really had to look carefully at how things got stored and retrieved,
it you had a large number of them."
should have been written as
"One really had to look carefully at how things got stored and retrieved,
if you had a large number of them."
...at least this is what I think. I might be completely wrong.
B.
2006/5/12, Ron Wheeler <[EMAIL PROTECTED]>:
I would be a little surprised. There does not seem to be any way to
control the hash parameters and every array would have a lot of wasted
space for nothing and without any way to control the hash size and the
percent utilization, you would not get a lot of advantage for the big
arrays.
The Java HashMap defaults are pretty modest and would yield less than
optimal performance with a big array.
You can set the parameters if you have a big array and know a bit about
the "randomness" of your keys to get fast lookups with a reasonable
trade-off in wasted space
Perhaps someone who knows the Flash Player internals could tell for
sure.
Ron
Bernard Poulin wrote:
mmm... Are you implying that ActionScript objects are not hashmaps?
I thought they were *all* hashmaps (even Arrays are hashmaps). Every
method
call that you do involves at least one hash lookup.
B.
2006/5/10, Ron Wheeler <[EMAIL PROTECTED]>:
It appears that a HashMap is a Java class that uses a hash on the
"key"
to store its keys and values.
http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html
This would speed up lookup if you have a large set of keys.
If you do not need the speed or do not have a large collection of
keys
to store, an array object would seem to give the same
functionality in
ActionScript.
This leaves the implementation of the array to Flash and it is
likely a
simple structure that has to be searched sequentially (by the
Flash VM)
to get the associated value.
It you really need a hashing array that can handle large numbers of
key/value pairs, you probably have to write one. This is an old
concept
and you can likely find a few design ideas and probably some code if
you
search for it.
If you are converting code and want to create a HashMap class that
has
the same methods as HashMap in Java, you could fake the internal
storage
technology with a simple Array. it would be faster for a small set of
values and would get a bit slower as the number of keys increased.
You could start with a dumb HashMap class and then make it a true
hashing data store later without having to rewrite your code.
HashMap was only added to Java in Java 1.1 and they lived without it
before then.
Ron
Joshua Graham wrote:
Bit strange, but that works, thanks.
Joshua
On 10 May 2006, at 12:06, Lee McColl-Sylvester wrote:
Well, in AS2, it's called an object ;)
Lee
-----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED] On Behalf Of
Joshua
Graham
Sent: 10 May 2006 11:19
To: flashcoders@chattyfig.figleaf.com
Subject: [Flashcoders] HashMap?
Is there an AS3 equivalent of the java HashMap?
Basically, I just need the ability to set key/value pairs quickly/
easily.
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
------------------------------------------------------------------------
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
------------------------------------------------------------------------
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
------------------------------------------------------------------------
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
_______________________________________________
Flashcoders@chattyfig.figleaf.com
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
