Re: Using a lot of Maps
On 11/22/2010 7:59 AM, ses wrote:
So I find myself using rather a lot of maps in my latest piece of work
to represent nested objects e.g:
HashMap<Integer, HashMap<Integer,String>>
Where for example the first and second integers are attributes and
string is some value that an Integer-Integer combination corresponds
to. I only ever need to really put and get the String value based on
the Integer attributes, but it seems a more effective tree like
structure than using a custom data structure and having to iterate
over it.
My question is, should I be worried about using maps in this manner,
would a custom data structure be better? I think I'm becoming too used
to using them.
Possibly. I think (and this is just offf the top of my head) that one
problem with this approach is that you might end up with a lot of deeply
nested Maps:
HashMap<.., HashMap<.., HashMap<.., HashMap<..,..>>>> ....
And that's going to turn what could have been a single lookup O(1) into
a linear search O(n). It might be better to find a representation of
the key and value that allows you to look up a deeply nested value in
one go.
HashMap<Integer,Heirarchy> cache = ....
where Hierarchy is something like (code not compiled or tested):
class Hierarchy {
private final ArrayList<Object> hierarchy;
private int hash;
public Hierarchy( Object... parents) {
hierarchy = new ArrayList<Object>( parents.length );
for( Object o : parents) {
hierarchy.add( o );
}
}
@Override
public int hashCode() {
if( hash == 0 ) {
for( Object o : hierarchy ) {
hash = hash * 53 + o.hashCode();
}
}
return hash;
}
public List<Object> getHierarchy() {
return hierarchy.clone();
}
@Override
public boolean equals( Object ...
should override this
didn't need it for the example
}
This will let you make an entire hierarchy into one object, so it can be
looked-up in one go. I think this helps on both reads and writes, since
you don't have to search for a place to put it into a nest of Maps, or
make new Maps on the fly to hold new children.
As Tom said though I'd like to hear more about your use model for this
application. I don't think I've ever considered doing what you did, so
I'm unsure what sort of things one could or should do with it.