Re: Arrays as key in a HashMap

Chris Smith wrote:
tom fredriksen <tom@xxxxxxxxxx> wrote:
Chris Smith wrote:
The point that any necessary complexity can be encapsulated behind the contract for Object.equals and Object.hashCode.
Just because you have a contract about an interface, and it can be kept constant, does not mean that the code behind it needs to be as complicated as you can manage, or want to, create it. Thats the key to low complexity/high maintainability code.

Can you solve that problem with less complexity, or do you just move the complexity elsewhere? Somewhere, you've got to have code that compares two graphs for equality. The hash code is, of course, an optimization to avoid a linear search... but it's an even more welcome optimization when the graphs are so expensive to compare.

Of course somewhere you have to have the logic to perform the operations you need done. And using equals() to initiate a comparison of two graphs is as good as any.

But, using a hash code of the graph as a unique identifier of the graph is not the way to go, as you then have to take into consideration many factors that are quite complex, such as

- the complexity of the graph,
- a correct algorithm to produce a representative hash code for the
type and complexity of the graph,
- accuracy of the representation,
- collision rate of the hash code
- distribution properties of the hash code, when considering the accuracy, collision rate etc

I would try to look for another piece of simple information about a graph that can be used as a unique identifier.

/tom
.

Relevant Pages

  • Re: kung fu mereotopology
    ... the algebraic approach to computational complexity ... because the homology of graph complexes ... that much of the operad theory on which this is built ... that ties their algebraics to more classical work on matroidshttp://www.springerlink.com/content/y60n827057m374n8/ ...
    (sci.math)
  • Re: kung fu mereotopology
    ... Can you point to a sentence of Kontsevich related to ... the algebraic approach to computational complexity ... because the homology of graph complexes ... that ties their algebraics to more classical work on matroids ...
    (sci.math)
  • Re: Graph Theory: Cutting a Graph into Two in an Artificial Chemistry
    ... I start with a graph that has a single connected component (such that ... then I count that as a valid way that my original graph ... The set of all 'valid' splits from is the answer I want. ... It would probably be useful to know the size and complexity of the ...
    (sci.math)
  • Re: Algorithmic complexity of a graph
    ... > Does by chance anyone know of a definition of the ALGORITHMIC (or ... > I have only found definitions of computational complexity... ... bits necessary to describe a graph in such a system - for instance you ... the number of spanning trees is often called the "complexity" ...
    (sci.math.research)