Map with random access behavior

I know that Java have a map, which its key is same order as the insertion order.

http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html

Now, I would like to get the key during 1001 th times insertion. However, linked is not good at random access. In order to have random access

1. I need to concert the key set to array and perform random access. Coverting key set to array is costly

2. I need to have a seperate ArrayList beside the map, so that I would have something which have map and array list feature. However, it seems that having two collections to store a same data is not a good data structure design.

Any comment for improvement?

Thanks

[703 byte] By [KwangHooia] at [2007-11-27 3:16:18]