ProgrammingMethodology-Lecture19.pdf

Programming Methodology-Lecture19

Instructor (Mehran Sahami): Howdy. So welcome back to yet another fun filled,

exciting day in CS106A. I don’t know if there’s any days actually we started where I

didn’t say that. I don’t know. Someday, I should go back and watch the video. But

they’re all fun filled and exciting, aren’t they? So it’s not like false advertising. There’s

no handouts today. A little breather after the four handouts you got last time. And another

quick announcement, if you didn’t pick up your midterm already, you can pick it up.

They’re along the back wall over there in alphabetical order, so hopefully you can pick it

up if you haven’t already gotten yours. If you’re an SITN student and you’re worrying

about where you can get your midterm, it will be sent back to you through the SITN

courier, unless you come into class and you picked it up, in which case it won’t be sent

back to you because then you already have it. All righty. So any questions about anything

we’ve done before we delve into our next great topic? All right. So time for our next

topic. And our next topic is really a little bit of a revisiting of an old topic, kind of an old

friend of ours, and then we’re gonna push a little bit further. So remember our old

interface. I always love it when math books say like “recall” and they have some concept,

and I look at that, and I’m like, “Oh, recall the interface. Oh, what good times the

interface and I had, like we were holding hands and running through a garden, the

interface and I, and I recall our happy times together.” So now’s the time to recall the

interface. What was an interface? Right? Last time when we talked about interface, we

talked about something really generic, which was basically – it was a set of methods. And

this was a set of methods that we sort of designate that some sort of classes actually

shares. So it’s a common set of functionality – common functionality among a certain set

of classes.

And we talked a little bit about how yeah, there’s – if you had some notions of

[inaudible] classic standing in other class, you get sort of that same idea, but the real

generality of interface is with – that you could have certain things that weren’t related to

each other in an object hierarchy or a class hierarchy that you still wanted to have some

common methodology. And you sort of saw this all before, so in the days of yore when

we talked about G objects. Remember? Those little fun graphical objects like the GLabel

and the GRect, and all that happy stuff. And we said there were a bunch of interfaces

there. Like for example, there was an interface called GFillable, and the GFillable

interface had certain methods associated with it, like you could set something to be filled,

or you could check to see if it was filled. And we said some of the objects actually

implemented this interface, so for example, GRect, and GOval, and a couple others

actually implement this GFillable interface. And there were other things like GLabel

where it didn’t make sense to have a filled or unfilled label, so GLabel didn’t implement

this interface. Okay? And it was just kind of a set of functionality. We’re gonna kinda

return to this idea of interface to talk about some of the things that we’ve actually done so

far, like array lists, and some new concepts you’re gonna learn, and how it relates to our

notion of interfaces.

But the more general thing to take away from interfaces is in terms of thinking about how

they’re actually implemented for their syntax. Sometimes what you’ll see in the actual

code when you see that a particular class implements the methods that are considered part

of some interface, the way we write is that is we say public class, and then we have the

class name just like we usually do. So I’ll write class name here, and I’ll underline it to

indicate that this is just a placeholder for the actual name of the class as opposed to

writing class name. And then what we would write is implement – this would all

generally be on the same line, much in the same way when you’ve seen before like your

class, my program extends console program, or extends graphics program. Here we have

a notion of implements, which is an actual word in Java, and then the name of the

interface that it implements. So this over here would be the interface name. So you can

imagine somewhere in the definition of the GRect class, there is a GRect class that

implements GFillable. And GFillable is defined to be some interface somewhere which

just specifies a set of methods, and any class that implements that interface needs to

provide its own version of the methods. That’s all it means, so for a class to implement

some interface just means that that interface specifies some set of methods, and this class

provides all of those methods. By providing all of those methods, it what’s called

implements the interface. Okay? And it’s perfectly fine for a class to not only implement

an interface, but also to extend some other class. That’s perfectly fine, so the syntax is

gonna get longer up here, but I just want you to see the implements syntax.

And then inside here, just like you would be used to – actually, I’ll just draw the opening

brace here and inside here – this would be all of your code for the implementation of the

methods would go in there. So it’s the same kind of syntax for writing a regular class, but

now you’re just specifically telling the machine, “Hey, this class is gonna support all the

stuff from some particular or other interface,” like GFillable or whatever the case may be.

Okay? So that’s kinda the concept. Now why do we sort of revisit this idea of interface is

that now it’s time to talk about some new things and the interfaces that they actually

implement. So any questions about the basic notion of an interface or implementing an

interface? Good call on the microphone.

