6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.3.20 Lessons so far Here is a summary of the key messages from this part of the Association list structure can represent the table aDt lecture The data abstraction technique(constructors, accessors, etc)exists to su mation hiding Information hiding is necessary for modularity 6.001 Notes: Section 10.4 Now let's look at how the data abstraction allows us to alter theHash tables Slide 10.4.1 Suppose a program is written using Table 1 nternal representation of tables, without affecting any consumer. Suppose we measure that a lot of tir spent in of tables. This, after all, has been our key point all along tablel-get To motivate this, suppose we build a table using our existing Want to replace the implementation with a faster one abstraction, but then observe that most of the time spent in using the table is actually spend in the get operation. In other words as you might expect, we spend most of our time retriving information from the table, rather than putting things into the table. If this is the case. it would be nice if we could devise an implementation in which get operations are very efficient, while preserving all the contracts of the table Slide 10.4.2 Hash tables In fact, there is a standard data structure for fast table lookup Suppose a program is written using Table 1 called a hash table. The idea behind a hash table is to keep a Suppose we measure that a lot of time is spent in bunch of association lists, rather than a single one. We chose which association list to use. based on a function called a hash function Want to replace the implementation with a faster one That hash function takes our key as input, and computes a number between 0 and the number of a-lists that we are using. and that standard data structure for fast table lookup: hash table number will tell us which a-list to use to look up a value eep n association lists instead of 1 You should already begin to see why this idea should lead to a . choose which list to search using a hash function iven the key, hash function computes faster implementation. Rather than having to search one big a-list number x where<=X <=(N-1) to find a pairing, we should only have to search a much smaller a list. This should be faster, so long as the cost of computing the hash function is not too large6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.3.20 Here is a summary of the key messages from this part of the lecture. 6.001 Notes: Section 10.4 Slide 10.4.1 Now let's look at how the data abstraction allows us to alter the internal representation of tables, without affecting any consumer of tables. This, after all, has been our key point all along. To motivate this, suppose we build a table using our existing abstraction, but then observe that most of the time spent in using the table is actually spend in the get operation. In other words, as you might expect, we spend most of our time retriveing information from the table, rather than putting things into the table. If this is the case, it would be nice if we could devise an implementation in which get operations are very efficient, while preserving all the contracts of the table. Slide 10.4.2 In fact, there is a standard data structure for fast table lookup, called a hash table. The idea behind a hash table is to keep a bunch of association lists, rather than a single one. We chose which association list to use, based on a function called a hash function. That hash function takes our key as input, and computes a number between 0 and the number of a-lists that we are using, and that number will tell us which a-list to use to look up a value. You should already begin to see why this idea should lead to a faster implementation. Rather than having to search one big a-list to find a pairing, we should only have to search a much smaller a￾list. This should be faster, so long as the cost of computing the hash function is not too large