Essentials: Brian Kernighan on Associative Arrays - Computerphile 

£134 worth of coffee at that, hooooly

Classic Kernighan examples :D

Eh. Sounds like your average programmer.

you forgot beer

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

tg

Ken Thompson is still with us...

@@treyquattro ken doesn't like the interviews.

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

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

Sebastian Schrader my bad, I must've misheard!

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.

object. B)

Elegantly put.

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

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

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

Access time in terms of caching seems inefficient as well

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

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

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

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.

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

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

Are you claiming that it's a magic marker?

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.

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.

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.

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.

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

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.

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.

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

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.

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

So a hash comments, but percentage hashes?

It may matter which "Perl" we are talking about. Like Python, there was a significant break in compatibility at some point. Perl is supposed to be one of the best languages for string manipulation, but its also a language that never really took off outside of *nix operating systems.

hashes in perl are the most useful structures ever so I used them a lot and Im not aware of % being changed at any time between versions, but I didnt check the whole history

I’ve learned to use hashes in Perl, but I learned to love hashes in Ruby.

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.

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

web devs (cringes)

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

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.

really?

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.

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.

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

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.

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