Java: Iterating HashMap - Algorithm needed

Question

Hi! I have a question.

I have a list of names, say 8 names: Joe, Bob, Andrew, Bill, Charlie, Sarah, Ann, Victor

The count of names might differ**.

1) What should I use as name list? Hashmap, Vector, Hashtable, List, ArrayList?

2) I need to match them up like this: Joe-Bob, Andrew-Bill, Charlie-Sarah, Ann-Victor. Could you please show me an example how to make a loop which would do so?

Thank you!

Answer 1

Hashmaps have no order. If you want to insert a list of names like you want, you'd do something like the following (with an array):

for(int i = 0; i < myArray.length - 1; i += 2) {
    hashMap.add(myArray[i], myArray[i+1]);
}

Answer 2

It's not exactly clear what you mean by "associating" the names and what you need to do with them. Also you don't say whether the names are unique.

You can pair names this way:

String input = "Joe, Bob, Andrew, Bill, Charlie, Sarah, Ann, Victor";
String names[] = input.split(",");
Map<String, String> output = new HashMap<String, String>();
for (int i=0; i<names.length; i+=2) {
  output.put(names[i].trim(), names[i+1].trim());
}

and then do:

output.remove("Joe"); // Joe is paired with Bob

If you also need to associate Bob with Joe, you could do it this way:

String input = "Joe, Bob, Andrew, Bill, Charlie, Sarah, Ann, Victor";
String names[] = input.split(",");
Map<String, String> output = new HashMap<String, String>();
for (int i=0; i<names.length; i+=2) {
  String first = names[i].trim();
  String second = names[i+1].trim();
  output.put(first, second);
  output.put(second, first);
}

and then do:

String other = output.remove("Joe");
output.remove(other);

Answer 3

Your choice should depend on the purpose for which you want these names. Do you want efficient search over the list for a given last name? If yes, then you should follow Anon's proposal.

Otherwise, you could just create a class where you could keep information about each person (first name, last name, telephone, etc.) and use a Vector to keep the instances of this class. An example of this class could be:

class PersonDetails {

    String firstName;
    String lastName;

    public PersonDetails(String fn, String ln) {
        firstName = fn;
        lastName = ln;
    }
}

For the insertion of the names in the vector you could use something like the following:

for(int i = 0; i < nameArray.length; i += 2) {
    vector.add(new PersonDetails(nameArray[i], nameArray[i+1]));
}

Answer 4

If you have an array to start with but want to remove elements as you process them, first convert it to a List of some kind. Also, removing items from the beginning of an ArrayList can be very expensive, so if you have a lot of names, you may want to use either a LinkedList (though there are very few reasons to actually use this between performance and memory utilization, it is better to have a circular List but this does not come standard with Java).

So, in your case, you know you will be processing the list sequentially so the most efficient I can think of is to create an ArrayList and reverse it then remove from the end, like this:

private Map matchNames(String[] names) {
    List namesList = new ArrayList(Arrays.asList(names));
    Collections.reverse(namesList);

    Map result = new HashMap(namesList.size() / 2);
    while (!namesList.isEmpty()) {
        result.put(namesList.remove(namesList.size() - 1), 
            namesList.remove(namesList.size() - 1));
    }

    return result;
}

Answer 5

1) What should I use as name list? Hashmap, Vector, Hashtable, List, ArrayList?

Well, it depends on your needs :) But, because of the question and because you are mixing collection interfaces (e.g. List) and concrete implementations (e.g. ArrayList or Vector), I think that you should start with the basics. An awesome resource for this is the Trail: Collections from The Java(tm) Tutorials, a really highly recommended reading.

First, you need to understand the various collection interfaces and their purpose. Then you'll choose a concrete implementations. The Interfaces section of the tutorial that I'm quoting below will help you for the first step:

The following list describes the core collection interfaces:

• Collection — the root of the collection hierarchy. A collection represents a group of objects known as its elements. The Collection interface is the least common denominator that all collections implement and is used to pass collections around and to manipulate them when maximum generality is desired. Some types of collections allow duplicate elements, and others do not. Some are ordered and others are unordered. The Java platform doesn't provide any direct implementations of this interface but provides implementations of more specific subinterfaces, such as Set and List. Also see The Collection Interface section.

• Set — a collection that cannot contain duplicate elements. This interface models the mathematical set abstraction and is used to represent sets, such as the cards comprising a poker hand, the courses making up a student's schedule, or the processes running on a machine. See also The Set Interface section.

• List — an ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List generally has precise control over where in the list each element is inserted and can access elements by their integer index (position). If you've used Vector, you're familiar with the general flavor of List. Also see The List Interface section.

• Queue — a collection used to hold multiple elements prior to processing. Besides basic Collection operations, a Queue provides additional insertion, extraction, and inspection operations.

  Queues typically, but do not necessarily, order elements in a FIFO (first-in, first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator or the elements' natural ordering. Whatever the ordering used, the head of the queue is the element that would be removed by a call to remove or poll. In a FIFO queue, all new elements are inserted at the tail of the queue. Other kinds of queues may use different placement rules. Every Queue implementation must specify its ordering properties. Also see The Queue Interface section.

• Map — an object that maps keys to values. A Map cannot contain duplicate keys; each key can map to at most one value. If you've used Hashtable, you're already familiar with the basics of Map. Also see The Map Interface section.

In your case, I don't think that you want a Queue, I'm not sure you need a Map, I think you want to allow duplicate elements so you don't want a Set and this leaves us with a List.

Regarding the concrete implementation, if a thread safe implementation is not needed, ArrayList - or LinkedList, depending on the algorithm in 2) - might be a good choice). But really, have a look at the Implementations section of the tutorial to learn more.

2) I need to match them up like this: Joe-Bob, Andrew-Bill, Charlie-Sarah, Ann-Victor. Could you please show me an example how to make a loop which would do so?

If the initial list can contain duplicate elements, I wouldn't use a Map to store matched names (because a Map cannot contain duplicate keys). So, I'd create a Couple class to store associated names:

public class Couple {
    private name1;
    private name2;
    ...
}

and use a List<Couple> to store matched names. But, because the logic of the algorithm is still not clear (does the initial list always contain an odd number of elements? is one element always associated with the immediate next one?), I can't provide more guidance.