Hash Table in C

Рет қаралды 58,214

Күн бұрын

Chapters:
- 0:00:00 - Announcement
- 0:00:41 - Why Implement Hash Table?
- 0:02:07 - Where we could use the Hash Table?
- 0:03:15 - New Project
- 0:03:40 - Nob build
- 0:07:54 - The Problem Description
- 0:08:48 - Downloading all the Works of Shakespeare
- 0:10:40 - Reusability of Nob
- 0:11:12 - Reading the File
- 0:13:09 - Tokenizing the File
- 0:16:23 - Better Tokenization
- 0:20:28 - Linear Associative Array
- 0:23:58 - Total Amount of Tokens
- 0:25:00 - find_key()
- 0:27:07 - Collecting Frequencies
- 0:29:03 - Nob Subcommands
- 0:31:13 - Smaller File
- 0:32:36 - File Path via Command Arguments
- 0:35:32 - Measuring Time
- 0:36:33 - Sorting Frequencies
- 0:37:39 - compare_freqkv_count()
- 0:38:16 - Generic Comparison in C
- 0:40:05 - Generic Comparison in Other Languages
- 0:40:45 - Generic Comparison in Rust
- 0:42:30 - Subtraction is All You Need
- 0:44:15 - Comparison is Basically Subtraction
- 0:44:39 - Descending Order
- 0:44:57 - Printing Top 10 Frequent Tokens
- 0:47:23 - Cleaning up logging
- 0:49:01 - Elapsed time
- 1:00:29 - Concatenating Files
- 1:02:07 - How Linear Search Works?
- 1:03:31 - The Hash Table
- 1:07:39 - Hacking Hash in Competitive programming
- 1:09:02 - Q: Have I done Competitive Programming before?
- 1:10:14 - What's the Competition in Competitive Programming?
- 1:11:11 - hash()
- 1:12:32 - naive_analysis()
- 1:15:05 - Iterating tokens
- 1:15:59 - Looking at the Hashes
- 1:17:33 - When Hashes Collide?
- 1:24:40 - Better Hash Function
- 1:26:55 - Open Addressing
- 1:28:44 - Probing Strategies
- 1:29:33 - Reflection
- 1:31:29 - Resolving Collisions
- 1:34:35 - Table Overflow
- 1:40:44 - Abstraction
- 1:46:41 - Adjusting Hash Table Parameters
- 1:47:34 - Sorting Final Results
- 1:48:59 - hash_analysis()
- 1:51:53 - Comparing execution time
- 1:54:05 - Sum is a bad Hash Function
- 1:55:25 - Testing Bigger Files
- 1:57:03 - djb2
- 2:03:18 - Further Abstraction
- 2:06:43 - Summary
- 2:07:08 - Potential Malicious File
- 2:07:53 - Just Do Dumb Things!
- 2:11:15 - Outro
References:
- / provod
- ocw.mit.edu/ans7870/6/6.006/s...
- codeforces.com/
- www.cse.yorku.ca/~oz/hash.html
Support:
- BTC: bc1qj820dmeazpeq5pjn89mlh9lhws7ghs9v34x9v9
- Servers: zap-hosting.com/en/shop/donat...

Пікірлер: 121

@samuraijosh1595 7 ай бұрын

Tsoding has finally heard us, Gentiles, giving us the content that's on our level. The Lord has heard my prayers, amen. 😭😭

@caiodavi9829 7 ай бұрын

finally back to C

@anon_y_mousse 7 ай бұрын

My goto hash table implementation is to use an array of arrays to handle the collisions, but I've also used an array of trees and an array of sorted lists and all manner of other combinations. I also always use a power of two for the table size so I can just do a `bitwise and` to normalize the hash and store the unnormalized hash with the keys to make collision checks faster. I also like to use a handy trick to speed up deletions, if that's an operation you even need to support, whereby I swap the key to be deleted with the last key in the table and just fix up the indices for that key then decrement the length of the table. It only reorders two elements with each deletion so it's a lot faster if you don't need the data in a sorted order after every modification, or for that matter need to preserve the order. I've used a DJB hash function every time I've needed string keys and I kind of flip flop on whether *31 or *33 is better, but I'd say play with it for whatever data you're using and either it won't matter or one will be just a bit better. Though, I always initialize it with 5381 as I figure that constant is what designates it as a DJB hash. Maybe I'm just weird.

