Differences between version 2 and revision by previous author of HashTable.
Other diffs: Previous Major Revision, Previous Revision, or view the Annotated Edit History
| Newer page: | version 2 | Last edited on Monday, August 11, 2003 2:07:43 pm | by JohnMcPherson | Revert |
| Older page: | version 1 | Last edited on Saturday, July 27, 2002 1:58:55 pm | by PerryLorier | Revert |
@@ -1,5 +1,5 @@
-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.
+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
