I am trying to code a sokoban solver, My code works, but it takes so much time to calculate the solution. I think it's because I use ArrayList, I tried to use Hashtable but the method get does not work,

Hashtable < Vertix, ArrayList<Vertix>> Graph;

so when I fill my hashtable, and use the key to get the list I get null.

Graph.get(new Vertix(5,3));

however the vertix exists in Graph.

how can I solve this problem to increase the speed of my Sokoban solver.

CodePudding user response：

Is Vertix your own class? If so, it needs to have a definition of equals and hashcode methods to be compared against other instances with matching values.

Otherwise, the new reference you've created doesn't exist in the table.

Also, unless you need thread safety, you can just use Hashmap

CodePudding user response：

You should read the javadocs for HashMap and HashTable where it explains how lookups are performed, and the requirements on the hashcode and equals methods.

The most likely explanation for your problem is that your Vertix class doe not override Object::equals and Object::hashCode. Therefore, your class is inheriting "equality means same object" behavior from java.lang.Object. In other words, every Vertix instance is not equal to every other Vertix instance. Thus

    new Vertix(5, 3).equals(new Vertix(5, 3)) 

evaluates to false. That would explain why Graph.get(new Vertix(5,3)) returns false.

Solution: override equals and hashCode so that they have the correct properties for your application.

Reference:

• Java equals() and hashCode() Contracts

Note that there are some style, etc errors in your code snippets.

• You probably should use HashMap instead of Hashtable. Hashtable is notionally thread-safe, but this comes at the cost of acquiring and releasing a lock on each get and put. If your code is single threaded, this is unnecessary. Conversely, if your code is multi-threaded, then a Hashtable is liable to be a concurrency bottleneck.

• Graph is a variable name, so it should start with a lowercase letter.

• Vertix is probably a spelling error. The English word for a node in a graph is "vertex", not "vertix". ("Vertix" is a trademark for a GPS watch, a multiplayer shooter game, etcetera.)