6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 10.4.3 What does a hash function look like? As noted it should take as Example hash function input a key and compute a number between 0 and N, for some fixed N As an example, suppose we have a table where the keys are points, i.e. x and y coordinates of points in the plane, such as the points we might use in a graphics display. Associated with each point will be (10.6)( square8) some graphic object that passes through that point Example hash function For example, if in my graphics system includes I want to move A table where the keys are points some object on the screen, I would like to know which points are graphic object covered by that object, as I am going to have to redraw those (5.5) (circle 4 points. a nice way to do this is to take a point and find all the 0,6) bjects that cover that point, so I want to use the point as my key So how could we design a hash function that takes points as input and returns a num ber between o and N Slide 10.4.5 Here is a particular example. Given a point(represented by someExample hash function data abstraction)and a specified number N, we can add the x and y. A table where the keys are points coordinates of that point and find the sum's remainder modulo N graphic object Remember that this means finding the remainder of the number after dividing it by N Note that a good hash function is one that evenly distributes its (10.6)|( square8) keys among the values between 0 and N. For this case, if the points(define chash-a-point point N) re uniformly distributed in the plane, the result will be a nearly (modulo (+(or-coor point)(y-coor point)) uniform distribution of output values of the hash function odulo x n the remainder of x, n 0←( modul。xn)<n-1 for any z Slide 10. 4.6 Hash function output chooses a bucket So a hash function basically chooses a bucket(out of a fixed set of buckets)into which to put an object or from which to extract an6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 10.4.3 What does a hash function look like? As noted, it should take as input a key and compute a number between 0 and N, for some fixed N. As an example, suppose we have a table where the keys are points, i.e. x and y coordinates of points in the plane, such as the points we might use in a graphics display. Associated with each point will be some graphic object that passes through that point. Slide 10.4.4 For example, if in my graphics system includes I want to move some object on the screen, I would like to know which points are covered by that object, as I am going to have to redraw those points. A nice way to do this is to take a point and find all the objects that cover that point, so I want to use the point as my key. So how could we design a hash function that takes points as input, and returns a number between 0 and N. Slide 10.4.5 Here is a particular example. Given a point (represented by some data abstraction) and a specified number N, we can add the x and y coordinates of that point and find the sum's remainder modulo N. Remember that this means finding the remainder of the number after dividing it by N. Note that a good hash function is one that evenly distributes its keys among the values between 0 and N. For this case, if the points are uniformly distributed in the plane, the result will be a nearly uniform distribution of output values of the hash function. Slide 10.4.6 So a hash function basically chooses a bucket (out of a fixed set of buckets) into which to put an object or from which to extract an object