I have two lists of phone numbers. 1st list is a subset of 2nd list. I ran two different algorithms below to determine which phone numbers are contained in both of two lists.

* Way 1:   

	+ Sortting 1st list: Arrays.sort(FirstList);
	+ Looping 2nd list to find matched element: If Arrays.binarySearch(FistList, 'each of 2nd list') then OK
* Way 2:   

	+ Convert 1st list into HashMap with key/valus is ('each of 1st list', Boolean.TRUE)
	+ Looping 2nd list to find matched element: If FirstList.containsKey('each of 2nd list') then OK

It results in Way 2 ran within 5 seconds is faster considerably than Way 1 with 39 seconds. I can't understand the reason why.

I appreciate your any comments.
['https://Stackoverflow.com/questions/31799751', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1517270/']
Because hashing is *O(1)* and binary searching is *O(log N)*.
Way 1:

* Sorting: around `O(nlogn)`
* Search: around `O(logn)`

Way 2:

* Creating HashTable: `O(n)` for small density (no collisions)
* Contains: `O(1)`