Does it matter what hash function I use? (hash table example in c)

Рет қаралды 6,061

Күн бұрын

Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
Does it matter what hash function I use? // Continuing my hash table kick, let's look at hash function performance. There are a lot of them out there. How much does it matter which one I use?
Related Videos:
Original hash table video: • Understanding and impl...
A better hash table: • A better hash table (i...
Fixing that better hash table: • Fixing our "better" ha...
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]

Пікірлер: 29

@cleightthejw2202 Жыл бұрын

@Jacob I definitely want to see those cryptographic functions video//s

@elkhayder Жыл бұрын

@randomscribblings Жыл бұрын

If I was in the mood to benchmark hash table performance, I would also be tracking the distribution of collision lengths. If you think about the work required to retrieve a record, the non-hashed case is a list of 100k. Simple. If you produce, say, a max collision of 10 items --- that's almost noise level. But if your hash has lists of 1000 items, then you have a problem.

@anon_y_mousse Жыл бұрын

One possible backup would be to have the chains be AVL trees. Hash tables provide faster lookup than trees, sometimes, but if an individual chain devolves a tree would be better than a flat list. Of course, if you check the balance of the table at each insertion and/or deletion then you might opt to change the hashing algorithm used and rebuild the table. Which won't work if the data you're storing is opaque, and thus trees for chains as the last resort backup. Just remember to save the unnormalized hash value for each item as it can be a sorting factor that's faster than outright comparing individual items.

@unperrier5998 Жыл бұрын

How about perfect hash for the next video?

@samuelmartin7319 Жыл бұрын

I would love some videos on cryptographic hash functions

@vladalgov1770 Жыл бұрын

Function hash_table_lookup should return a pointer. But after the first check on NULL pointers it returns false. Note that this line was copied from the previous function hash_table_insert.

@tigrankashapov2288 Жыл бұрын

Great video

@jesselangham Жыл бұрын

SHA SHA SHA! DO SHA!

@noodlish 7 ай бұрын

I would be interested to see if changing the hash table length to a prime number has any effect on performance. I've read that this can reduce the likelihood of collisions depending on the hash function.

@zxuiji Жыл бұрын

6:35, personally I would stuck with the original but used it as a seed for a random number, slightly more secure, doubt it would effect the number of collisions though

@ankitlamba8875 Жыл бұрын

Hey Jacob, which IDE/Editor do you use for writing code?

@KangJangkrik Жыл бұрын

Visual Studio Code, with some C/C++ extensions

@sarahross7515 Жыл бұрын

Is there any way to pass a custom struct as a key to the hash function?

@Xiterlide Жыл бұрын

with such a generic function Jacob implemented, it should be as easy as: struct my_sctruct a = {/* init your struct, heap or stack */}; int hash = hash_function( (char *)(&a), sizeof(a) );

@sarahross7515 Жыл бұрын

@@Xiterlide if you pass the struct pointer to the function, it will just generate a hash using the pointer (say 0xdeadbeef) now if I try to lookup the key using the same value but with a different location then it will not be able to find the value

@Xiterlide Жыл бұрын

@@sarahross7515 I don't think so. In the video, the passed pointer is dereferenced in the function using the indexing syntax - data[i] - so this will in fact make hash out of the bytes of the struct in memory. The problem you're describing would arise if your struct contained a pointer - for that you would need to have a specific hash function I guess.

@anon_y_mousse Жыл бұрын

@@Xiterlide There's no need to cast it, just have the function take a void* or if you're specializing it for an individual project just have it take a pointer to the struct itself.

@brianb2308 Жыл бұрын

You can pretty much abstract anything like that, but after changing your key to a void pointer, you'd probably want to also take a function pointer for your hash and use that. Abstracting ideas is really good and good c libraries for hash maps will give you that option, maybe having 2 different data structures, one that's fully abstracted and the other being specific to strings. That's a somewhat common thing in c. If you want your data structure or algorithm to be abstract, you typically need to take a function pointer and void pointer somewhere. Another example of this would be sorting algorithms. You don't want to reimplement sorting algorithms for each data structure, so instead you make one that takes a void*, an int or size_t for the size of the data structure, and a function pointer that takes two void* and returns a bool depending on which is "greater", whatever the user wants to make that mean.

@AlyxCouch Жыл бұрын

Hi Im a CS student and am worried about AI making me obsolete before I even am in the field. What are you thoughts on all this? Will there still be people writing code in a few years or am I screwed?

@unperrier5998 Жыл бұрын

chatgpt is not a silver bullet. there is a need for someone to specify the input to chatgpt and assess the correctness / security in the context of the project. So our work will likely shift for some of us but we'll still be there.

@AlyxCouch Жыл бұрын

@@unperrier5998 So programming will change to prompt engineering? I like programming, it sucks that it's looking like that will change?

@sanderbos4243 Жыл бұрын

@@AlyxCouch Prompt engineers are of no use if they aren't able to fix any bugs/find any bugs in it. Just see prompt engineering like any other tool like Git / StackOverflow / Visual Studio Code, etc.

@ANT-jm4qx 10 ай бұрын

Some people still write and look at assembly code 40 years after compilers became commonplace so I think it's safe to say our jobs are going to stick around for a looooong time :D