Java Programming

Ive had this design problem come up twice already (in the last 3 weeks)
so i figured its time to consult the sages.

Though I know how to use a hashmap in
code I dont really know anything technical about them (or any other map
or hash---). I dont really have a grasp when to use them over ArrayList
or LinkedList aside from obvious key/value situations.
I see them used almost everywhere (I use them almost nowhere). I hear they are faster than get() methods in Lists (which I use always).

Anyway, this is my requirement:
I have an object that has a unique index (ordering value).
this index isnt the position that the object has in the list its just some number or numbers that are sortable and unique (and usually not
consequtive).

Example:
13
105
106
418
2107

(not 1, 2, 3, 4, 5)

I could have from 0-30,000+ of these objects. Right now im using a LinkedList because from what I understand they are better for random insertion (which there will be a lot of).
Because I dont have technical knowledge of Hashmaps i dont
use them - but I thought the index numbers would make good keys (theyre guarenteed to be unique).

Heres the problem. When I grab a random object I (as a requirement)
need to be able to get the previous/next object. Using the example above: if im at object indexed 105 id need to know that object indexed
13 is the previous entry in the collection.

I did research this and the Hashmap API specifically says:
"This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time."

So Hashmap is unuseable for my purposes right?

Right now i am using a binary search with a comparator to always
insert objects into the LinkedList sorted ascendingly by that index number. I am using the same binary search and comparator to then retrieve an object quickly. To grab the previous object I get the object
in the previous element and grab its index number.

So my question is: are my assertions correct? is my linkedlist with a
binary search for keeping it sorted and quickly accessible an ok method?

thanks for any input!