(Java) When using Maps, does it make sense for a key and value to have the same type?

Question

To give a simple example, consider a Place class:

public class Place {
 //fields
 private String name;
 private String state;
 private int population;
 private int squareMileage;
 private int elevation;
 //constructors
 public Place() { 
 }
 public Place(String name, String state) {
 this.name = name;
 this.state = state;
 }
 public Place(String name, String state, int population, int squareMileage, 
 int elevation) {
 this.name = name;
 this.state = state;
 this.population = population;
 this.squareMileage = squareMileage;
 this.elevation = elevation;
 }
 //getters and setters
 public String getName() {
 return this.name;
 }
 public String getState() {
 return this.state;
 }
 //... (other getters and setters omitted)
 //do stuff
}

And a Places class (a HashMap of Place objects):

import java.util.*;
public class Places {
 private Map searchablePlaces;
 public Places() {
 searchablePlaces = new HashMap();
 }
 public void add(Place value) {
 Place key = new Place(value.getName(), value.getState());
 searchablePlaces.put(key, value);
 }
 public Place find(Place key) {
 return searchablePlaces.get(key);
 }
 //override hashCode, equals
 //do stuff
}

Essentially, my question is:

1. Would there be any efficiency gained in searching the HashMap for key, as opposed to searching for value directly in, let's say, a sorted ArrayList?
2. What if key was of type String equal to name + state (or of type String[2])?

• adarshr: The arguments to the map are different in add and find methods. You store <String, String> in add but try to fetch Place as though it is <String, Place> in find.
• TheBlackKeys: @adarshr I used the 2 Strings to construct a Place object, then added that Place and the one passed as an arg to the add method, so it should be <Place, Place>.

Answer 1

It's confusing, IMHO. I would define a PlaceKey class, holding just a name and a state and defining hashCode and equals. A place would hold a PlaceKey, and other attributes. And I would use a Map<PlaceKey, Place>.

Note that, in your example, it's the Place class that needs equals and hashCode, not the Places class.

Now, to answer your 2 questions :

1. a hash map is O(1), and a list is O(n). A map will thus usually be faster (except perhaps for very small n values)
2. concatenating is almost always a bad idea. You could have name1 = aa, state1 = a, name2 = a and state2 = aa, which would result in a collision. An array doesn't override equals and hashCode in terms of their content, and is not an appropriate map key class.

• Thomas: Well, a map could also be O(log n), depending on the implementation (like TreeMap) :)
• TheBlackKeys: I like this idea very much. Thank you for your response.
• JB Nizet: @Thomas : you're right. I edited the answer to talk about hash maps rather than simply maps.

Answer 2

Would there be any efficiency gained in searching the HashMap for key, as opposed to searching for value directly in, let's say, a sorted ArrayList?

Yes. Comparing strings is way slower than comparing integers (and additionally rarely comparing strings).

If you use custom object for keys, you should implement hashCode carefully with the most used possible values in mind. You should also have a streamlined equals as well.

The benefit of the custom class against the name + state would be that you can take into account the possible values.

• Thomas: Plus it's faster to do a direct lookup and possible a short sequential search instead of iterating to lots of objects in a list, i.e. HashMap lookup has O(1) cost whereas ArrayList (or any other list) lookup has O(n) cost.
• aroth: It's not quite as simple as which type is faster to compare. Hashing, in the general case, will always be faster then a linear or binary search, no matter what types are being compared (within reason). And of course, if you decide to search for a key in the map by doing something silly, like iterating the keySet, then you've completely lost the benefits of having a hash table.
• vbence: @aroth It would be faster unless, in the very very unlikely situation of all the objects producing exactly the same hashCode. - This can happen due to a carelessly written custom key object (for example basing the hashCode on the first few letters of the state), in which case there are going to be lots of identical codes.
• TheBlackKeys: I'm sorry if I wasn't clear, value is type Place, not int. It's HashMap<Place, Place>. So it would come down to the speed of comparing String objects versus the speed of comparing Place objects. Thanks for your time and sorry for the multiple edits (I'm new).
• vbence: @TheBlackKeys I get it. But the very reason for hashCode is to minimize the call to equals. When you use HashMap and search for a Place then thae API will get the hashCode of your key, then can do a binary search between the hash codes of the elements (no comparsion of strings here), then only if there are multiple items with the same hash code will it use equals. - So it boils down to "comparing integers (and additionally rarely comparing strings)" as I wronte in my answer.

Answer 3

Accessing objects through an ArrayList is much faster than doing it by a key of a HashMap, but the pointers to that objects have to be stored on memory in a continuous block, that makes slower to remove and put object in the ArrayList. So deciding which type is better will depend on the operations you will do during the execution of your program.

For example, if you need to put and/or remove the places lots of times it will be better to use the HashMap as the ArrayList is less eficient. If your places are more or less fixed and you have to move them rarely then ArrayList will give you more performance.

If you definetly use the HashMap it will be faster to use an unique string as a key.

• vbence: The OP ment "searching for value directly in ... ArrayList" - which would involve lots of equals' based comparsion. The access cost of elements is not the bigest question here.
• Thomas: Accessing objects might be faster, but not finding objects in a list.

Answer 4

Using another (not fully filled) Place object as key is at least waste of memory. Usually you search by a unique identifier. There are several possibilities to get one:

1. Use (name+SEPARATOR+state) as key, if you want to search using both of them.
2. Use several maps, one for each (searchable) property - if it isn't unique you'll connect a List to it.
3. Use a (cryptogrphic) hash of the object as key ...

Answer 5

1. It depends upon how you search the HashMap. If, for example, you use containsKey() then the map will be an order of magnitude faster than searching through the list. In the typical case, checking for a key in a hash-table happens in constant time (O(1)). Searching a sorted array for the key can be done in O(log n) time if you use a binary search. However, if you search for the key by iterating the keyset (which is not guaranteed to be sorted in any order) then you have an O(n) operation, which is slower than searching through a sorted list.

   The short version? Using containsKey() will give the best performance.

2. You could do that, but then why use a Map? Why not a List or a Set? The point of a Map is to associate a key with a value. If you aren't doing that (and the example code isn't, really), then you are using the wrong data structure for your task.

• TheBlackKeys: Thank you for the tip, then I will definitely use containsKey for efficiency. Regarding #2, I'm a bit confused. I like @JB Nizet's suggestion of defining a PlaceKey class as the key type, but (while maybe more inefficient), it still seems reasonable to use a String (containing only the relevant search terms) as the key to a Map. Would you mind clarifying? Would that not be more efficient than searching a List or a Set?