I'm creating a chess program that utilizes a hash table of previously evaluated positions to (hopefully) reduce search time. Only problem is I'm using an ArrayList to store the hash values and the lookup time increases based on how many positions i've stored. How can I get a hash table which has a lookup time independent of it's current size? (Forgive me, I'm kinda a noob at java, objective c is really my thing)
Edit: If it matters, I'm using the Zobrist fast hashing technique. Based on some trials, I've determined that it is NOT the generation of the hash keys that takes up the large amount of time. The hashing methods is very fast and its effect on the speed is almost unnoticeable.
java.util.HashMap is your best bet. Key lookups are O(1) (amortised) and it's a very good general purpose HashMap.
That's not to say that it is optimal: you could certainly design a custom hashmap implementation to be better for your special case if you know how and have a lot of time/determination. But a regular HashMap is definitely the place to start - you can always optimise later.