Essentials: Brian Kernighan on Associative Arrays - Computerphile

[@ThePandaGuitar]

Pizza: 10 POUNDS! Beer: 20 POUNDS! Coffee: 2 POUNDS! Beer: 20 POUNDS! You go Kernighan, that's the spirit!

[@DavidChipman]

I see a Computerphile video featuring Brian Kernighan, I must drop everything and watch and "thumb-up". I'm a simple guy.

[@eugenesarce3997]

tg

[@leninalopez2912]

I love Brian's voice, and how gentle and methodical he is when explaining things

[@Hyreia]

I definitely fell in love with associative arrays in my Data Structures class in college. Between these and linked lists you can build just about everything.

[@jerichaux9219]

@@myspace_forever That’s an imported library. Built under the hood with associative arrays and linked lists.

[@498fun]

It makes me so happy to get some more lectures from my favorite prof even all this time after graduating. Not many people can be this entertaining and this informative at the same time!

[@landspide]

A legend that truly understands 'the programmer'

[@loadedfries5764]

This was a really great video! The way I get it, the value of a hash table is that it's flexible and, as the Professor Kernighan noted, has almost constant time. You can use any type of data as the indexing element, thanks to the hashing function, and you almost always go through the same number of steps to access any data in the array, which is very different from--for example--a search function. And it's probably easier to read and understand in code. The only downside I see is that a hash table can be inefficient in terms of how much memory is used.

[@tscoffey1]

It is the classic "cpu time" versus "memory used" trade-off in computer science.

[@dmitripogosian5084]

Access time in terms of caching seems inefficient as well

[@allluckyseven]

One thing in common between most if not all of these videos is that it is such a delight to listen to these experts talking about things in their respective areas.

[@azerotrlz]

hashmaps are one of many ways to implement the associative array abstract data type. some of the most famous alternatives would be tree maps, implemented using self-balanced or unbalanced binary search tree, or associative lists, implemented using linked lists.

[@jan_harald]

40th I love this legendary man... truly legendary, too bad I'm never gonna meet him in person...

[@JahMusicTube]

I'd have loved to have him as a professor! Very clear explanation :)

[@DJstarrfish]

Too bad this series came out too late to interview Dennis Ritchie. RIP.

[@treyquattro]

Ken Thompson is still with us...

[@nicolareiman9687]

@@treyquattro ken doesn't like the interviews.

[@linuxelf]

Very interesting. I'd never studied how these structures were stored internally, and now I finally understand why data stored in a hash is stored in a somewhat random looking order.

[@sebschrader]

Map is also a common name for this data structure

[@JugglingGamer]

Sebastian Schrader he did mention that associative arrays can be referred to as [Hash]maps.

[@sebschrader]

I just rewatched it and didn't hear him say it. He mentioned only hash table, hash and dictionary.

[@JugglingGamer]

Sebastian Schrader my bad, I must've misheard!

[@unvergebeneid]

Although for C++, it's important to remember that map is usually some form of binary search tree and unordered_map is a hash map.

[@sofia.eris.bauhaus]

object. B)

[@AvailableUsernameTed]

Larry Wall: Doing linear scans over an associative array is like trying to club someone to death with a loaded Uzi.

[@JoeRobertshaw]

Elegantly put.

[@oysteinsoreide4323]

I'm using hash tables all the time in my code. In C# they are called Dictionary. Very useful collection type indeed.

[@brucewaters1617]

this guys shopping list Beer Pizza Coffee Beer

[@Riff.Wraith]

£134 worth of coffee at that, hooooly

[@498fun]

Classic Kernighan examples :D

[@knife_wizard]

Eh. Sounds like your average programmer.

[@noredine]

you forgot beer

[@jeffirwin7862]

+noredine Sorry I forgot, I'm blaming this one on the beer.

[@dustinjohnson6302]

he's a young Dumbledore of programming wizardry

[@donaldkjenstad1129]

We were doing this type of algorithms back in the early 80's to manage memory allocation for paging systems.

[@CakeIllusion]

Can Kernighan please explain the Lin-Kernighan heuristic?

[@gggfx4144]