@divingeveryday 6 ай бұрын

I am now subscribed. I just found these streams and absolutely love them. The rant at the end sealed the deal.

@jolynele2587 7 ай бұрын

i learnt to make a hash table in harvard's free cs50 course and it's pretty similar to this so it's pretty cool. writing collections is pretty fun

@snw404 5 ай бұрын

"Implementing hashtables in C kinda remind me my childhood" 💀💀

@ElPikacupacabra 7 ай бұрын

At 43:43, the real reason is that the subtraction trick only works for integers less than around half the value of the maximum absolute allowed. If you subtract `SIZE_MAX` from `-SIZE_MAX`, you will get overflow and your comparison will fail. In your case, it's irrelevant because there are not that many items in the hash table. `SIZE_MAX` is very large, practically. A better way of coding the logic without risking overflow and without too much branching is `(b < a) - (a < b)`.

@jadetermig2085 7 ай бұрын

Branch != cmp. There are zero branches in (b < a) - (a < b). There are two extra comparisons but no branch. A branch is a conditional jump. Another example would be cmov. That allows the compiler to compile something like if(a < 0) a = 0; without branches / conditional jumps.

@ElPikacupacabra 7 ай бұрын

@@jadetermig2085 Good point! I misused the word 'branching'.

@harleyspeedthrust4013 7 ай бұрын

perfect timing, i have been implementing some based data structures in c++ for fun these past few days

@rodelias9378 6 ай бұрын

Great stream and really good pieces of advice at the end!!

@kmsskyquake7330 6 ай бұрын

16:19 MY FIND FUCKING BLEW AT THIS POINT YOU ARE A LEGEND

@maxmustermann5590 Ай бұрын

I was asking myself some time how he got this good, but when implementing hash tables in C reminds you of your childhood that's probably the answer

@i007c 7 ай бұрын

you can also use the clock() function for cpu time. it will give you the total cpu cycles that took between the operation

@sanjaux 7 ай бұрын

Keeping my inspiration up with these vids 🫡

@puzzlinggamedev 5 ай бұрын

I like the exploratory style. Very interesting lessons learned!

@AlmogD 7 ай бұрын

This is actually an exercise in The C Programming Language by K&R

@user-ox6mt1lh7b 7 ай бұрын

Great video as always!

@araggohnxd 6 ай бұрын

gotta love this man's passion

@afterschool2594 7 ай бұрын

Let's Go we're back to C again

@blackhaze3856 5 ай бұрын

This is a masterpiece of programming.

@robmorgan1214 7 ай бұрын

Wow, nob looks pretty freaking cool! Make sure your clock is just a wrapper for rtdsc with calibration. Also to preserve precision subtract prior to conversion to double and then do your multiplication*. (Edit*)It's a minor detail that rarely matters but it's best to be in the habit of maximizing both accuracy and precision while ALSO maximizing performance (fewer FP ops = less rollover error and less fp mantisa mismatch error eg subtract a very small fp from a big fp will always = big fp no matter how many times you do it)

@anon_y_mousse 7 ай бұрын

Using rdtsc is specific to x86 platforms, and can be locked by the kernel, and thus must be accounted for beforehand on such platforms. The subtraction won't work prior to conversion because he's attempting to express the value in seconds and the tv_nsec field expresses the number of nanoseconds, so it has to be converted first.

@robmorgan1214 7 ай бұрын

@@anon_y_mousse the conversion is trivial it will work with or without the subtraction. As for x86 etc., any generic code you're gonna write in c or c++ will require define guards all over the place to do anything useful and platform independent. This isn't Java or python. Either embrace the metal or or not but the critique stands: when using floating point you need to have good habits or you won't get the answer you want. The reason you use rdtsc or it's local HW equivalent instead of a clock is to avoid measurement jitter or to detect runtime jitter and other non deterministic things happening to your code. This can be very important in many applications as core hot behavior is very different than one shot performance with cold cache. Interrupts can also make important performance tests non deterministic. C is an abstraction that let's you decide when it's time to program the machine, not the abstract machine. It goes without saying that you should pin and isolate your process or execution thread to a specific core if you care about accurately benchmarking a key section of a program... especially in C/C++ where memory performance and cache strategies often create the biggest bottlenecks unless it's unusually mathematically complex (rtdsc is local to your core)