Student: How’s this different from – does this work?

Instructor (Mehran Sahami): Sure. Just press the button. We’ll pretend it’s working.

Student: How is this different from extending a class or just calling it an instance of

another class?

Instructor (Mehran Sahami): Right. So that’s a good question. The difference between

this and extending a class is for example the notion of a hierarchy that we talked about.

So if we have some class that extends some other class, we basically say, right – like

when we talked about – remember in the very first day – primates and all humans are

primates? We would basically say any human is a primate. The difference is there might

actually be some things that are not primates, and humans may actually implement a class

like the GIntelligence class, which means you have a brain that’s larger than a pea or

something like that. It turns out there’s this other thing over here called the dolphin which

also implements the Intelligence class. Right? We generally like to think of dolphins as –

a point of debate. I don’t how they actually measure this. There’s like the dolphin SAT or

something, the DSAT, and they’re like [inaudible] – I don’t know how they do it, but

evidently someone has figured out how to measure intelligence in dolphins.

So you could say this dolphin class actually implements the methods of being intelligent,

which might be some method like it responds to some stimulus in the world, but a

dolphin’s not a primate, so – at least as far as I know. Dolphin’s not a primate, so there’s

no extends relationship here, and that’s the difference. Right? So an interface in some

sense provides more generality. When you extend the class, you’re saying there’s a direct

hierarchical relationship among those objects. Interfaces, you’re just saying there’s this

thing like the intelligence interface, and sometimes these get drawn with dash lines when

you see them in diagrams. Both humans and dolphins provide all the methods of the

intelligence interface, but only a human is a primate. That’s the difference. Okay? So any

other questions? Uh huh?

Student: Is the code in this instance the code for that particular class or the interface?

Instructor (Mehran Sahami): Pardon?

Student: You wrote code there as in – is that the code for that class or for the interface?

Instructor (Mehran Sahami): Yeah. So the code here is the code for class name, and

somewhere else there would actually be the code for the interface. And that’s covered in

the book. We’re not actually gonna be writing an interface together, which is why I’m not

showing that to you here in detail, but the basic idea is just so that you would actually see

that when a class implements an interface what that syntax would look like. Uh huh?

Student: Can you implement more than one interface?

Instructor (Mehran Sahami): Yes. You can implement multiple interface. For example,

GRect implements both the GFillable interface and the GResizable interface, and that’s

perfectly fine. It’s a good time. All right, so let me move on a little bit and talk about

something that we’re actually gonna deal with which is an interface, which is why we

kinda revisit the subject. And the particular thing we’re gonna talk about is something

that’s known as a map. Okay? So a map – and you might look at this, and you’re like,

“Map? Is that like oh yeah, the travel guide, like I got one of these, and I kinda look in

here, and I’m like yeah, where was I going? Oh, here’s a map of all the interstates on the

United States, and I’m sure this is copyright, mapquest.com. There’s this map, right? Is

this what you’re talking about?” No. This is not at all to do with what I’m referring to

here as maps.

So when you think of the word map, you need to let go of what your previous notion of

what a map might have been is, and think of the computer science notion of a map. So

basically, all a map is – it’s an interface in Java, which means it’s some collection of

methods that will implement some functionality. What are the methods? What is a actual

map? What does it do? The way to think about a map is there’s two key terms you wanna

think about for map. One is called the key, and one is called the value. And basically, all

a map is is it’s a way of associating a particular key with a particular value. You might

say, “Whoa, man. That’s kinda weird.” Yeah, that’s a very abstract idea. So let me give

you an example of a map that you’ve probably used throughout the majority of your life,

but no one told you up until now that it was map, something called the dictionary.

Anyone ever use the dictionary? The number’s getting smaller and smaller. No, I just let

my word processor spell correct for me. A dictionary is a map. Its keys are the words that

exist in the dictionary, and the values are the definitions of those words. So what a

dictionary gives you is the ability to associate a particular key with a value. It associates

words with their definitions. And the important idea to think about a map is in a map

what you do is you add key value pairs – so like in a dictionary like the Oxford English

Dictionary, right every year there’s a little convention, and they actually figure out some

new words that are considered part of English, and they add them to the map that is the

OED.

Anyone have a copy of the OED? Yeah, a couple folks. It’s a good time. Just get it. You

get the little magnifying glass version where it’s got like four pages on one page, hurts

your eyes, but it’s a good time. That’s what it is. We’re just adding key value pairs. Now

what you do in a dictionary is when you look things up in a map, you don’t look them up

