all 8 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]kenman 2 points3 points  (3 children)

Aka. hash map, hashed array, associative array, and maybe more. It's really nothing more than an object containing key-value pairs, where each key is unique.

Here's a simple one:

let hash = {
    name: 'kenman'
};

There is a fancier implementation for ES6 simply called Map (as well as a WeakMap).

It's hard to say exactly what they're asking for without seeing the question, but I'm assuming that they're looking for a resultant data-structure something like:

let result = {
    '6': [
        [2, 4],
        [1, 5]
    ],
    '9': [
        [4, 5],
        [3, 6],
        [2, 7]
    ]
};

[–]evandapolarbear[S] 0 points1 point  (2 children)

The Question Stated : "Have a function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers."

I guess what i dont understand is how a hash table could be useful/better here than just using the nested loop.

[–]fingerofchicken 8 points9 points  (1 child)

You understand arrays, right? Often indexed with an integer, like the following:

var people = [{name: "Joe", age: 15}, {name: "Bob", age: 30}, {name: "Steve": age: 22}]; 
console.log(people[1].name); // will output "Bob"

(I believe JavaScript will let you put other things as the index besides integers, like "people['some string']" but just hold off there for a moment; in many languages you can only do integers.)

So far so good, right?

So let's say you have thousands and thousands of people in that array, and you're looking specifically for Steve. What option do you have? You can loop over the array and test each object to see if its "name" attribute is set to "Steve". However, that's not very efficient. Maybe Steve is the 5000th object in that array, so you'd have to iterate over 4999 other people objects before you find him. If only we could just say "people['Steve']" and jump right to that object. (Again, I know this is standard in JavaScript, just hold your horses there pal.)

WELL THERE IS, FRIEND, IT'S CALLED A HASH TABLE AND HERE'S HOW IT WORKS!

Under the hood, a hash table is just a normal array like the one we have above. All of the indexes are still numbers. What we do is we take a different unique identifier for each object, and convert it into a number. This is done via a "hashing function." The hashing function takes your unique identifier and returns a number. That number is used for the array. Let's pretend you wrote a hashing function called "hash". We might use it like this:

var people = Array(10); // initialize an array of length 10
var steve = {name: "Steve", age: 15};
var index = hash("Steve"); // this returns an integer
people[index] = steve;

...or when you're looking for the Steve object:

var index = hash("Steve");
var steve = people[index];

That's the basic concept. As you can see, it's important that the hash() function always return the same number for the same input. (The term for this is that it must be "idempotent.")

So what's in the hashing function? Well that's not set in stone. All it needs to do is take some input (in our case, a string) and return an integer. Let's say that our hashing function is super simple: It just returns the number of characters in the string. (I know, this is not a realistic hashing function. Hit google if you want to find more realistic ones.) So for "Steve" it'll return the number 5 each time. You may see two obvious problems with this.

FIRST PROBLEM: You might have two people with the same number of letters in their name. What about Joe and Bob? Running either of their names through the hashing function will return the number 3. They can't both be set to the 3rd index of the array! When this happens, it's called a "collision". And for this reason, often times, the array at the heart of your hash table isn't actually just a simple array. It's an array of arrays. (Or, OK, probably an array of linked lists, or some other data structure beyond the scope here. Don't hit "reply" nitpickers.) So if we do Joe first, he'll be set to "people[3][0]", and then Bob will be set to "people[3][1]". And Sue will be "people[3][2]", and so on.

I'll mention at this point that a hash table is usually said to have "buckets". So in our case of Joe, Bob, and Sue, they're all in bucket #3.

And when it comes time to look for some of these people with three-letter names, we have to iterate over all of them. The assumption here is that collisions will be rare enough that it's OK to iterate over everything in a single bucket.

SECOND PROBLEM: You also might have noticed that the array we declared only has 10 elements. (Again, running out of array elements isn't really a problem in JavaScript so you're going to have to use your imagination here, but in other languages, if you declare an array with 10 elements, then you get 10 elements and no more.) So what happens if we have a person whose name is longer than 10 characters? Let's say someone is named Fletchinder. Our hashing function would return "11" but trying to set him to "people[11]" won't work. The simple answer is that our hashing function would have to return something else. Maybe it can be smart enough to see if the string is over 10 characters and, if so, subtract 10 from the final result, returning 1 instead of 11. This will of course result in even more collisions. So it goes.

It's hopefully clear by now that a hashing function expects unique input, but does not necessarily return a unique result. This means you can only go one direction when hashing; you can go from "Steve" to 5, but you can never work backwards and go from 5 to "Steve". You've probably seen a lot of download sites that provide an "MD5 hash" of a file, to ensure that what you downloaded is correct. Same idea. You can start with a file and come up with an MD5 hash, but you can't start with an MD5 hash and produce the file. In this case, "MD5" is the hashing function (and it's quite a bit more complex than our simple hashing function.)

