The map implementation assumes that each key can only hold 1 value ... But I need 1 key to be able to store <Any Big Number> values
For example ... Implementation of an address list
public class Vertex {
String name;
boolean visited;
public Vertex(String name) {
this.name=name;
visited=false;
}
public int hashCode() {
return name.hashCode();
}
public boolean equals(Object ob) {
return hashCode()==ob.hashCode();
}
public String toString() {
return name;
}
}
Main class
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
PrintWriter pw=new PrintWriter(System.out);
Map<Vertex,Vertex> m=new HashMap();
m.put(new Vertex("a"), new Vertex("b"));// a ---> b
m.put(new Vertex("a"), new Vertex("c"));// a ---> c
m.put(new Vertex("a"), new Vertex("d"));// a ---> d
pw.println("All vertex from: ");
for (Vertex vert_from:m.keySet()) {
pw.print(vert_from+" ");
}
pw.println();
pw.println("All vertices to: ");
for (Vertex vert_to:m.values()) {
pw.print(vert_to+" ");
}
pw.close();
}
}
It outputs:
All vertices from:
a
All vertices: d
But I need "all vertices: bc d"
How can I fix this?
source to share
A Map
does store one value for each key. However, you can store the collection in a value, for example Set
:
Map<Vertex, Set<Vertex>> m = new HashMap<>();
Set<Vertex> set = new HashSet<>();
set.add(new Vertex("b"));
set.add(new Vertex("c"));
set.add(new Vertex("d"));
m.add (new Vertex("a"), set);
Alternatively, you can use one of the generic implementations of this concept such as Apache Commons Collections' MultiValueMap
or Guava HashMultiMap
.
source to share
What you are asking for is called "Multi Map".
If you are using Java 8 then this is pretty neat, you need to first Map<Vertex, Collection<Vertex>>
. I don't know which properties you need from Collection
which you will have to research on your own.
As you have overridden equals
and hashCode
(incorrect but valiant attempt), I assume you want the items to be unique with name
. I also assume that order matters, so LinkedHashSet
it seems like a good choice.
final Map<Vertex, Collection<Vertex>> graph = new HashMap<>();
Now, to add an item to Map
, we must first make sure that Collection
there is no key for that null
. This is exactly what is included in the new one Map.computeIfAbsent
.
final Vertex a = new Vertex("a");
graph.computeIfAbsent(a, v -> new LinkedHashSet<>()).add(new Vertex("b"));
graph.computeIfAbsent(a, v -> new LinkedHashSet<>()).add(new Vertex("c"));
graph.computeIfAbsent(a, v -> new LinkedHashSet<>()).add(new Vertex("d"));
So what does it mean, when you insert a
into Map
, if Collection
for this key null
, computes a new value for it.
Now, to get all the values for a key:
Collection<Vertex> values = graph.get(a);
You can wrap Map<Vertex, Collection<Vertex>>
in some kind of class Graph
to hide implementation details and have cleaner code:
class Graph {
final Map<Vertex, Collection<Vertex>> graph = new HashMap<>();
public void put(final Vertex key, final Vertex value) {
graph.computeIfAbsent(key, k -> new LinkedHashSet<>()).add(value);
}
public Collection<Vertex> get(final Vertex key) {
return Optional.ofNullable(graph.get(key)).orElse(Collections.EMPTY_SET);
}
}
This also applies to returning an empty collection instead null
if the key is not present in Map
. Depending on your use case, you can also wrap the returned one Collection
with Collections.unmodifiableCollection
to prevent unwanted changes:
public Collection<Vertex> get(final Vertex key) {
return Optional.ofNullable(graph.get(key))
.map(Collections::unmodifiableCollection)
.orElse(Collections.EMPTY_SET);
}
You can also use Guava Multimap
if you're not averse to external libraries.
source to share
Using Multimap for your problem, it can be written like this:
public static void main(String[] args) {
PrintWriter pw=new PrintWriter(System.out);
ListMultimap<Vertex,Vertex> m= ArrayListMultimap.create();
Vertex a = new Vertex("a"); // it better to create each object once
Vertex b = new Vertex("b");
Vertex c = new Vertex("c");
Vertex d = new Vertex("d");
m.put(a,b);// a ---> b
m.put(a,c);// a ---> c
m.put(a,d);// a ---> d
pw.println("All vertex from: ");
for (Vertex vert_from:m.keySet()) { //exactly the same as in your code
pw.print(vert_from+" ");
}
pw.println();
pw.println("All vertices to: ");
for (Vertex vert_to:m.values()) { //exactly the same as in your code
pw.print(vert_to+" ");
}
pw.close();
}
To use Guava, just download the latest jar from here and add it to your libraries.
Explanation:
By definition, each java map has one key and one value.
However, you can use Collection (like List) or Array for the value. Thus, your Map will be defined as follows:
Map<Vertex, List<Vertex>> m = new HashMap<>();
Every time you want to add an item value
to the vertex list key
, you can do it like this:
List<Vertex> list = m.get(key);
if (list == null) {
list = new ArrayList<>();
}
list.add(value);
An easier way is to use Guava Multimaps . This is the same as Map, but the value is a Collection. So ArrayListMultimap is what I described above. Way to use, but much simpler:
ListMultimap<Vertex, Vertex> m = ArrayListMultimap.create();
m.put(key, value1);
m.put(key, value2); //adds value2 to the key, which also contains value1
....
source to share