I think there are no "tuning" parameters simply because the "language" does not (and should not) specify how the Objects are implemented (and not because they are not hashmaps). From what we know so far (i.e. nothing!), this could be anything - like a straight array up to, say, 3 entries and switching to another more complex structure after that.
By "variable key length" did you mean automatically growing the relevant hash size (i.e. involving re-distribution) - A bit like what is happening with the Java HashMap implementation ? B. 2006/5/15, Ron Wheeler <[EMAIL PROTECTED]>:
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
_______________________________________________ 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
