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: [email protected]
>>>>>>>> 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.
>>>>>>>> _______________________________________________
>>>>>>>> [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
>>>>>>>> _______________________________________________
>>>>>>>> [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
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>
------------------------------------------------------------------------
>>>>
>>>>
>>>>>>> _______________________________________________
>>>>>>> [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
>>>>>>>
>>>>>>>
>>>>>> _______________________________________________
>>>>>> [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
>>>>>>
>>>>>>
>>>>>>
>>>>> _______________________________________________
>>>>> [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
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>> _______________________________________________
>>>> [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
>>>>
>>>>
>>>>
>>> _______________________________________________
>>> [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
>>>
>>>
>>>
>>>
>>>
>> _______________________________________________
>> [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
>>
>>
>>
>>
>>
------------------------------------------------------------------------
>>
>> _______________________________________________
>> [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
>>
> _______________________________________________
> [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
>
>
>
>
>
------------------------------------------------------------------------
>
> _______________________________________________
> [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
_______________________________________________
[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