@rian0xFFF 7 ай бұрын

I wish I had time to fully watch your videos, they are so cool.

@demolazer Ай бұрын

When asked why you are coding something, "Because I can" is an acceptable response.

@willvincentparrone3339 7 ай бұрын

Cool video!

@s4n7r0 6 ай бұрын

you absolutely murdered that semicolon backseating guy

@u9vata 7 ай бұрын

Awsome t-shirt. I have some like that too - just regionals though, and much better I am at home too because I am more like a slow water makes interesting algs than always in competitive environment ;-)

@loic.bertrand 7 ай бұрын

43:20 also subtration can cause an overflow, for exemple if you're doing (-big_number) - (big_number)

@opsJson_ 7 ай бұрын

now i'm happy.

@felixbilodeau-chagnon4781 7 ай бұрын

Love how the djb2 hash function is basically the same thing he did except it starts at 5381 instead of 0 and multiplies by 33 instead of 31

@monad_tcp 6 ай бұрын

That was probably exactly how the writers of djb2 came up with those numbers, just by throwing shite at the wall and seeing if it does better or worse. Which ironically, if you document it , is the scientific method. And thats literally why it's called computing science .

@mire6134 7 ай бұрын

Are you going to participate in the AoC event this year?

@slava6105 7 ай бұрын

Поставлю лайк, наверняка в универе пригодится

@TsodingDaily 7 ай бұрын

Лайк тебе никак не поможет в универе. Надо смотреть.

@kuijaye 6 ай бұрын

55:04 I think converting seconds and nanoseconds into miliseconds is a better idea. I feel dividing by 1e-9 may cause some round off error.

@lievenpetersen 7 ай бұрын

28:15 all hail the CLITERAL! (although the extra parens are not necessary afaik)

@agx1397 6 ай бұрын

From where does actual implementation of hash table start?

@ailphaune 6 ай бұрын

so the smallest string (using only lowercase letters) that has a djb2 hash of 69 is "glidrn" Edit: i'm pretty sure it's the smallest string even if you allow the full range of ascii characters

@cobbcoding 7 ай бұрын

go rebuild yourself is still the best macro name i've seen

@datadriveAshura 7 ай бұрын

Next pointers in c pls

@arabusov 7 ай бұрын

А переполнение беззнакового в сях разве не UB?

@0ne87 7 ай бұрын

delta_secs sounds like something that happens at super elite masquerade parties.

@HuntingKingYT 7 ай бұрын

Missing so many semicolons... really feels like python

@caiodavi9829 6 ай бұрын

😮

@alexloktionoff6833 2 ай бұрын

How stb hash does perform compared to this DIY?

@hbobenicio 7 ай бұрын

Just curious about the performance of these algorithms when compiling with optimization flags (like -O3 -march=native)

@MatthisDayer 7 ай бұрын

How does one write "azozin"?

@leewei9117 7 ай бұрын

I like your channel very much. Can you upload English subtitles? Is it convenient to translate into my mother tongue? Thank you very much!

@caiodavi9829 6 ай бұрын

👎

@jamesphilemon8010 5 ай бұрын

The auto-generated captions are actually very good quality (probably because of his enunciation), so just turn them on.

@RandomGeometryDashStuff 7 ай бұрын

43:14 big count overflow?

@UlvicanKahya 7 ай бұрын

The guy who suggeted 31 as the multiplier is 100% a Turkish guy

@j.u.g.y 7 ай бұрын

Wouldn't it be accurate to lowercase first.

@tigranmartirosyan7111 7 ай бұрын

Thank you for the excellent content! I would like to suggest recording another session that delves into consistent hashing, a technique actively employed in network load balancers.

@DeathSugar 7 ай бұрын

Nob release when?

@jannemyllyla1223 7 ай бұрын

sum makes it's distribution very non-uniform. (basically it is very similar to average)

@marcelijankowski9593 7 ай бұрын

