CODEWITHSUNDEEP
javaarrayslookup
rakrakrakrak
rakrakrakrak

Reputation: 69

Java: How does the Array provide instant-lookup

More specifically, how does the Array object in Java allow users to access each bucket in constant time? I understand that Java allocates memory equivalent to the specified size at initialization, but what about the structure of it allows such rapid lookup? The reason I am asking is because it's something not available in any other data structure save those that use Array representations of data.

Another (possibly silly) question is why can't other data structures provide such quick lookup of the stored data? I guess this question can/will be answered by the answer to the first question (how Arrays are implemented).

Upvotes: 0

Views: 248

Answers (1)

Jon Skeet
Jon Skeet

Reputation: 1503899

An array is just stored as a big contiguous block of memory.

Accessing an element is a matter of:

  • Finding where the data starts
  • Validating the index
  • Multipying the index by the element size, and adding the result to the start location
  • Accessing that memory location

Note that this is all done in the JVM, not in byte code. If arrays didn't exist at a JVM level, you couldn't fake them up within pure Java. Aside from anything else, arrays are the only objects in Java which logically vary in size between instances within the same JVM. (It's possible that some JVMs have clever systems to use compressed references in some cases and not in others, but that's an implementation detail rather than a logical difference.)

Upvotes: 4

Related Questions