Java ArrayList – Maximum Index Value Explained

javaprogramming-languages

I was thinking about it. You may have access to endless memory (one computer with lot of RAM) so that you can keep on adding more and more elements to your ArrayList.

But, I think that you can only access elements BY INDEX up to a certain value of index. The maximum size of this index could be = maximum number your computer can represent, that is long 9,223,372,036,854,775,807 in Java.

I know that you can access the NEXT element using an iterator. But, how do i access elements after the (9,223,372,036,854,775,807)TH index, using an index number ?

Best Answer

ArrayList in Java has a get(int index) method. int is a signed 32 bit value, with a maximum value of 2,147,483,647. That is the largest possible value that can be accessed in an ArrayList. Period. The specifics of what the maximum size of the array or ArrayList differe based upon the implementation of the JVM (which may be lower than the MAX_INT value). You can't make an ArrayList (or for that matter an int[] array) that has a long for its index.

If you were to try to instantiate an array list of this magnitude, you would have a structure that is at least 8 gigabytes - this only accounts for MAX_INT pointers, and not the additional space of the data at each point.

Attempting to access beyond the maximum value allowed through an iterator associated with the array would likely result in one of OutOfMemoryException, IndexOutOfBoundsException or a NoSuchElementException depending on implementation.

This is very impractical use of memory. If one was to want such a data structure, one should investigate less RAM intensive approaches such as databases, sparse arrays, and the like.

Related Solutions

Java – Question regarding LinkedList in Java

Here is an answer from stackoverflow that explains it pretty well:

https://stackoverflow.com/questions/716597/array-or-list-in-java-which-is-faster

Basically, the ArrayList is contiguous where the LinkedList is not. Incrementing to the next location in memory with the ArrayList is considered faster than jumping to the next location via a reference in LinkedList. Also, maintenance of the LinkedList would incur overhead to maintain two sets of references for a doubly linked list.

Java Hash Table Design – Simple Hash Function Implementation

If you want to build a hash table in Java, you should take advantage of the hashCode and equals methods which every object has, so there is no need to devise a custom hash function. Note that all Java “characters” are already numbers in the range 0x00 – 0xFFFF (they are UTF-16 code units, not ASCII characters or bytes).

Your idea of having the hash code be a Base-26 or Base-128 interpretation is a good idea for alphabetic-only/ASCII-only texts. But there are a few issues I can see:

Strings do not only contain ASCII letters, but also symbols or spaces. Frequently, text will contain Unicode characters which have no ASCII equivalent.
A hash code is an integer. To find a bucket, you'd do buckets.get(hashCode % buckets.size()). However, Java integers hold 32 bits, which offers enough bits for roughly 4.5 ASCII characters. Assuming your implementation left-shifts by seven bits and “or”s the new bits to the current hash code,
```
int hashCode = 0;
for (char c : str) {
    hashCode <<= 7;
    hashCode |= c & 0x7F;
}
```
then only the last 5 characters would be significant. This makes it extremely easy to create hash collisions: civilisation and train station.

This can be avoided by a cleverer hash function where any bit will stay somehow significant. E.g the bits in the hash code could be rotated rather than shifted, and new bits could be “xor”ed to the existing value:
```
int hashCode = 0;
for (char c : str) {
    // rotate the bits
    hashCode = (hashCode << 1) | (hashCode >> (32 - 1));
    // xor new bits
    hashCode ^= c;
}
```
Java uses a slightly different hash function:
```
for (char c : str) {
    hashCode = 31 * hashCode + c;
}
```
The multiplication with 31 makes sure that all bits are eventually used without making any bit irrelevant. Overflow is no problem due to the modulo operation when determining a bucket. The value of 31 is largely unimportant, but it being a prime number avoids hash collisions.

Best Answer

Related Solutions

Java – Question regarding LinkedList in Java

Java Hash Table Design – Simple Hash Function Implementation

Related Topic