Perfect timing! I just finished implementing hash table in x86-64 asm for my brainfuck interpreter. Although there is a bug in automatic resizing, slots are populated with some random gibrish after couple resizings. Gonna have to look into that. Edit: Ha! I managed to solve it, I had a label "ht_address" with address of hash table (statically stored, cause only one table is ever instantiated in that project), and I had statements like this one: leaq ht_address(,%rax, SLOT_SIZZE), %rdi The thing is that here the address at which the value of ht_address label is stored is used, and not the value itself! Silly me!

@Shywizz 7 ай бұрын

And here i am wondering if ill ever even be on half that level.

@josefaguilar2955 7 ай бұрын

You will be on that level as long as you try to be. The hardest problems are always solved with persistence.

@kingfrenchtoes5769 7 ай бұрын

drop the github link

@marcelijankowski9593 7 ай бұрын

@@Shywizz With enough effort you'll definitely get there. There's nothing special about tsoding guy, me, or anyone else for that matter (mostly).

@marcelijankowski9593 7 ай бұрын

@@kingfrenchtoes5769 this interpreter is literally the first thing that I ever wrote in assembly, so I didn't initially put it on github. I definitely will once it's finished (around 2 weeks from now most likely). I'll post the link here, if I won't forget. Now with the hash table, memory allocator, linked list, and so on so fourth implemented I just gotta finish the main interpreter part and it'll be over.

@Bambuchaa5 7 ай бұрын

SAIAGO FEZ ANTES DE VOCÊ !

@orzklv 7 ай бұрын

FINALLY! Some normal fucking content!!!

@orzklv 7 ай бұрын

@TigranK115I’m not about tsoding only, I mean, all dev channels combined.

@samuraijosh1595 7 ай бұрын

Yeah finally some content I'm hoping us mortals can understand.

@RandomGeometryDashStuff 7 ай бұрын

2:00:46 because terminated string?

@ZoraAlven 7 ай бұрын

at the dead end, semicoloned code much more readable and much more brain computable, from my conservative point of view. but yeah, for "shitting-on-the-go" type of activities python is pretty nice 👍🏼. Good stream, thanks!

@xspager 7 ай бұрын

I'm glad Python exists.

@davydorynbaev 7 ай бұрын

hello hello zozzing

@boogly3716 7 ай бұрын

Вот это возвращение к истокам... Кстати, насчет программирования в молодости: Недавно смотрел интервью 46-летнего Мурыча, где он рассказал об одержимости каждого программиста из 90-ых написать свою виртуалку. Не было ли у тебя такой шальной молодости?))

@RandomGeometryDashStuff 7 ай бұрын

1:43:44 why cap in parentheses when assign but not multiply?

@monad_tcp 6 ай бұрын

Multiply doesn't suffer from priority inversion of token precedence. Or probably just a bug. The idea of parenthesis is that if you put an expression in the macro instead of a single token, you don't break the precedence rules or even the syntax. Makes the macro a bit safer, not by much , it's still CPP , C preprocessing macros .

@RandomGeometryDashStuff 6 ай бұрын

@@monad_tcpwhat is priority inversion of token precedence?

@soyitiel 7 ай бұрын

1:14:28 famous last words

@vishwanathbondugula4593 6 ай бұрын

Hey a quick question, why don't you use make or cmake as your build too

@yrpsa 7 ай бұрын

can anyone tell me how do you mark the text like that in 2:38

@anon_y_mousse 7 ай бұрын

It's just highlighting the thing he's searching for. I don't know how it's turned on in Emacs, but in Vim you'd set hlsearch in your ~/.vimrc or if you just want it for the current session by typing it in directly at the command prompt.

@glowiak3430 7 ай бұрын

Great, but why complicate it so much? My approach is to just have two arraylists, one with strings and one with objects with 1 to 1 correspondence.

@Exatio 7 ай бұрын

Optimization. In hash tables, the index of an element is created from itself, so when searching, you just have to hash the element you're searching, and then check the index that was generated. This is O(1). In an arraylist, youd have to use bilinear search which is O(n)

@pierreollivier1 7 ай бұрын

@@Exatio his approach can be more performant, because you have two different compact data structures for different things, such that you have less risk of cache eviction on certain operations. It's called data oriented design, you make sure to have compact data structures, to maximise the use of the cache. Which is by far one of the most important performance predictor in almost any programs.