by the value. Right? It would make no sense if I told you look up the word for me that

has this as its definition. You’d kind of be like, “Yeah, Mehran. That’s just cruel and

unusual.” The way a map works is you look things up by their key. You have a particular

word in mind in a dictionary, you go to the dictionary, you look up that word, and then

you get its corresponding definition. Okay? So what we like to think of a map in this

abstract way it’s an association. It’s an association of a key to a value where when we

enter things we enter both the key and the value together, and when we look things up,

we look things up by saying get me the value associated with this key. Okay?

So dictionary’s a simple example of that. There’s other examples. Your phone book is

same thing. It’s a map. The keys in the case of your phone book happen to be names that

you wanna look up, and the values in the case of your phone book happen to be phone

numbers, but it’s also a map. There’s maps kind of all around you. Everywhere in life,

there’s a whole bunch of maps. No one told you they were maps before. And if I told you

all before this class started, “Yeah, a dictionary and a phone book are really the same

thing,” you might kinda look at me sorta weird and be like, “No, Mehran. One is like

storing names and numbers, and the other one’s storing words and definitions.” But when

you tell this to a computer scientist, they’re like, “Yeah. They’re both maps,” because

now you know what a map is. All right. So any questions about the general idea of a

map? Uh huh?

Student: [Inaudible].

Instructor (Mehran Sahami): As far as we’re dealing with right now, you can think of a

key having just one value, but that value is really some abstract notion, right? So you

could actually think we have some word – like let’s say we have a dictionary that has

multiple definitions. Its key could be a word. Its value could be an array of definitions. So

really, in the philosophical sense the value is one thing. That one thing happens to be an

array that stores multiple values. So philosophically it’s one thing. In terms of the

practicality of what you’re storing, you might actually be storing multiple things. And oh,

maybe for Assignment No. 6, you might actually do something like that, but that’s not

important right now because you’re still working on Assignment No. 5. All right? So

[inaudible] something, you’re like, “Quick. Write that down.” Yeah, we’ll talk about it

again when we get to Assignment No. 6. All right? So map is a particular interface, so

that means we need to define some class that actually implements this interface, that

provides some notions of these key value abstractions for us, and so in Java we have

something called a hashmap. Okay? A hashmap is an actual class. It is a class that

implements the map interface, which means everything that is a hashmap implements

map. Okay?

Map is not actually a class in itself. Hashmap is a particular class. Map is just a set of

methods that I think are actually useful to have. Now where did it get its name? Why do

we call it a hashmap? What’s this hashing thing all about? And in the book in

excruciating detail, it talks about hashing, what hashing is, and how to implement

hashing, and hash codes, and all this other stuff. You don’t need to know any of that for

the class. All you need to know is how to use a hashmap. You don’t need to build a

hashmap. If you wanna build a hashmap, in CS106B a couple weeks from now, you will

build a hashmap. You will have the joy of seeing the underlying implementation of

hashmaps in C++ of all things. But for right now, you just don’t need to worry about it.

The reason why it’s called a hashmap is it uses a particular strategy to store these key

value pairs called hashing. That’s all you need to know, and because it’s called hashing,

we call it a hashmap. That’s life in the city. Okay? But so this particular hashmap is a

template. Right? Remember we talked about templates, and we talked about how the

array list was a template, and you could have an array list of strings, or you could have an

array list of integers, or whatever the case may be. A hashmap is also a template, but the

key here is there are two types involved. It’s like two scoops of raisins. You have two

types involved in the template for a hashmap. You’re gonna have a type for your keys,

and you’re gonna have a type for your values. So what does that actually look like in

terms of syntax? Let me create a hashmap for you.

Now that you know all about interfaces, we can erase this part. So let’s create a hashmap.

The class is called hashmap. Because it’s a template, it has this funky angled bracket

notation, but it’s gonna have two parameters for two types for this templatized class. The

first type is what are you gonna have for your keys. So let’s say we wanna implement a

dictionary. A dictionary for its key type is gonna have strings because it’s gonna be

words. What type – the next type – so you have a comma in here, and then you specify

the next type, the type for your value. For a dictionary again, if we assume a simple

definition rather than multiple definitions which could be an array, we’ll also just gonna

have a string for the value type. So hashmap string comma string, or sometimes we refer

to this as a map from strings to strings because it maps from keys to values is how we

would actually specify this. We need to give it some name, so we might call this “dict”

for dictionary, and then this is going to – we are gonna create one by saying a new

hashmap – and this is where the syntax gets a little bit bulky, but you just have to stick

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: