hash map / collection choice

[Philipp Kraus]

Hello,

I need help to create a data structure. I have got a class

class myEdge {
private int m_edgeid = 0;
….

@Override
public int compareTo(myEdgep_edgelink) {
if (m_edgeid > p_edgelink.m_edgeid)
return 1;
if (m_edgeid < p_edgelink.m_edgeid)
return -1;

return 0;
}


@Override
public boolean equals(Object p_object) {
if ( (p_object == null) || (!(p_object instanceof myEdge)) )
return false;

return this.m_edgeid == ((myEdge)p_object).m_edgeid;
}


@Override
public int hashCode() {
return m_edgeid;
}
}

The edge ID is always unique. So I would like to create a collection in
which I can do something like

myEdge x = edgecollection.get( searching edge id )

So the collection stores the edge objects and I can get an object with
the internal id. The collection
should use the the edgeid value to identify the object.

A set should be the correct structure, but I can not get the object
itself of the map without iteration over all
items. A HashMap needs a key, value pair, so I need also a key class
which stores the edge id (redundant data).

I'm a little bit uncertain, which collection is the correct choice.

Thanks a lot

Phil

 

[Eric Sosman]

Hello,

I need help to create a data structure. I have got a class

class myEdge {

Aside: It is customary to start class and interface names with
a capital letter.

private int m_edgeid = 0;
….

@Override

public int compareTo(myEdgep_edgelink) {

I think there's a space character missing here ...

if (m_edgeid > p_edgelink.m_edgeid)
return 1;
if (m_edgeid < p_edgelink.m_edgeid)
return -1;
return 0;

Aside: `return Integer.compare(m_edgeid, p_edgelink.m_edgeid);'
does the whole job in one line of code.

}


@Override
public boolean equals(Object p_object) {
if ( (p_object == null) || (!(p_object instanceof myEdge)) )
return false;

Aside: Since the class isn't final it might someday be extended,
and then equals() could mistake a MyDecoratedEdge instance for a
plain myEdge. Try something like

if (p_object == null || p_object.getClass() != getClass())
return false;

return this.m_edgeid == ((myEdge)p_object).m_edgeid;
}


@Override
public int hashCode() {
return m_edgeid;
}
}

The edge ID is always unique. So I would like to create a collection in
which I can do something like

myEdge x = edgecollection.get( searching edge id )

So the collection stores the edge objects and I can get an object with
the internal id. The collection
should use the the edgeid value to identify the object.

A set should be the correct structure, but I can not get the object
itself of the map without iteration over all
items. A HashMap needs a key, value pair, so I need also a key class
which stores the edge id (redundant data).

I'm a little bit uncertain, which collection is the correct choice.

You want some kind of Map<Integer, myEdge>, most probably a
HashMap if iteration order is unimportant, or a TreeMap if you'd
like to traverse by edge ID. (There are other Map candidates, too,
but these are "the usual suspects.") Whatever kind of Map you
use, you'd insert (or update) with

myEdge edge = ...;
theMap.put(edge.getID(), edge);

.... and retrieve with

myEdge edge = theMap.get(someRandomIdValue);
if (edge == null) {
// no such thing in the Map
}

For traversals, you can iterate over the Map's values:

for (myEdge edge : theMap.values()) {
...
}

.... or you can use those newfangled Java 8 stream thingummies.

 

[Eric Sosman]

[...]
On a second, unrelated note, the style of your code is pretty far from
the Java style conventions, and if it's not throwaway code you're
writing, you should probably read through the document "Code
Conventions for the Java Programming Language" [1] and try to adhere
to it as much as practical.

[1] You can find it at
http://www.oracle.com/technetwork/java/index-135089.html

Unfortunately, the links on that promisingly-named page
are all 404's or inoperative. Bug 8039151 was filed a little
over three weeks ago but hasn't yet been resolved; I guess an
Oracle committee is preparing to start discussions on a suitable
framework and process for repairing links. If so, the links may
get repaired in time for Java 9 or 10. ;-)

 

[Jeff Higgins]

... or you can use those newfangled Java 8 stream thingummies.

Durn. Streaming thingummies on my new lambda colored glasses.

 

[Marcel Müller]

The edge ID is always unique. So I would like to create a collection in
which I can do something like

myEdge x = edgecollection.get( searching edge id )

So the collection stores the edge objects and I can get an object with
the internal id. The collection
should use the the edgeid value to identify the object.

A set should be the correct structure, but I can not get the object
itself of the map without iteration over all
items. A HashMap needs a key, value pair, so I need also a key class
which stores the edge id (redundant data).

This is a well known limitation of the Java collections. They cannot
deal with objects that have an embedded key.
There are some good reasons for this restriction. I.e. if you modify the
embedded key of an object in a container the entire container may get
inconsistent.

I'm a little bit uncertain, which collection is the correct choice.

You need a key value collection rather than a set. You can't come around
the redundant keys because of the above restriction.


Marcel

 

[markspace]

A set should be the correct structure, but I can not get the object
itself of the map without iteration over all
items. A HashMap needs a key, value pair, so I need also a key class

If you'd prefer a set, I'd just make one. It isn't that much trouble to
do so. The implementation might be a little slow, but if it gives you
trouble then you just have to optimize it more. Most time code like
this won't be the bottle-neck.

Not tested. I've renamed your get method to "findById", and you'll need
a proper hash/equals method, one that compares all fields in MyEdge, for
this to work 100%.


package quicktest;

import java.util.AbstractSet;
import java.util.HashMap;
import java.util.Iterator;

public class MySet extends AbstractSet<MyEdge>
{
private final HashMap<Integer,MyEdge> map = new HashMap<>();

@Override
public Iterator iterator() {
return map.values().iterator();
}

@Override
public int size() {
return map.size();
}

@Override
public boolean add( MyEdge edge ) { // edge @NotNull
MyEdge temp = map.get( edge.getID() );
map.put( edge.getID(), edge);
return !edge.equals( temp );
}

public MyEdge findById( int id ) {
return map.get(id);
}
}

// Dummy for compilation
class MyEdge{
public int getID() {return 0;}
}

 

[Roedy Green]

I'm a little bit uncertain, which collection is the correct choice.

Generic advice.

see http://mindprod.com/jgloss/hashmap.html
http://mindprod.com/jgloss/treemap.html
http://mindprod.com/jgloss/hashset.html
http://mindprod.com/jgloss/arraylist.html

There are comments on why you might use each one.
Avoid Hashtable,Vector. I also talk about digested HashMaps.

 

[Jeff Higgins]

Ack. My bad, apologies. I should have checked that the link
actually worked.


*wince* It's pretty bad that a document this important has gone awol.

There seems to be an old copy of it here:
http://yohanan.org/steve/projects/java-code-conventions/

The guide _is_ a little out-of-date by now, mainly in that it doesn't
cover the later language features such as generics or varargs, but
it's still worth a read through.

Not much better here. :-o
<http://openjdk.java.net/guide/codeConventions.html>
Committee having cold beer.

 

[Philipp Kraus]

Hello,

thanks for the helpful code lines, but

return Integer.compare(m_edgeid, p_edgelink.m_edgeid);

my Integer does not have a method "compare"

Phil

 

[Eric Sosman]

Hello,

thanks for the helpful code lines, but



my Integer does not have a method "compare"

Integer.compare() was introduced in Java 1.7, just under three
years ago (the current Java version is 1.8). Is there some special
reason you need to stick with 1.6-or-even-older?

 

[Philipp Kraus]

Which version of Java are you using? The Integer.compare()
method was introduced in 1.7

I'm using 1.6 (OSX)

 

[Joerg Meier]

I'm using 1.6 (OSX)

Then you should upgrade as soon as possible. As I understand, that should
be trivial for a developer even on a Mac.

Liebe Gruesse,
Joerg

 

[Arne Vajhøj]

Then you should upgrade as soon as possible. As I understand, that should
be trivial for a developer even on a Mac.

Unless he has a Java version vs MacOS X version issue.

Arne

 

[Joerg Meier]

Unless he has a Java version vs MacOS X version issue.

As far as I know, Macs can now simply download current Java versions from
Oracle and need no longer wait for MacOS to provide a newer version. If I
am mistaken I apologize.

Liebe Gruesse,
Joerg

 

[Arne Vajhøj]

As far as I know, Macs can now simply download current Java versions from
Oracle and need no longer wait for MacOS to provide a newer version.

They can.

If the MacOS X version they are running is supported by the Java version
they want.

According to Oracle "certified system configurations" then:

1.8 requires 10.8.3+ or 10.9+
1.7 requires 10.7.3 or 10.8.3+ or 10.9+

Arne