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. > ...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
