HashMap Data Structure

Collapse Content Show Content

The HashMap in Java uses a Hash function so all its basic operations (adding, removing and finding keys) can be done in constant time. Other languages provide the same capabilities with their Map-equivalent classes. The HashMap's performance is useful for finding optimal solutions to many different problems.

Dictionary Data Structure

Many projects involve matching keys and values so the Map data type is often a natural fit for implementing them:

Application	Purpose	Mapping
Phone book	Get phone numbers	Map names to phone numbers
Dictionary	Define words	Map words to definitions
Internet DNS Lookup	Find IP addresses for accessing websites	Map domain names to IP addresses

When Not to use HashMaps

Q: If the HashMap can do everything so quickly, why would I ever use another data structure for quickly looking up items?

A: It's great for quickly looking up keys and values, but it doesn't store the items in order. Sometimes an application needs to get the next elements in order on a list, or display all the elements in order at once. For example, you could use a HashMap for a simple PhoneBook-lookup app, but it wouldn't be able to display the Phonebook contacts in alphabetical order. For such an app, you would want to use a sorted data structure instead, such as the TreeMap (a type of Search Tree).

Challenge

The "Prime Prime" is a prime number that is the factor of the most numbers in a given list. Can you find the Prime prime in each list?

For example, for the list {2, 3, 5, 6, 9}, the answer is 3, since 3 is a factor of 3, 6, and 9, which is more than any other number in the list.

Note: Unlike the prime challenge, here each number N in a list will be in the range 2 to 10,000.

Guideline
Get all the prime numbers that you need like in the last challenge. Then use a HashMap to keep track of the number of times each prime number is factor of a number in the list.