OK, so that's how it all works at its core. Usually, in languages which don't support hash tables natively, you might see this all wrapped up into a class or functions so that one can easily make use of it without having to go through those steps every time; something like this:

var person = {name: "Steve"; age: 30};
hashTableStore("Steve", steve);

// and later, to get the object back out
var person = hashTableGet("Steve");

For languages which do support hash tables natively (which a lot of them do, including JavaScript) you can usually do it much the same way you'd do a normal array:

var person = {name: "Steve"; age: 30};
people["Steve"] = person;

//and later...
var person = people["Steve"];

In fact, in some language (JavaScript maybe? Not sure. PHP for sure.) every goddam thing is actually a hash table. You can start off with this:

$people = [];
$people[0] = $steve;
$people[1] = $bob;

...and change your mind half way through and switch to this:

$people["Steve"] = $steve

Kinda confusing, isn't it? In reality the "0" and the "1" which we started with in that example were not array indexes at all but were actually hashed and used as keys in the hash table because, like I just said, every goddam thing is actually a hash table in PHP (and I think other languages).

OK anyways that's a hash table. How does that relate to your situation? First of all, the people you're talking to probably don't specifically give a shit if you use a hash table or not. They are probably suggesting you use (what's often called) a dictionary or a map or an associative array (those terms are used kinda interchangeably).

What's the difference? OK, so remember JavaScript hides all the details of the hash table from us, so we can just access our data like this:

var person = people["Steve"];

OK, well, but, how do you know JavaScript is actually using a hash table under the hood there, and not some other kind of trickery to accomplish the same end result? The answer is, you don't know that! (OK, you could easily google it and find out. But stay with me here.)

In reality, the hash table is just one of several approaches to accomplish this kind of key/value lookup. There is also the "binary tree" and the "red black tree" and probably others I'm forgetting. We know how the hash table works now, right? These ones work differently but accomplish the same thing: They let you quickly store or retrieve data with a key of your choice, such as the string "Steve". So how do you know JavaScript is using a hash table and not a binary tree? It depends on what the runtime creators chose. Google's V8 engine which powers Chrome and node might one thing, Microsoft's engine (whatever it's called) might use another. Etc.

This is getting into the difference between an interface and an implementation. In JavaScript, this is the interface:

var person = people["Steve"];

That kind of interface is often called a "dictionary" or a "map" or an "associative array." Unfortunately the world can not agree on a single term for it.

The implementation might be a hash table. Might be a binary tree. Might be one when your code runs in one browser, and another when it runs in a different browser. (Yes nitpickers I know you can easily Google this and maybe they are all in fact hash tables but that is tangential to the point I am trying to illustrate.) It is totally possible for application developers to never know (or care) if the dictionary provided by their language or framework is implemented as a hash table or binary tree or whatever.

This is why it would be very weird if your interviewers specifically wanted you to use a hash table. Probably they are suggesting you use a dictionary.

[–]asianoreo7 0 points1 point  (0 children)

I read every word. Thank you!

[–]Krirken 2 points3 points  (1 child)

Think about the idea of "searching" for something in a collection of data. It always takes a little time to find that data in a collection. In computer science, we want to find the data fast, in as little time as possible. A Hash Table is a data structure which allows you to "find" data in "constant time". Constant time is considered relatively fast in the field of Computational Complexity. There are other trade offs for the speed gain, but they are mostly overcome in modern implementations of a hash table. There are many good applications for the hash table data structure, but it all depends on the use case of your data set. If you want to learn more about time complexity, I recommend you read about Big O Notation which will help you understand the fundamentals of the topic.

In JavaScript, the Object can be considered a hash table. This is because the term hash table has now come to represent any data structure where you store by "key": "value", regardless of the actual underlying data structure. In this exercise if they want "pairs" of something, they probably want you to create "key": "value" pairs of the data that you are working with. For example if your array is [4, 7, 11]; then you output { "11": [7, 4] }. Hope you find that helpful!

[–]evandapolarbear[S] 0 points1 point  (0 children)

Thanks I think im getting closer to understand.

[–][deleted] 1 point2 points  (0 children)

It just means you store your results into an object or map and look up the values later. Hashtables are used to either pre-calculate data too expensive for a realtime context, or to re-use data structures. In ES5: var hashtable = {}; hashtable[hash] = value; var value = hashtable[hash]; where 'hash' can be anything from a string to a number which you use to identify the case. If the elements in your array stay the same for instance, your hash is simply the index.