How much do you trust the Collection class?

[DEXWERX]

@Elroy - If you're questioning how my implementation "could" work - you haven't comprehended how it does work. It's the tiniest and simplest hashtable implementation I could possibly imagine.

I just don't see how this hash-table approach is going to help with an unsorted list. If (or, rather, when) a key hashes to the same hash-code, creating duplicate hash-codes, things get complicated. With your scheme, here's what'll happen:

• We'll get a hash-code from our key. Yes
• We'll get an index value from the hash table. <--- No, We get and Index Into the Array from the Hash Function
• We'll use that index value to spin to an entry in our doubly linked list. No... we have an index into an Array, IE a direct memory location. No spinning involved. This is where all the "performance" comes from. Translating a Hash into a direct memory location without searching.
• We'll check the list's key value with the key value we want. Yes
• It won't match, but then, we'll have no idea where the key value is that we want. We won't even know if it's in front of us or behind us. <-- We will because it's in front, it's always in front in this implementation, It's in a following slot in front of the already populated one if theres a collision.
  

Good questions, I guess I forget that things implied by the code still aren't obvious to the uninitiated. Tanner's linked directly to the relevant Wikipedia section on chaining. Our hash function finds the bucket, and if there's a collision, the retrieval checks whatever else is in the bucket. For simplification - The implementation I posted just treats the whole table as a single bucket, and uses the hash function to get close. The point I was trying to illustrate was the importance of using the Hash Function to get to a spot in memory that is close (or exactly where our Entry lives.)

FYI: The only reason the Collection class maintains a linked list, is to iterate over the entries in order, and to find entries by index. This is exactly why the Collection class is so slow at retrieving entries by index. A Collection doesn't have a choice on how to search by index, except to traverse the entire list forward or backwards.