Hash Tables - Beau teaches JavaScript

Просмотров 92 тыс.

% 1 565

Hash tables are a quick way to implement associative arrays, or mappings of key-value pairs. Find our more and learn how to create one in JavaScript.
💻 Code: codepen.io/beaucarnes/pen/VbYGMb?editors=0012
🔗 Info: www.willvillanueva.com/javascript-hash-tables/
🐦 Beau Carnes on Twitter: carnesbeau
⭐JavaScript Playlists⭐
▶JavaScript Basics: ru-vid.com/group/PLWKjhJtqVAbk2qRZtWSzCIN38JC_NdhW5
▶Data Structures and Algorithms: ru-vid.com/group/PLWKjhJtqVAbkso-IbgiiP48n-O-JQA9PJ
▶Design Patterns: ru-vid.com/group/PLWKjhJtqVAbnZtkAI3BqcYxKnfWn_C704
▶ES6: ru-vid.com/group/PLWKjhJtqVAbljtmmeS0c-CEl2LdE-eR_F
▶Clean Code: ru-vid.com/group/PLWKjhJtqVAbkK24EaPurzMq0-kw5U9pJh
-
We're busy people who learn to code, then practice by building projects for nonprofits. Learn Full-stack JavaScript, build a portfolio, and get great references with our open source community.
Join our community at freecodecamp.com
Read great tech articles at medium.freecodecamp.com

Опубликовано:

14 апр 2017

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 40

@lenaggar 6 лет назад

@Beau thank you for what you do for the community

@fatemabohra4277 6 лет назад

there is no such video except this which explains a simple hash function in javascript in a practical way.

@paschalynukwuani6930 Год назад

Beau you are one of the best tutors on the internet.

@camillemorell3270 4 года назад

This is the best video I've watched on Hash Tables

@jhovahngibbs6720 6 лет назад

tux is a penguin, that made me smile

@vishalheble 7 лет назад

Can you explain what do you mean by "When (inserted=== false), then push the key,vales into storage array. But how do we get multiple entries for the same bucket? It means collision right? But how can it happen when you don't find the same key which actually happens in previous case i.e. when the key exists already. Help me.

@goodwish1543 7 лет назад

Nice explanation. Good work, Beau Carnes ! Line 42, There is a use case in Remove method, that is the key doesn't exist in array. The code logic works. If we may test it separately, it'll be more clear.

@facundomartingarciaengel6318 2 года назад

U re the best bro ;) thanks from Argentina!

@ChocolateMilkCultLeader 4 года назад

So well done

@OliverMensahDev 7 лет назад

Good work Sir

@arthuretf 7 лет назад

Shouldn't it be `i < storage[index].length` on line 46?

@BeauCarnes 7 лет назад

Yup! I fixed it in the code that is linked to in the description.

@__abshir 4 года назад

line 45*

@funkybuddha1598 3 года назад

I wasted 2 hours because of that!

@NathanielBabalola 2 года назад

The buckets in the hashtable function is 4, but you're using 10 in the hash function ?

@sergeypomaraiko4661 6 лет назад

at line 43 you have deleted array item, but length of array wasn't changed. So line 42 never will be true if we have inserted item once

@goodrowj 5 лет назад

I think I might be missing something here, wasn't the point of a hastable to have O(1) reads, inserts, and deletes? This is running O(n) blocks for each of those operations. Is there a way to get those down to O(1) in Javascript?

@ernwillburn 5 лет назад

Yeah this video is not really correct or O(1)

@dannytran4667 5 лет назад

You get constant time by reducing the chance of collision. One simple way to do this is to double your storage size when the load factor gets high (the ratio of items to buckets). When you hit the load factor, double the number of buckets (in this case the storage Limit) and rehash all the items so hopefully they're in their own bucket.

@NathanielBabalola 2 года назад

On line 30, you're overwriting the previous value that was tied to that key. Is that how it's meant to be ?

@dcts7526 2 года назад

was looking for that comment. Since the hashfunction is deterministic, the same key will always result in the same index, hence the value must be by definition the same. Overriding it is unneccessary you are right!

@sabuein Год назад

Thank you.

@anirvanchandra 7 лет назад

which text editor do you use

@rexromae17 7 лет назад

that looks like CodePen

@FernandoFleuryGil 6 лет назад

it's a website called codepen

@JohnDoe-ji1zv 4 года назад

Is hashtable actually used in a daily programming ? Could you give an example please

@kattenelvis1778 4 года назад

No it's only used in leetcode and interview questions.

@RedEyedJedi 4 года назад

It is used anytime you want a fast insertion, look up or delete. The data structure you decide to use should always be based on how the data is going to be used. Don't just use an array for everything, although an array can be used for most things, speed is a major factor in developing software.

@dcts7526 2 года назад

Good question, would be interested to hear too. We all use hashtables indirectly by using hashmaps, sets or simply objects. But I've never applied a hashtable throughout my developer career so far too...

@seyfullah7314 Год назад

Average time complexity of finding the hash value of any input is already O(n), However, how come the average time complexity of insertion be O(1) ?

@aaronargottelopez3488 3 года назад

Thanks

@bluemenkranz_2953 2 года назад

actually iam a beginner but when i reading the code for add function i got confused and i try to fix it with this code instead > this.add = function (key, value) { var index = hash(key, storageLimit); if (storage[index] === undefined) { storage[index] = [key, value]; } else { storage[index].push([key, value]); } }; still work tho

@bruhmoment3731 Год назад

hello Genshin player.

@sifatmoonjerin2479 4 года назад

Hey, great content! But I think using splice instead of delete will be a better solution. This throws an error if you remove a chained key and then try to reassign it.

@iuripires7285 3 года назад

hmm, but I think splice gonna remove the slot spaces in our storage, while delete keeps the space associated with that index but with an undefined value.

7 лет назад

hey, good video

@shayanjavadi 6 лет назад

Really weird mixture of var let and const here. Your storage can be a const since the array location in the memory doesn't change, only the array items do. all the functions should also be consts as well. there's really no point in using var anymore. great video otherwise!