CODEWITHSUNDEEP
javaperformancedictionary
G. Bach
G. Bach

Reputation: 3909

Efficient java map for values.contains(object) in O(1)?

I've started writing a tool for modelling graphs (nodes and edges, both represented by objects, not adjacency matrices or simply numbers) recently to get some practice in software development next to grad school. I'd like a node to know its neighbors and the edges it's incident with. An obvious way to do this would be to take a HashSet and a HashSet. What I would like to do however is have a method

Node_A.getEdge(Node B)

that returns the edge between nodes A and B in O(1). I was thinking of doing this by replacing the two HashSets mentioned above by using one HashMap that maps the neighbors to the edges that connect a node with its neighbors. For example, calling

Node_A.hashmap.get(B)

should return the edge that connects A and B. My issue here is whether there's a way to have

HashMap.keySet().contains(Node A);
HashMap.values().contains(Edge e);

both work in O(1)? If that isn't the case with the standard libraries, are there implementations that will give me constant time for add, remove, contains, size for keySet() and values()?

Upvotes: 1

Views: 307

Answers (2)

zvez
zvez

Reputation: 818

As AmitD said HashSet and HashMap alredy have constant times for for contains, get and put. For HashMap.valueSet().contains(Edge e) case you may try to look at HashBiMap in Google Guava library.

Upvotes: 1

Bernd Elkemann
Bernd Elkemann

Reputation: 23560

Try not to over-think this. E.g. you are saying you get the edge between A and B by Node_A.getEdge(Node B). But normally it is the A->B-information that IS considered the edge. (So you are requiring the information you should be retrieving.)

You say you want O(1), understandably, and obviously storing an adjacency-matrix will only give you O(n), so you cannot use that; but already the second-most obvious choice storing a list of adjacent nodes within each node object will give you what you want. (Note: this is different from having a global adjacency-list which would give you O(n)).

Upvotes: 1

Related Questions