35

I need to create phone book kind of thing. It contains name & number. Now when I type letters matching list should be returned. For the example given below, when I type H, a list containing Harmer, Harris, Hawken, Hosler should be returned. When type Ha then list containing only Harmer, Harris, Hawken should be returned. 

  Map<String, String> nameNum = new HashMap<String, String>();

  nameNum.put("Brown", "+1236389023");
  nameNum.put("Bob", "+1236389023");
  nameNum.put("Harmer", "+1236389023");
  nameNum.put("Harris", "+1236389023");
  nameNum.put("Hawken", "+1236389023");
  nameNum.put("Hosler", "+1236389023");

Any idea how achieve it? Thanks in advance.

Paŭlo Ebermann
  • 73,284
  • 20
  • 146
  • 210
Partha
  • 572
  • 1
  • 9
  • 17
  • Are you sure that using a `HashMap` at all is a good idea for something like this? I think a different data structure might be better. – Tikhon Jelvis Jul 15 '11 at 21:19
  • Are you only looking for the first letter or is it eliminating the list as you type? For example does an input of "Ha" eliminate "Hosler"? – Nate Zaugg Jul 15 '11 at 21:24

5 Answers5

35

Yeah, a HashMap is not the right data structure for this. As Bozho said, a Trie would be the right one.

With Java's on-board tools, a TreeMap (or any SortedMap, actually) could be used:

public <V> SortedMap<String, V> filterPrefix(SortedMap<String,V> baseMap, String prefix) {
    if(prefix.length() > 0) {
        char nextLetter = prefix.charAt(prefix.length() -1) + 1;
        String end = prefix.substring(0, prefix.length()-1) + nextLetter;
        return baseMap.subMap(prefix, end);
    }
    return baseMap;
}

The output would even be sorted by key.

Here an usage example:

SortedMap<String, String> nameNum = new TreeMap<String, String>();
// put your phone numbers

String prefix = ...;
for(Map.Entry<String,String> entry : filterPrefix(nameNum, prefix).entrySet()) {
    System.out.println(entry);
}

If you want your prefix filter to not be depending on case differences, use a suitable Comparator for your map (like a Collator with a suitable strength setting, or String.CASE_INSENSITIVE_ORDER).

Paŭlo Ebermann
  • 73,284
  • 20
  • 146
  • 210
  • @Paŭlo Ebermann : Why Trie, how does it save space {http://stackoverflow.com/questions/8265476/trie-saves-space-but-how} ? – Rajat Gupta Nov 25 '11 at 07:56
  • You can use prefix + "\uffff" as end, also. – Tires Nov 27 '13 at 16:16
  • @PaŭloEbermann I've the same scenario. But the existing map is a HashMap implementation (for 10k+ elements) and it can't be altered. Now, for achieving this as per the above solution, if I go for dumping the whole thing contained in Hashmap into the TreeMap, the construction of TreeMap itself will be very costly (as it builds a sorted structure), rest might be easy and fast. Any suggestions for wraping this solution on my requirements? – abksrv Aug 29 '14 at 10:34
  • 1
    @abksrv If this is just one search, a single iteration over all entries of your HashMap should be fastest. If you want to do it more often, transfer the data to a better structure. (Also, measure: maybe for your data set and hardware no optimization is even necessary.) – Paŭlo Ebermann Aug 29 '14 at 18:40
11

This calls for a Trie data structure. See this question for java implementations. I used this one.

Community
  • 1
  • 1
Bozho
  • 588,226
  • 146
  • 1,060
  • 1,140
2

Remove all values which doesn't contain key part:

yourMap.keySet().removeIf(key -> !key.contains(keyPart));

Or regex:

yourMap.keySet().removeIf(key -> !key.matches(".*keyPart.*"));

Or filter stream and collect to a new map: 

yourMap.entrySet().stream().filter(e -> e.getKey().contains(keyPart)).collect(Collectors.toMap(e -> e.getKey(), e -> e.getValue()));
Justinas Jakavonis
  • 8,220
  • 10
  • 69
  • 114
0

Put it all in a MultiMap (or just store a List as the value in your HashMap). For "Brown", store:

"B"->["Brown"]
"BR"->["Brown"]
"BRO"->["Brown"]

If you later add "Bradley":

"B"->["Brown", "Bradley"]
"BR"->["Brown", "Bradley"]
"BRO"->["Brown"]
"BRA"->["Bradley"]

etc...

then have another map to map "Brown" or "Bradley" to the phone number.

dgrant
  • 1,417
  • 3
  • 16
  • 23
  • Adding and removing things from this data structure would be *very* costly. – Mark Elliot Jul 16 '11 at 00:51
  • I agree. But we don't even know how big his "phone book kind of thing" is. I prefer to do something simple first and optimize later. This seems like the simplest thing to do. – dgrant Jul 16 '11 at 06:25
  • Accesses would be O(1) whereas for the trees it would be log(n). And isn't that more important if you're doing something like autocomplete? And how often is the dataset being updated? If gets are much more frequent that sets, who cares how slow adding/removing is. And adding and removing here is not even that bad I don't think. – dgrant Jul 16 '11 at 06:33
-2

Use guava Multimap will ease your solution.

The key is first letter of name, the value is a Collection containing all name-phone pair which name is started with the key(first letter).

Example:

    public void test(){
      //firstLetter -> list of name-phone pair
      Multimap<String, Pair> mMap =  ArrayListMultimap.create();

      put(mMap, "Brown",  "+1236389023");
      put(mMap, "Bob",    "+1236389023");
      put(mMap, "Harmer", "+1236389023");
      put(mMap, "Harris", "+1236389023");
      put(mMap, "Hawken", "+1236389023");
      put(mMap, "Hosler", "+1236389023");

      //Test
      System.out.println(mMap.get("H"));
   }

   void put(Multimap<String, Pair> mMap, String name, String phone){
      mMap.put(name.substring(0,1), new Pair(name, phone));
   }

   public static class Pair{
      String name;
      String phone;

      public Pair(String name, String phone) {
         this.name = name;
         this.phone = phone;
      }

      @Override
      public String toString() {
         return "Pair [name="+name+", phone="+phone+"]";
      }

}

卢声远 Shengyuan Lu
  • 31,208
  • 22
  • 85
  • 130