@jacksonlevine9236 7 ай бұрын

@@pierreollivier1How does this invalidate hash table as a data structure though, it sounds like you are just poking holes in his arbitrary use case he chose. Hash tables are a thing, they have their place, no knock on data oriented design, but one doesn't invalidate the other.

@pierreollivier1 7 ай бұрын

@@jacksonlevine9236 It doesn't that's why I've said that "his approach can be more performant" It's not necessarily the case, a good old hash table might be faster, but a DOD hash table might also be faster depends on the use cases, but both are valid variation of the same model.

@kasuto-no-machi 7 ай бұрын

Because having two 1:1 arrays/lists is linear time lookup, insertion and retrieval. That’s fine if you have very few keys, but for a hash map those operations are all constant time, and for large datasets it’s far more performant.

@trashcan3958 7 ай бұрын

Coding in C is so painful...

@jadetermig2085 7 ай бұрын

I think you missed an opportunity to call it nobs = no build system

@jaumeguimeramarquez2244 7 ай бұрын

I expected a hash table in Next.js😢

@____r72 7 ай бұрын

Gluggalog vandierbloggagglen

@hectorjazz7 6 ай бұрын

I recently downloaded the musializer project, compiling with nob is pure delicacy ./nob :) I have been experimenting with nob.h, we hope to have an official version of that promising project. Thanks tsoding

@ludwintor4986 7 ай бұрын

I love how you after the message from chat "you forgot a semicolon" just go and remove the only one semicolon. great troll

@keremardcl6759 7 ай бұрын

Yet you dont like PHP just having the feature natively :D

@adriansyahkadir1548 7 ай бұрын

1w upload?😂

@realfootball338 6 ай бұрын

Hello

@AlameenAdeyemi 2 ай бұрын

Bro said he his not a computer science person 😂 btw how can i join the discord server?

@kuijaye 6 ай бұрын

I wish i could give you money or buy you a book or sth.

@brissance 7 ай бұрын

i have no programming socks .

@cronosmain 7 ай бұрын

C# of a normal person

@soyitiel 7 ай бұрын

Ayo, if the compiler can tell us where we forgot to put a semicolon then it shouldn’t need us to put a semicolon, it should just infer it, I mean js already does it

@jadetermig2085 7 ай бұрын

This is a nonissue to C programmers. I never forget semicolons and type them without thinking about it / noticing it. It's an issue to people that regularly switch between C and Python/Go/JS. AFAIK semicolons are optional in js but it's idiomatic for people to use them. Does no semicolons even work with minified javascript?

@soyitiel 7 ай бұрын

@@jadetermig2085 Having acquired the habit, I guess that's alright Still, as you said, it'll always be an issue for polyglots Also I don't think there should be any merit in developing the habit to always do something that could and should already be done, it'd be like developing the habit to always putting the toilet seat down or closing the fridge door because someone else in the house always leaves those open, it just shouldn't be necessary. In any field, the goal should always be to alleviate unnecessary tasks so processes may be optimized. PD: About js and semicolons, that's exactly the point I'm trying to make: Do you want to write semicolons? Knock yourself out. Do you not want to? I got you, hun

@jadetermig2085 7 ай бұрын

@@soyitiel Sure but js syntax is already C-like and (like C) very sprawling and not elegant or minimal. For something so "trivial" as semicolons it's a tradeoff between familiarity and "correcting mistakes of the past". I'm not even sure semicolons were a mistake for the context C was designed for (a PDP-11 in the 70s). JS syntax was obviously inspired by C so an argument could be made that having to unlearn a habit is just as counterproductive. Semicolons are kind of special since they're optional so a C programmer in the 90s didn't have to unlearn it to use js. But he still has to adapt to it not being there even though the syntax otherwise feels like C. For example nobody complains about the lack of semicolons in Haskell because the syntax is nothing like C. All in all I feel it's no big deal. I still type semicolons in js (as do most people in my experience) and for languages that are nothing like C I don't even think about it because everything is different.

@segus_faultise 2 ай бұрын

