Recitation 6
From 6.006: Introduction to Algorithms
(Difference between revisions)
| (3 intermediate revisions by one user not shown) | |||
| Line 1: | Line 1: | ||
| + | == Can we hash in constant time? == | ||
| + | |||
| + | If your object is of constant size (like a 32-bit integer, or an English word) then you can hash in constant time. | ||
| + | |||
| + | If, however, your object is large (like a large python integer, or a DNA string) then hashing takes time linear in the size of the object. | ||
| + | |||
| + | == Python Internal Hash == | ||
| + | |||
[http://courses.csail.mit.edu/6.006/fall07/source/alg_hash.py python hash (reimplemented)] | [http://courses.csail.mit.edu/6.006/fall07/source/alg_hash.py python hash (reimplemented)] | ||
| + | |||
| + | We went over how python hashes: | ||
| + | * ints | ||
| + | * strings | ||
| + | * tuples | ||
| + | |||
| + | == Mutability == | ||
| + | |||
| + | Python does not allow you to put lists in dictionaries, because they are mutable. | ||
| + | |||
| + | == .__hash__() == | ||
| + | |||
| + | We gave a simple example of how to implement a hash function in your own class | ||
Latest revision as of 21:54, 30 January 2008
Contents |
Can we hash in constant time?
If your object is of constant size (like a 32-bit integer, or an English word) then you can hash in constant time.
If, however, your object is large (like a large python integer, or a DNA string) then hashing takes time linear in the size of the object.
Python Internal Hash
We went over how python hashes:
- ints
- strings
- tuples
Mutability
Python does not allow you to put lists in dictionaries, because they are mutable.
.__hash__()
We gave a simple example of how to implement a hash function in your own class
