2
$\begingroup$

I'm trying to understand how instance variables for a given object are stored for easy access later on.

For some background, I understand that if you have a reference to an array it is very easy for a computer to access any particular item in the array with an efficiency of $O(1)$ by just multiplying the index provided with the size of each item and adding that to the address of the array.

However it is not always meaningful to store things with just an index and so this is where things like HashMaps can come in handy because they allow someone to store a particular value based on a key and retrieve it in the same $O(1)$ efficiency.

So now imagine that we have some class that has many many instance variables

class myClass {
    int a1;
    int a2;
    int a3;
    ...
    int a500; //or some other really big number
}

and I write some code such as

myObject is new instance of myClass;
myObject.a5 = 123;
myObject.a450 = 70;
//etc

So my questions is:

How does the the .a450...etc get turned into an address? This type of access seems a lot more like the hashMap described above where a450 is a key that stores some corresponding value... however a hashMap really only attains that $O(1)$ access by careful maintenance of things such as the load factor. And to achieve the proper load factor you need to have a certain amount of empty items. There is also the issue that even though both hashMap and arrays have the same $O(1)$ access time... in practice the array will be much faster because there is no need to compute a hash function. It seems like this would not be an appropriate way to manage objects in any given language because if you have hundreds or thousands of such objects, then the overhead of having a hashmap would be very wasteful.

$\endgroup$
2
$\begingroup$

Since the class is fixed in advance in C++-style languages, the offset to a5 or a450 is known in advance, in compile time. Each instance of the class contains a copy of each instance variable at a fixed location (relative to the address of the instance), so there is no "load factor" to talk about. So myObject.a5 translates to something like myObject[5].

Other programming languages such as python support dynamic addition of instance variables. In that case the instance variables are stored in a hash table, which as you mention has $O(1)$ amortized access time. (Perhaps some instance variables are stored in fixed locations, for the sake of optimization.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ In particular, in a C++-style language, the executable doesn't know the names of the variables. The names are just a convenience for the programmer. $\endgroup$ – David Richerby Feb 21 '17 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.