Alboin wrote:hckr83 wrote:I have no idea what hash tables are(checksums?)
They're also known as associative arrays. (ie. $hash["cat"] = "meow"; )
Ofcourse hash tables are sometimes a good data-structure even if you don't need to use strings as keys...
Hash tables work by "hashing" a key into an array index, such that you don't need an array as large as your potential key-space. A trivial, although not necessarily good hash function for integers would be (key modulo table-size). Their advantage over something like linked-list is that they have the same complexities as arrays, at least in theory: as long as you can hash each key into a different value, you can access each element directly. If several key's hash to the same value, you have a collision, which can be handled by storing a (hopefully short) linked list in each array cell (instead of a single value) and then searching this list, by having a secondary hash function to hash again until no collision occurs, or by simply allocating a bigger table as soon as there's a collision (or some combination of the previous).
Simply allocating a new table has the disadvantage that in the worst case you could end up with almost as big array as with no hashing at all, so usually that's not a good strategy. The multiple-hashing strategy is good, if the secondary hash and the table sizes are well chosen, and the table is grown before it becomes too full, but removal needs to be done lazily and searching for a non-existing key becomes a bit more expensive. Finally the linked list version has the nice property, that in theory you never need to grow the table, your performance just drops if the chains grow too long.
There are some variations, but the basic idea is a data-structure which behaves like an array, but allows sparse key-space.
The real problem with goto is not with the control transfer, but with environments. Properly tail-recursive closures get both right.
