Deprecated: (6.006) preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /afs/athena.mit.edu/course/6/6.006/web_scripts/spring08/wiki/includes/Sanitizer.php on line 1470
Recitation 5 - 6.006 Introduction to Algorithms

Recitation 5

From 6.006 Introduction to Algorithms

Jump to: navigation, search

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

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

Personal tools