أَبَانَا الذِي فِي السَّمَاوَاتِ، لِيَتَقَدَّسَ اسْمُكَ لِيَأْتِ مَلَكُوتُكَ لِتَكُنْ مَشِيئَتُكَ فِي الأَرْضِ كَمَا السَّمَاءِ اعْطِنَا خُبْزَنَا اليَوْمِيَّ اعْفِنَا فِي مِمَّا عَلَيْنَا فَقَدْ أَعْفَيْنَا نَحْنُ أيَضاً مَنْ لَنَا عَلَيْهِ وَلاَ تُدْخِلْنَا فِي تَجْرِبَةٍ لَكِنْ نَجِّنَا مِنَ الشِّرِّيرِ لأَنَّ لَكَ الْمُلْكَ وَالْقُوَّةَ وَالْمَجْدَ إِلَى الأَبَدِ آمِين

@0x80-linux_user 7 ай бұрын

Nice video, but i can better

@desertfish74 7 ай бұрын

Knob

@Purkinje90 7 ай бұрын

Have you accepted Rust as your lord and savior?

@vbachris 7 ай бұрын

very dumb hashtable, 100% time improvement!

@careneso6502 7 ай бұрын

Хоршо что Rust существует , в его стандартном крейте уже есть хеш таблицы. Ни один гомосексуалист не будет оскорблен тем, что он вынужден писать свою хеш таблицу. Воистину лгбт-френдли язык, не то что С\C++

@gorenbk 7 ай бұрын

rust is better :3

@enclave2k1 7 ай бұрын

As someone who loves rust, why not just view languages as tools to complete a task? Hammers aren't better than screwdrivers; use the best tool for the job at hand. People treat languages like political affiliations these days. (sorry to go off, I know this is likely a tease/troll comment for tsoding - just see a lot of this kind of stuff, which confuses me)

@dupdrop 7 ай бұрын

@@enclave2k1 Programming languages are just tools, but C is like that hammer with a handle the stubs your hand with nails. Friends don't let friends use bad tools. But hey, if you like it, go ahead and use it :) If there is one language that isn't going to ever disappear, it's C.

@jadetermig2085 7 ай бұрын

@@dupdrop To ppl that have coded in C for decades, Rust is far more likely to feel like getting your hands stubbed with nails. When you have mastered a tool you begin to see it as a means to an end and you become frustrated when another tool gets in your way. I.e. I know what I mean and I know exactly what I want the machine to do, so don't get in my way. All languages influence the way you think about programming and problem solving through their syntax and semantics but rust is especially onerous in this regard.

@gorenbk 7 ай бұрын

@@enclave2k1 hi, im really not trolling. im a fan of rust, but this is kind of a joke. if you saw me as trolling, im sorry i made you feel that way. also tsoding has made really great apps in rust (noq, seroost). anyways, that was a joke, and a language is just a tool, it's just that rust is the tool that i enjoy using most. rust is obviously not objectively better! anyways, thank you for your reply!

@enclave2k1 7 ай бұрын

@@gorenbk Cool! Thanks for clarifying. Sorry for reading too much into your comment. I did love those series, I'm actively following noq in particular.

@monad_tcp 7 ай бұрын

Actually GCC should be part of the shell so it can run C code directly #! /bin/gccsh Even better, someone should propose an RFC for POSIX to have GCC as a shell.

@monad_tcp 6 ай бұрын

I was a dummy. There's this thing called C shell , they tried it , not good enough thou

@munawarcheema8991 4 ай бұрын

go_flags="-g -Wall -include allheads.h -O3" alias go_c="c99 -xc - $go_libs $go_flags" where allheads.h is the aggregate header you’d put together earlier. Using the -include flag means one less thing to think about when writing the C code, and I’ve found that bash’s history gets wonky when there are #s in the C code. On the compilation line, you’ll recognize the - to mean that instead of reading from a named file, use stdin. The -xc identifies this as C code, because gcc stands for GNU Compiler Collection, not GNU C Compiler, and with no input filename ending in .c to tip it off, we have to be clear that this is not Java, Fortran, Objective C, Ada, or C++ (and likewise for clang, even though its name is meant to invoke C language). Whatever you did to customize the LDLIBS and CFLAGS in your makefile, do here. Now we’re sailing, and can compile C code on the command line: go_c