How does RandomAccess interface works internally?

Question

As per my understanding, this RandomAccess interface provides an ability to retrieve data in constant time. How this functionality is achieved? Is there any hashing technique?

Thanks in advance

Answer 1

Your understanding is wrong. RandomAccess may provide a promise but it doesn’t provide any ability. Providing the ability is up to the implementing class. Actually RandomAccess doesn’t “work internally” in any sense of the expression, it has no functionality whatsoever.

In the documentation it called an indication, not a promise:

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access.

The classes implementing RandomAccess generally provide constant time access by storing their contents in an array. Array lookup takes constant time. (Classes implementing the interface include ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack and Vector according to the documentation. Surely also some third-party classes implement it too.)

Edit: Fast access in arrays relies on the hardware. The computer can access any memory cell (storage cell) in constant time. Array elements are laid out in consecutive memory cells. So if you know that an array is laid out from address 54321 and you need to access the array element at index 35, you add those two numbers and know the element is at memory address 54356 (I am ignoring the slight complication in that the word size is often 8 bytes and addresses have granularity of 1 byte). The principle is the same whether the JVM is interpreting byte code or the method has been compiled to native machine code thus bypasses the JVM. Your search engine should lead to a better explanation than the one I am giving here.

It’s quite general for interfaces they they don’t have any internal working but leave this to the classes implementing the interface (as has been said, since Java 8 and 9 the situation has become more blurred, but in this respect RandomAccess still keeps the classical design). It’s the job of an interface to specify a behaviour and that of the implementing class/es to provide it.

Edit:

From the documentation, "The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists". Why it is mentioned as algorithms here?

“Generic algortithms” refers to algorithms that you and I write that work with lists that may or may not have fast element access (may or may not implement RandomAccess). So you may write for example:

public void yourMethod(List<String> param) {
     if (param instanceof RandomAccess) {
          // do your work relying on fast element access
     } else {
         // do your work in some other way that doesn’t depend on fast element access
         // for example by iterating sequentially through the list
         // or copying the elements to a faster list implementation first.
     }
}

So no, it has nothing to do with different JVM implementations.

Answer 2

RandomAccess is a marker interface. It is an interface with no methods. Apart from that an interface generally does not have any functionality in it ¹. It is upto the implementing classes to provide random access functionality.

Have a look at

Why does ArrayList implement RandomAccess Interface?

What is the use of marker interfaces in Java?

---

¹ Yes. An interface can have default methods that has some logic. But this was added only from Java 8 to enable adding new methods to an interface without breaking the implementing classes. An interface is only for providing or declaring the contract that the implementing class has to fulfil.