Thursday, October 19, 2006

Hash Tables

Topics

• Hash tables create an integer index out of non-integer data
• Possibility of collisions
• Kinds of hash functions
• Chained hash tables versus open addressing (not covered in the book)
• Buckets in chained hash tables and the underlying data structures
• Searching efficiency -- can be O(1)
• Sorting efficiency -- theoretically close to O(n), but not usually that good in practice    

Readings

Chapter 17, Sections 17.1, 17.2, 17.3, 17.4 (lightly), 17.6.  Skip 17.5.