Essentials: Brian Kernighan on Associative Arrays - Computerphile

The 'Swiss Army Knife' of data structures, Professor Brian Kernighan talks about the associative array with beer & pizza.

Many thanks to Microsoft Research UK for their support with the 'Essentials' mini-series.

This video was filmed and edited by Sean Riley.

[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.

[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.

[leninalopez]

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

[fun]

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!

[loadedfries]

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.

[landspide]

A legend that truly understands 'the programmer'

[sebschrader]

Map is also a common name for this data structure

[brucewaters]

this guys shopping list

Beer
Pizza
Coffee
Beer

[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 :)

[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.

[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.

[AvailableUsernameTed]

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

[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.

[oysteinsoreide]

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

[DJstarrfish]

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

[gggfx]

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"

[sowellmemo]

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

[donaldkjenstad]

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