Hashmaps - Binary Search
Time
import java.util.*;
public class BinarySearchVsHashMap {
public static void main(String[] args) {
int numKeys = 5000;
int numSearches = 100;
int numIterations = 12;
// Generate random keys
Random random = new Random();
List<Integer> keys = new ArrayList<>();
for (int i = 0; i < numKeys; i++) {
keys.add(random.nextInt());
}
// Create HashMap
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < numKeys; i++) {
map.put(keys.get(i), i);
}
// Sort keys for Binary Search
Collections.sort(keys);
// Perform search and measure time
double binarySearchTime = 0;
double hashMapLookupTime = 0;
for (int i = 0; i < numIterations; i++) {
// Generate random keys to search for
List<Integer> searchKeys = new ArrayList<>();
for (int j = 0; j < numSearches; j++) {
searchKeys.add(random.nextInt());
}
// Binary Search
double startTime = System.nanoTime();
for (int j = 0; j < numSearches; j++) {
int index = Collections.binarySearch(keys, searchKeys.get(j));
}
double endTime = System.nanoTime();
double elapsedTime = endTime - startTime;
if (i > 0 && i < numIterations - 1) { // Throw out highest and lowest times
binarySearchTime += elapsedTime;
//eliminate any outlier measurements that may skew the average time
}
// HashMap Lookup
startTime = System.nanoTime();
for (int j = 0; j < numSearches; j++) {
Integer value = map.get(searchKeys.get(j));
}
//retrieves the value associated with the specified key in the map
//in this case, we're using a HashMap, which is a data structure that stores key-value pairs
//for randomly generated keys, value is searched for in hashmap for corresponding value, which is returned as integer
//returns null if nonexistent
endTime = System.nanoTime();
elapsedTime = endTime - startTime;
if (i > 0 && i < numIterations - 1) { // Throw out highest and lowest times
hashMapLookupTime += elapsedTime;
}
}
// Convert time to seconds and calculate average time
double binarySearchAvgTime = binarySearchTime / ((double) (numIterations - 2) * numSearches) / 1e9;
double hashMapLookupAvgTime = hashMapLookupTime / ((double) (numIterations - 2) * numSearches) / 1e9;
//division by 1e9 to convert to seconds
//gets rid of high/low values through -2
// Print results
System.out.println("Average time for Binary Search: " + binarySearchAvgTime + " seconds");
System.out.println("Average time for HashMap Lookup: " + hashMapLookupAvgTime + " seconds");
}
}
BinarySearchVsHashMap.main(null);