
Title:
Hash Function  Intro to Computer Science

Description:

So let's try to define a hash function

that has these properties. And what we want the

hash function to do is to take a string

as its input, we'll call the hash function hash_string,

and it'll produce as output a number between 0

and b. So, we also need another input to

our hash string, which is going to be the size

of the hash table. So that'll be the second

input is the size of the hash table, the

number of buckets. What we haven't seen yet, that

we're going to need for this function, is a way

to turn a string into a number. Python provides an

operation to do that. It's called ord as an

ordinal, and what ord takes as it's input is

a one letter string and produces as it's output

a number. And actual mapping between strings and numbers is

not so important. We just want something

that is going to map different string to

different numbers. There's another operator that goes in

the opposite direction that takes in a number,

and outputs the oneletter string that corresponds to

that number. And the property these functions have

is their inverses. That if we take the

character corresponding to the ordinal corresponding to any

oneletter string. We'll call that alpha. What we get as a result is the same

alpha that we passed in. So let's try

a few examples in the python interpreter to

see how ord and chr work. So we'll print ord of a, and

when we run that we see we get the number 97. If we try print ord of capital A.

That's different. We get 65. And if we print ord of B,

we get 66. So, the numbers are sort of sensible.

B is higher than A. The lower case letters have

different ordinals than the upper case. So, if we try

a lower case b, we should expect to get 98.

And that is indeed what we get. And these are

the numbers based on the ASCII enchar, character encoding, what

the actual numbers are, are not very important for us,

other than that we get different number for different letters.

So we'll be able to use the results

of ord to make different strings hash to different

values. And just to show that there are inter, inverses. If we do ord of u, and

then chart of that, what we get back

is the single letter string u that we started

with. The limit of ord is it only works

on oneletter strings. If it provided a mapping from

any string to a number that would be useful for a

hash table. Well, then we'd be done. But it doesn't do that.

If we try running it on a multiletter string, we get

an error. It says that ord expects a single character, but it

got a string of length 7. So we're going to need to

use ord only on single letter strings. So with ord, we have

a way of converting strings to numbers. Converting single character strengths

to numbers. The other property we need our hash function to have,

is that our output number is always between 0 and B minus 1. We need it to be in

that range, because we're going to use that to index

the list, to find the bucket where that string belongs.