How exactly indexing works in arrays?

Question

I only know that index is faster but don't know why is it faster.

Suppose I have an array int[] a = {2,3,6,7}. Then I will try to find the element at a[3] and the speed of this will be O(1). Why? How it will know that 3 is placed after 2 boxes? So for more clarification of my question here is the structure of array I'm expecting.

index   values 
 [0] ->  [2]
 [1] ->  [3]
 [2] ->  [6]
 [3] ->  [7]

Why will a[3] go directly to 7?

HashTable

Same confusion I have for the HashTable:

 hash   values 
 [7nsh] ->  [2]
 [j2ns] ->  [3]
 [9sjm] ->  [6]
 [an5k] ->  [7]

If I search for the value from a hash function getValue(6), it will generate the same key 9sjm but how it knows that the key is placed on third number? Same how it could be O(1)?

Answer 1

Forget hashing, it is much simpler than that. Arrays will always be laid out in memory using consecutive storage locations. The compiler knows the array to start at memory cell x. When it needs to get to a[123], it adds 123 to x and uses that number to address the memory to get to the element.

It is actually 123 * elementSize but you get the point. It always takes one multiplication, one add operation and one fetch of an element from a know location.

Answer 2

Arrays and HashTables are both maps; a map converts a key into a value (or provide a place to store a value).

For arrays, the keys are integral indexes, for Java (and many languages) starting at zero.

The elements of arrays are stored so that simple pointer arithmetic can be used on the integral key — aka the indexing expression — in order to locate the storage for the element at that index. No "lookup" is necessary, it is rather arithmetic locates the desired element.

In practice this means that the elements are stored contiguously. However note that there is a difference between array of primitive value type, like int and an array of objects in Java. The array of objects is actually an array of references to objects, and those references are stored contiguously — the objects themselves are stored more according to whenever they were/are allocated (in the conceptual heap).  So, to access an element of an array of objects, the normal pointer arithmetic locates the object reference, and then one more indirection (through the obtained reference) access the object itself.

---

Hash tables are also maps; however, they allow for an arbitrary key type (as well as value type) chosen at compile time (though you could choose the very general Object type). The hash table uses the hash value of a key to distribute key/value pairs among the elements in its internal bucket array. The hash table is O(1) because even with many elements in the hash table, the lookup is relatively constant.  The item can be located: the hash value of the key is used to compute the bucket index.  Then the normal array indexing (pointer arithmetic) is applied to obtain the bucket, which is searched for the perfect match.

So, describing it broadly (i.e. for both lookup and insert) as O(1) is a bit of an oversimplification, because of the search.  The search is necessary because collisions in the bucket index computation mean multiple items have to be stored in the same bucket (that's why it is a bucket not a simple slot.)

However, when the hash table is working properly, it will keep the number of items in the any one bucket to a small number (say between 0 and 10, depending on the application), and, it does this by expanding the bucket array periodically as more elements are inserted into the hash table.  This periodic expansion has a real cost, in particular, when a trigger is crossed that the hash table decides to expand; still, that expansion can be considered amortized over many inserts because when not expanding the insertion is relatively free, O(1), as well.

Lookups, on average, will then take a small number of searches, where (expansion working properly, hash functions working well, also) this number doesn't really depend on the number of total items in the hash table.  Because of this, the lookups are basically constant.

The basic hash table offers no particular acceleration for lookup of keys or key/value pair by value (i.e. given a value without a key).   Searching for a value in a basic hash table would be O(N).  It would take a comparable second hash table of swapped key & value to accelerate that.

---

Note that memory itself (simplified, of course) is one big array, and pointers are variables that hold addresses, just like index variables hold array indexes.  the memory system allows for direct access to the memory stored at a given address.  As with arrays, the memory system doesn't store addresses it only stores the data bytes; however, it simply knows how to translate an address into a byte or word.