An Algorithm where you take a Hash of a key, and then index it into a lookup table to find the value. You can get HashCollisions when two keys hash to the same value, in that case you peturb your hash and put it somewhere else in the array (which I think is really ugly), or you can have your lookup table being a linked list of (key,value) pairs, which you walk.
HashTable's have approximately !O(1)?1? lookup with a good Hash value.
1?: See ComplexityTheory
4 pages link to HashTable:
