Re: [Flashcoders] HashMap?
For some AVM1 and AVM2 flash representation of objects, fire up this breeze presentation about the flash player 9. http://seminars.breezecentral.com/p64058844/ Around minute 28 into the presentation, it talks about AVM1 and AVM2 representation of an object. Like I suspected, AVM1 uses a straight hash table. B. 2006/5/16, Ron Wheeler [EMAIL PROTECTED]: 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---) ___ 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
Re: [Flashcoders] HashMap?
Bernard Poulin wrote: Funny, I was actually thinking of an implementation which would use a Java-style String objects. In java, all string objects have an int hash data member (computed the first time it is needed). In that scenario, only a portion of the hash value is used to make the hash lookup. The complete hash stays around since it is part of the String object and so can still be used to quickly distinguish strings. Also when rehashing you do not need to really compute new hashes - you just need to re-distribute them based on more bits of the complete hash. That only works if the hash primary table has a length that is a power of 2. If your original has maps from 1-5,000 and your increase the size of the primary storage area to 15,000, you will need more than more bits, you will need a completely different set of hash values. Not sure what Java does with its hash. Do you have to declare the maximum array size when you declare the array? Ron And yes, this is still heavier than re-balancing a tree. regards, B. 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). ___ 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
Re: [Flashcoders] HashMap?
If memory serves... There's a HashMap class in Java that hides the implimentation. You can declare it with or without a size (I don't rememv[ber the default) and optionally it will accept a load value which is the percentage of capacity at which to increase the size of the map. Growing the array, increasing the hash, etc... is all handled by the class. Since you probably have an installation you can find the source in the utils package, I think. On 5/17/06, Ron Wheeler [EMAIL PROTECTED] wrote: Bernard Poulin wrote: Funny, I was actually thinking of an implementation which would use a Java-style String objects. In java, all string objects have an int hash data member (computed the first time it is needed). In that scenario, only a portion of the hash value is used to make the hash lookup. The complete hash stays around since it is part of the String object and so can still be used to quickly distinguish strings. Also when rehashing you do not need to really compute new hashes - you just need to re-distribute them based on more bits of the complete hash. That only works if the hash primary table has a length that is a power of 2. If your original has maps from 1-5,000 and your increase the size of the primary storage area to 15,000, you will need more than more bits, you will need a completely different set of hash values. Not sure what Java does with its hash. Do you have to declare the maximum array size when you declare the array? Ron And yes, this is still heavier than re-balancing a tree. regards, B. 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). ___ 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 -- Weldon MacDonald ___ 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
Re: [Flashcoders] HashMap?
Ah yes, now that you mention it, I just checked the Java HashMap code and it is not limited to a power of two, here's a snippet: index = (hash 0x7FFF) % table.length; That way, they can still use the same set of 32bit hash values when growing. There is no maximum that can be declared. The complete hash is always kept around. regards, B. 2006/5/17, Ron Wheeler [EMAIL PROTECTED]: Bernard Poulin wrote: Funny, I was actually thinking of an implementation which would use a Java-style String objects. In java, all string objects have an int hash data member (computed the first time it is needed). In that scenario, only a portion of the hash value is used to make the hash lookup. The complete hash stays around since it is part of the String object and so can still be used to quickly distinguish strings. Also when rehashing you do not need to really compute new hashes - you just need to re-distribute them based on more bits of the complete hash. That only works if the hash primary table has a length that is a power of 2. If your original has maps from 1-5,000 and your increase the size of the primary storage area to 15,000, you will need more than more bits, you will need a completely different set of hash values. Not sure what Java does with its hash. Do you have to declare the maximum array size when you declare the array? Ron And yes, this is still heavier than re-balancing a tree. regards, B. 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). ___ 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
Re: [Flashcoders] HashMap?
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---) ___ 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
Re: [Flashcoders] HashMap?
Funny, I was actually thinking of an implementation which would use a Java-style String objects. In java, all string objects have an int hash data member (computed the first time it is needed). In that scenario, only a portion of the hash value is used to make the hash lookup. The complete hash stays around since it is part of the String object and so can still be used to quickly distinguish strings. Also when rehashing you do not need to really compute new hashes - you just need to re-distribute them based on more bits of the complete hash. And yes, this is still heavier than re-balancing a tree. regards, B. 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). ___ 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
Re: [Flashcoders] HashMap?
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
Re: [Flashcoders] HashMap?
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
Re: [Flashcoders] HashMap?
Bernard Poulin wrote: 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. If you can not tune a HashMap it will be worse than an ordinary array. It will take more space and more processing time. A HashMap does require some understanding of implementation since it is using a special arrangement of physical storage to buy you speed. From the Java docs. http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html#HashMap%28int,%20float%29|* HashMap http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html#HashMap%28int,%20float%29*(int initialCapacity, float loadFactor)| Constructs an empty HashMap with the specified initial capacity and load factor. A lot of the implementation details are hidden and you can just take the defaults for the tuning. 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 ? No. I mean that the length of each key (and each value -more obviously) is not fixed when the Array is declared. I can add a hundred 3 character keys and then add a new key which is 50 characters long and the Array object will still find a place for it. 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
Re: [Flashcoders] HashMap?
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? Keeping an array ordered to be able to do binary searches can statistically cost a lot of copying at insertion time. 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. 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. 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. regards, B. (--snip--rest of previous mail removed to keep it shorter---snip---) ___ 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
RE: [Flashcoders] HashMap?
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
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
RE: [Flashcoders] HashMap?
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
Re: [Flashcoders] HashMap?
the dictionary object in as3 allows you to use a class as the key. it also uses weak references for the keys (but not for the values). ___ 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
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
Re: [Flashcoders] HashMap?
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
Re: [Flashcoders] HashMap?
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. ...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:
Re: [Flashcoders] HashMap?
dictionary object. On 5/10/06, Joshua Graham [EMAIL PROTECTED] wrote: 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 -- j:pn http://www.lennel.org ___ 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
RE: [Flashcoders] HashMap?
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
Re: [Flashcoders] HashMap?
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
Re: [Flashcoders] HashMap?
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
Re: [Flashcoders] HashMap?
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
