Arrays VS Structures

May 25, 2005

Array's and Structures (structures in CF are called hashtables, or associative arrays) are two very different data structures. There is some confusion about how arrays work in CF, and from what I can understand they are based on native java arrays.

Once common misconception is that the following code will only allocate two slots of memory:

<cfset a = ArrayNew(1)>
<cfset a[1] = "One">
<cfset a[10] = "Ten">

What is really going on here is that cf is allocating an Array with 10 elements , elements 2-9 are null. The memory allocated is about 8 bytes for each element in the array (these are references the objects they hold). The memory is allocated in one contiguous block, so if you have a very large range in your Array, it can be fairly taxing on your memory manager.

You can see the size of the array, and the length of the array is 10 elements by using either ArrayLen or the .size() method (undocumented).

Len: #ArrayLen(a)# Size: #a.size()#

It is a common misconception that CF will only allocate two slots of memory, but from my understanding it will allocate all ten, so beware of this.

If your wasting a lot of space in the array, the other option is to use a structure:

<cfset a = StructNew()>
<cfset a[1] = "One">
<cfset a[10] = "Ten">
<cfoutput>Size: #a.size()#</cfoutput>

You will notice that with a structure the size of the data structure will be just 2, instead of 10. Also note that the index of the structure is treated as a string, so you can index that structure with any string, not just unsigned integers as in Arrays.

A performance tradeoff decision must be made. Array's are very fast for retrieving elements, and for looping over. They can be slow to add elements to if you don't know the size of the array ahead of time (because they need to allocate contiguous blocks of memory). If your using array's with non-consecutive indexes you will require a lot of memory, and possibly lots of dynamic resizing.

Structures or hashtables have an expensive lookup cost compared to arrays because the string values are converted to an integer using a hash function that is used to locate a hash bucket then (because hash functions can create identical hashes for two different input keys) if the bucket has more than one item each item is compared with the key value. However if you have lots of non-consecutive indexes you will not have wasted memory like you would with an array.

So bottom line is if you have somewhat consecutive non negative integer indexes arrays are a good bet. Otherwise use a structure.

17 people found this page useful, what do you think?


I should point out that the 8 byte size I gave may be different based on the jvm and operating system (eg 32bits vs 64bit will make a difference).
Mark Kruger also has some info about this:
CF Arrays are based on java.util.Vector, which is based on a native array. It doesn't really change anything (you'll still get 10 slots), but it's worth mentioning, since it has some implications when dealing with Java directly.
If arrays are from java.util.Vector, hashtables are probably implemented from java.util.Hashtable, right? If so, the default size for a Hashtable is 11 with a fill factor of .75; for small structs, the Java engine shouldn't need to rehash until the ninth object. The Vector class has a default initial size of 10, so it won't resize itself until (hopefully) all ten slots are full. I think it's important to note the difference between the usage for arrays v. structs. Arrays associate a number with an object, whereas structs associate names (keys) with objects. There's also a speed enhancement in finding the objects with a hashtable. Arrays iterate through each object every time you look something up [O(n): actually on average you'll locate the object in n/2 searches]; structs are speedier because of the hash function has only one item [0(1)] that it has to find (and if your hashbucket has more than two items, its time to revisit your hashCode code). Granted, there is some overhead in generating the hashcode, but the Vector class also has overhead because it must maintain its synchronization. This is a bit different from what you've stated I way off on this?
Wayne, Array's don't iterate through the entire array every time you look something up. Think of an Array as a chunk of memory with slots for each item in the array, if you know you want item 10, the exact memory address of the item can be calculated by taking the address of the first item, and adding 10 * size of each item (object references are all the same size). So an array item lookup is O(1) constant time. And for structures your forgetting about looking up the hash item, when you generate the hash of the item it has to be put in a sorted sequence, then you have to do a binary search to find the item, which I think would give you a O(log(n)) - my big O is a bit rusty... As for synchronization both java.util.Hashtable and java.util.Vector are both synchronized, so that would not have any effect on performance.
thanks --------------------------
Is the default size of array in java is 10??????? plz help. hare i am confuse..... reply
require paticular differences b/n array &structure and also structures and punoins w.r.t C language
Back in the U.S.S.R Doru Hendrikje.
that's why it will never wor. Anandi Hristina.
please tell me why, i'm feeling . Jumana Fanni.
ARRAY: An array is defined as a group of related data items stored by means of a single variable name. it is use for static memory allocation. STRUCTURE: Structure is defined as a data type to represent several different types of data with a single name. DIFFERENCE BETWEEN ARRAYS AND STRUCTURES: 1.All data in a array should be of same data type.But in structures data can be of different data types. 2.Individual entries in an array are called elements.But in structure individual entries are called members. *it is used for dynamic memory allocation.
after the putting the value of array in main function ..i wanna change it udf function..
please send the concept of structers using arrays clearly
i need point to point difference.

Post a Comment


Spell Checker by Foundeo

Recent Entries


did you hack my cf?