My problem is as follows.  I have an array of n strings with m < n of them distinct.  I want to create a one-to-one function which assigns each of the m distinct strings to the numbers 0 ... m-1.  For example, if my strings are:Bob, Amy, Bob, Charlie, Amythen the function:Bob -> 0, Amy -> 1, Charlie -> 2would meet my needs.  I have thought of three possible approaches:Sort the list of strings, remove duplicates, and construct the function using a search algorithm.Create a hash table and check each string to see if it is already in the table before inserting it.Sort the list of strings, remove duplicates, and put the resulting list into a hash table.My code will be written in Java, and I will likely use standard Java algorithms: merge sort for sorting, binary search for searching, and whatever the standard Java hash table algorithm is.Question: Assume that after creating the function I will have to evaluate it on each of the n original strings.  Which of the three approaches is fastest?  Is there a better way?Part of the problem is that I don't really know what's going on under the hood in standard hashing algorithms.  Any help would be appreciated.
Sorting versus hashing
sorting;hashing
Firstly, I'll note that there are two different things to be concerned with. How long will it take to assign all the numbers, and how long will it take to lookup the number later.Sort the list of strings, remove duplicates, and construct the function using a search algorithmSorting will take O(m log m) time, you can remove the duplicate in O(log m) time. To lookup the number you can use binary search which will take O(log n) time for each search.Create a hash table and check each string to see if it is already in the table before inserting it.Hash table operations are typically considered to be O(1). This is a bit of lie because it depends on the number of collisions you get. But its close to O(1) and definitely better then O(log n). Checking and inserting all values will then be O(m). Fetching the counts later will be O(1) for each fetch.Sort the list of strings, remove duplicates, and put the resulting list into a hash table.Sorting and deduplicating will take O(m log m) time. Inserting all of that into a hash will take O(m) time. Then fetching the individual elements will take O(1) time. This is basically the same as the previous option except that you spend O(m log m) extra time sorting.The second option will be fastest, at least for large enough cases. 