When he was talking about pounds, I initially wasn't sure if he meant weight or currency, so I was thinking "he buys 20lb of beer and pizza?!; programmer for life"

[@grn1]

Maybe that's my problem, I don't like beer.

[@andresilveirah]

Awesome idea to bring this "Essentials" series, specially for us who have seen all this some time ago at University.

[@typograf62]

Some "administrative" programming languages have "temporary database tables". They are not committed to disk, they are private, they do not bother much about the overhead of behaving like a database table. But they do such a job just fine (or better) and you do not have to invent a hash function or copy data when things get crowded.

[@absurdengineering]

typograf62 These days all languages that have sqlite bindings automatically get “temporary database tables”. In .net you also get DataSet.

[@afelps9515]

An episode about character sets and encoding algorithms would be interesting.

[@-rikishi-]

Let's make a hash table JESSY!! -Misteeeer Kernighan, this is the purest blue linted code i've seen!

[@AmnonSadeh]

7:35 the marker pen makes its sound even when not being used :-o

[@dec2]

How the heck did you catch that!? Please teach me how to sorcerer.

[@X_Baron]

Are you claiming that it's a magic marker?

[@reallyWyrd]

In perl it's actual '%' not '#'. '#' is for comments instead. But yeah perl has hash tables as a basic data type. That always seemed very weird to me, but now I get it. Up until now, I simply could not understand how something seemingly so elaborate could be said to be efficient or quick. I get it now.

[@sowellmemo]

" Maybe beer collides with pizza. I mean they go well together! "

[@ThunderAppeal]

When BK looks in to the camera i feel as if he's speaking directly to me. As if I'm Neo from The Matrix.

[@rrp2600]

I have used PERL hashes before but I don't think I really grasped the inner workings of them until watching this 10 minute video.

[@MegaGreenLightning]

Please also make a video on Open Addressing, which is another way to implement associative arrays.

[@idivideby0096]

I work with these every day. Very common in the medical industry.

[@patricknelson]

As a programmer myself, I figured I might not learn much, but I didn’t realize hash tables utilized linked lists under the hood.

[@leonhrad]

If you care about performance you should consider not using collision lists, but keep the array flat (each element contains the actual (key,value) pair instead of a pointer to a list) and use linear probing. It's usually faster. You only need to be careful where to insert new elements and how to remove elements. You can then even separate the (key,value) array in two arrays, one for the keys and one for the values which is especially useful if you're iterating a lot and you're mostly interested in the keys for example.

[@cad97]

(Or even better, just use the builtin)

[@kmac499]

key value pairs. oft derided by comp sci and database guys is a natural way to handle data.

[@PixelOutlaw]

It's one step further when your associative array can have different types of key. At that point you can model OOP at some level. :) Not that is the most efficient to do it that way. But it's a fun diversion.

[@mdmenzel]

Are tuples implemented in the same way by programming languages that have them?

[@bobi97bg]

For anyone just getting into the java world, if you are going to use a Hashtable somewhere, its probably better to use a HashMap instead. More details can be provided by google/stackoverflow.

[@IceMetalPunk]

In Java, they're called HashMap. In Javascript, plain, anonymous objects are used for this purpose. (Also, fun fact: in Ruby, the operator that associates a key with a value, =>, is called a "hash rocket".)

[@BrianFrichette]

IceMetalPunk in JavaScript, there's been Map and WeakMap for a couple years.

[@jasonmathew33]

The foundation of many efficient algorithms :)

[@eliastandel]

These are so essential that In Lua hash tables (called tables in the language) are the only data structuring mechanism, ie.e there are no lists, sets etc., only hash tables.

[@jabuci]

What assoc. array library should I use for C? If I don't want to implement it each time, what do you suggest?

[@zoranhacker]

