title: How to quickly know the indexes in a massive ArrayList of a very large number of strings from this ArrayList in Java?
body: <p>Suppose that I have a collection of 50 million different strings in a Java ArrayList. Let <code>foo</code> be a set of 40 million arbitrarily chosen (but fixed) strings from the previous collection. I want to know the index of every string in <code>foo</code> in the ArrayList. </p>
  
  <p>An obvious way to do this would be to iterate through the whole ArrayList until we found a match for the first string in <code>foo</code>, then for the second one and so on. However, this solution would take an extremely long time (considering also that 50 million was an arbitrary large number that I picked for the example, the collection could be in the order of hundreds of millions or even billions but this is given from the beginning and remains constant).  </p>
  
  <p>I thought then of using a Hashtable of fixed size 50 million in order to determine the index of a given string in <code>foo</code> using <code>someStringInFoo.hashCode()</code>. However, from my understanding of Java's Hashtable, it seems that this will fail if there are collisions as calling <code>hashCode()</code> will produce the same index for two different strings. </p>
  
  <p>Lastly, I thought about first sorting the ArrayList with the <code>sort(List&lt;T&gt; list)</code> in Java's Collections and then using  <code>binarySearch(List&lt;? extends T&gt; list,T key,Comparator&lt;? super T&gt; c)</code> to obtain the index of the term. Is there a more efficient solution than this or is this as good as it gets?</p>