We only know that the value for pizza is in some location because the hash of pizza gives the "address" (not sure if it's literally the address), right? So if there is a collision with another value and we expand the linked list how exactly would we differentiate between the two values?

[@kpjVideo]

Associative arrays are especially useful when trying to conserve time and space. Otherwise, you'd be enumerating local variables quite a bit

[@timc3600]

I wish I had a tenth of his knowledge. I came across hashes in PERL and thought wow as they are so logical but I never thought about how they worked under the hood.

[@cmdlp4178]

I think you should write specific hashingfunctions for specific applications, like you make a hash out of a string, while only adding the position of the letters in the alphabet instead of the unicode-id. Why don't you split associative arrays into associative key-array and data-array, where you can reuse the key-array on other data-arrays, as you making a struct in C(++) and the key-array to access a specific member (which is "inlined" into code by the compiler) is not stored within the struct.

[@franciscogerardohernandezr4788]

The master has spoken: associative array it is.

[@XBOXLivexyab]

Beer, Pizza, Coffee, and Chips... A programmer's grocery list for sure!

[@Syntax753]

Loved this!

[@blueluelueluelue2343]

how do you loop through an associative array?........like in a traditional array, you can just start a for loop as (i=0;i

[@animowany111]

You use an iterator, as you can't index memory sequentially like with arrays. Something like iter = map.keys(); // or values directly while((elem = iter.next()) != null) {...} The details differ slightly between languages, but this is in general the way to do it.

[@Multigor96]

Blueluelueluelue depends on how you implement hash function, usually hash function takes key and provides a number that corresponds to that key. So what you should do is just make normal array of n elements where insertion is done on indexes that correspond to key, what that means is that developer can go through whole array like you just said but user can't.

[@wi1h]

Blueluelueluelue they're typically linked lists i believe. or you can also just use an iterator

[@nerdy_crawfish]

The correct way is to use a foreach loop if your language supports it. It should automatically get the iterator for you and iterate through each element in the array.

[@airjuri]

foreach() is the easiest, IMO, way to loop through associative array. And by using associative arrays you don't have to loop through it to find the one you are looking for. For example if you need to find price of coffee, you just use that associative index. echo $data_array['coffee']; php example follows: foreach($data_array as $key => $data) { // your code here } Inside that foreach loop, there are two variables, $key and $data, $key is the current array index and $data is anything that current index of $data_array holds. It can be anything that variable can be, another array perhaps :D

[@LeonardoBaracat]

This is THE Brian Kernighan. 27 dislikes?! Are those people nuts?!

[@vitalspark6288]

The Perl sigil for hash tables is %, not #.

[@VishiVish01]

Great video!

[@davesextraneousinformation9807]

Why is the symbol for "pound" that (strange to Americans) upside-down 7 with a line through it?

[@pleappleappleap]

Why use a linked list to deal with collisions? Why not use a second-level hashtable with a different hash function? The chances that two items will collide in two hash functions is vanishingly small.

[@balorprice]

Did Brian Kernighan just make an off-by-one array length error??? So... Much... Irony...

[@mescobar12me]

You guys should do a video on, Network on Chip! :P

[@skyepyro7104]

That small hesitation before 'Javascript "programmer"' makes me giggle.

[@Croxmata]

Are you trying to tell me that HTML is not a programming language? Hmmm!

[@weepinghomonculus4887]

Shared the same sentiment, until I started to program in React + Redux. It's as sophisticated as anything else really :)

[@BeCurieUs]

People who use things like C++ and such hate to call people who use "scripting languages" like JavaScript actual programmers.

[@knife_wizard]

Yeah... I was on a group project in college that managed to, in one semester, add a whole 7 lines to node.js that was a mistake... Javascript is hellish, and I feel sorry for the people that have to look at it for their jobs.

[@sofia.eris.bauhaus]

the only thing wrong with javascript is the few remnants of java in it. :P

[@ernststravoblofeld]

How many interviewees learn the crews' names? Cool guy.

[@jern6224]

i feel uncomfortable of the sound of the marker grinding on paper, :

[@hansvetter8653]

The only way for humans to express meaning is language, which uses words as its building blocks. So instead of a meaningless number, address in memory or numeric position in a list, you use meaningfull words instead in associative arrays ... very easy to use ... enhancing readability of code greatly ... BUT ... is hard to implement in any programming language in terms of compilers ...

[@schok51]

Topic suggestion: persistant data structures.

[@vladomaimun]

For some reason I always thought associative arrays would be complicated to implement.

[@tscoffey1]

The complexity is in making them efficient for the maximal numbers of use cases. An associative array that only expected strings as keys can be optimized better than one that has to handle many disparate kinds of keys.

[@MrSlowestD16]

The problem with them is choosing the number of buckets. Choose too many and you have wasted space. Choose too little and you have long lookup times. Then to adjust the bucketsize as Brian talked about, it takes a fair bit, so it's not something you want to do often.

[@DDranks]

At their simplest, they are simple. But then there's the implementation choices and optimisations about the hash function, numbers of buckets, re-allocation strategies etc., and they suddenly become complicated.

[@styleisaweapon]

The most complicated of them minimize overhead either in the space-complexity sense, or the time-complexity sense. The simple implementations fall right in the middle.

[@TheMagicToyChest]

Is Dr. Kernighan in Nottingham or something?

[@MissPiggyM976]

Thanks, I saw debugging Java Hashtable the effect of collisions, but I didn't recognize it for what it was, I believed it was an Eclipse strange bug!

[@DarthAthar]

This video is more about Hash tables than associative arrays, and even then it only looks at one way of doing collision resolution.

[@haczyk84]

Thank you!

[@ImSquiggs]

I thought hash collisions were exceptionally rare... do they really come up that much in associative arrays?

[@MadocComadrin]

It depends on your hash function. It needs to be rare for cryptographic hash functions, but hash functions for hash tables only really need to be balanced--- infrequent collisions are okay if your hash values are spread out over the entire table.

[@SteinGauslaaStrindhaug]

Weirdly I refer to them as hashmaps or just maps when talking about them in general, even though my two main languages calls them dictionaries (Python) and objects (JavaScript)... Wonder where I got that from, maybe back in programming class... Are they called hashmaps in C++ maybe?

[@w0mblemania]

The advantage of calling them "Dictionaries" or "Arrays" is that you abstract the problem away. After all, whether a Collection uses a fixed array or a hash table should be entirely an implementation detail, usually dependent on the number of elements in the collection, and whether uniqueness is required. The programmer typically shouldn't care about the implementation detail, only the boilerplate description, and big O characteristics.

[@liamsutton6202]

Brian could describe his breakfast for 2 hours and it would still be interesting

[@MerthanE]

How about doing some KZbin magic and making "Essentials" a actual KZbin series, like Tom Scott did with the fizzbuzz video recently +Computerphile? Anyways, nice miniseries.

[@Android480]

Not a CS dude here; why have those linked lists on top of your associative array? Why not just use a hash function with truly unique outputs, and have N be the exact number of elements in your array? This way every key is assigned a unique integer, and there's no more fuss with checking for repeated hashes. I'm sure theres a reason, I'm just wondering what it is.

[@absurdengineering]

Android480 It’s not normally possible to have a collision-free hash function. Such hash functions are called perfect hashes, and you can only develop them when there is a tractably finite set of values you wish to ever hash. Perfect hashes work great for attaching data to dictionaries with a fixed set of keys. But generating a perfect hash function is not cheap, so you can’t cheat by enumerating all the values and recompiling the hash - it’ll usually take way more time than dealing with hash collisions.

[@blvnktek]

for some reason hearing that marker really kills me inside

[@briansmith8967]

I first learned about associative arrays when I learned Tcl and I thought, "that's magic!"

[@TheTurnipKing]

In essence, an array without index numbers?

[@zss123456789]

In essence, an array with index numbers converted from actual keys.

[@sizzlebread23]

how did he get my shopping list

[@limew]

in bash you can create an associative array with: declare -A array array[pizza]=20

[@deltakid0]

Could you please add English subtitles??? It's very hard to non native English speakers like me to understand everything you say. I've seen other videos from this channel supporting this feature or at least allow Google auto captioning

[@styleisaweapon]

Its probably queued up to be auto-captioned by Google. Likely it depends on the number of views a video has before it gets put into the queue.

[@lels3618]

Why arnt there just two arrays, one with the keys (So on a access you loop trought fill you find the index where the key was) and another array with the values (which you would access by the index where the key was in its array)

[@daviddupoise6443]

The "mission" critical issue which Brian didn't really get around to is reducing the lookup for any one element. You don't want your algorithm to have to traverse the entire structure in order to find what 'could' be the 'last' element in a very very long list. Too inefficient. So the modified hash table is superior to an array or standard linked list or doubly linked list.

[@SuperManitu1]

Yeah, your two array solution is O(n) to access an element, a hashmap is O(1)

[@tscoffey1]

The search cost for table lookups for that approach is very expensive. For string keys (as in this video), you end of comparing the strings for equality to find the matching key in the table. With a table of size K, you can expect to have to check K/2 keys on average to find a match. With hashing you still have to scan the lookup key string once to produce a hash value, but you then only have to search a much smaller subset of keys (the collisions), trying to match the key. Much, much faster. However, as with all things, there is a worst case scenario - the one where ALL keys collide to one hash slot - that then requires checking the same K/2 key strings to the search key string (as above). But this is very unlikely to occur in practice.

[@zee63976]

> Coffee is essential SAVE 418!!

[@MrSlowestD16]

"Buying beer and, pizza, and coffee, and chips" - yeah, 100% programmer confirmed, lol.

[@welltypedwitch]

Well... C# has both, Dictionarys and HashTables I'm confused now

[@computerscientist5953]

they essentially serve the same purpose, but have some internal differences

[@shaylempert9994]

Whats the algorithm that decides when to increase N?

[@tscoffey1]

It can vary. The associative array would keep track internally of both how many table "slots" are used, and also how long the longest collision list is for any one hash slot. When some cost function (which combines the two in some way) reaches some cutoff value, a growth process occurs. Bear in mind that growing these tables is expensive though, as each table entry must be rehashed. So the cost/benefit between growing and not growing (but having longer search lookups) can be tricky to get right. (If you grow too often, you waste cpu growing unnecessarily. If you don't grow enough, you waste cpu on table lookups due to more collisions).

[@HazeAnderson]

0:58 he almost said Perl. He did. What happened to Perl is damn tragedy.

[@Joe-ud1de]

What did happened with Perl?

[@brittanymarie8523]

Oh my.

[@styleisaweapon]

Yay back to people that arent out of their depth!

[@keybizzoneg5209]

Coffee is essential. I like this guy :D

[@ficolas2]

2:15, why is juice free?

[@sidharthjha6916]

IIITD SHOW UP!

[@BrianFrichette]

I've only ever heard "associative array" used in PHP, a language I try to stay as far away as possible.

[@GCOSBenbow]

web devs (cringes)

[@recklessroges]

Avoiding PHP is to your credit. It was the 90ies version of node.js ;-)

[@kensmith5694]

The first one I saw was written in IBM-360 ASM. They are very useful when making compilers and interpreters. Programmers are notorious for using variable names that are similar.

[@BlenderDumbass]

In python Dictionaries it explains it self

[@bsvenss2]

02:15 I love the £0 spent on juice! *lol*

[@daiharr]

"I take pizza and run it through a hash..." Yeah, nobody will eat that pizza anymore...

[@diaverde09]

I clicked on this because I had never heard of "associative arrays" before. But then he said "Hash Tables". I'm like, "Oh, I know what those are".

[@styleisaweapon]

In actuality, "hash tables" are only one way to implement "associative arrays" in the same way that "linked list" is only one way to implement an "ordered set" ..

[@lotrbuilders5041]

diaverde09 Same i heard dictionary

[@boudreauxbroletariat3959]

just noticed that Dr. Kernighan is a lefty -- why am i not surprised haha

[@kittyrules]

Clicked because of the cans on the thumbnail

[@gz6616]

really?

[@AndrejPodzimek]

5:55 Well, in that case you might need to *undrink* some beer, diplomatically speaking. That was a very common occurrence during my university years.

[@benderrodriquez]

If I was left handed, I would have been tempted to start writing from right to left.

[@recklessroges]

Or at least set up the over-head camera on the other side.

[@mokumoku6492]

Still boils down to Linear Algebra.

[@lukenukem8028]

C# Dictionary Yay

[@lukenukem8028]

They Are Awesome