Hashes 4 Hash Functions for Strings

[@sontiyo7113]

His jokes are killing me man I love this guy

[@xerxius5446]

what if i have shi.. never mind..

[@audreyjensen666]

06:05

[@mmahal]

@Harper Malcolm yea you guessed it right mate. No one cares.

[@Doctor_Hams_Dingus_Jam]

Writing on the glass whiteboard while it's in front of you is the best shit I've ever seen. I wish all my professors had this Edit: wait, how does that work? It's edited in, right?

[@andrewwaggoner8797]

video is flipped, if you saw it live from this angle letters would be backwards. nice how it makes it so easy to see

[@pepa007]

He started writing and I was like wait... how… holy smoke that’s genius! 😍

[@superuser8636]

“...returns all permutations of the string and [assigns a unique value according to order] ...” ... wow. Great explanation of finding all anagrams assigned a unique Val. These videos are incredible

[@justinlee6075]

I noticed a few things, and correct me if my thoughts are wrong. Hell, I may have completely interpreted the lecture wrong. 1) 116 + g(104 + g(105 + g(115 + g))) doesn't translate to 116 + 104g + 105g^2 + 115g^3. He may have meant to write 116 + g(104 + g(105 + g(115))). 2) That hashCode function at the end doesn't represent 116 + 104g + 105g^2 + 115g^3. I think it represents 116g^3 + 104g^2 + 105g + 115. (Although, that may have been intentional, in which that case, I apologize for pointing out the obvious).

[@markrayne5382]

this comment right here! you hit the nail in the head a fair few and confusing mistakes by the professor that needed clearing up

[@Funnybone_FB]

I noticed the same things! Thanks for posting so I know I'm not going nutty

[@MrYourMedia]

The character at index 6 is e; hehe

[@laneroberts8747]

@@abhishekavr1848 You are an idiot, you have had 8 months to respond and you respond with the wrong answer lmao

[@saineshnakra6045]

@@abhishekavr1848 Yeah , you probably want to count that again

[@moisesacero4995]

@@laneroberts8747 gawd dam ur pissy

[@laneroberts8747]

@@moisesacero4995 ya maybe... But the point is that he literally did not count. However, I do realize that what I said might be out of line. But @Abhishek avr is still an idiot

[@thepurpleone7153]

He IS right, its e. My name 0123456

[@a1988ditya]

6:05 THAT EPIC MOMENT :)

[@edrtjiud7752]

I think the correct "formula" of what you are writing (at min 7:30) is: s[0]*g^(n-1) + s[1]*g^(n-2) + ...+s[n-1]*g^0. (where s is our string and n = s.length()) The power you have to rise g starts from (s.length - 1). ex: s[i] * g^(n - i - 1) Using this formula you can do like this: for (int i = 0; i < s.length(); i++){ hash += Math.pow(31, s.length() - i - 1) * s.charAt(i); }

[@任安明]

edrt jiud does it matters？i think there is no big difference

[@syedasadalizaidi55]

why are we taking g as 31?

[@NourAli-hl4ih]

this is correct. his is g^0 then g^1... while yours is g^1 then g^0..

[@MammadovAdil]

I also noticed that, there should not be much difference but what he explained and what he coded are different. I think instead of using Math.pow, we can also just invert the loop to start from last element and to go down to first

[@seitarion4538]

Your iterating through indices, there's no need to calculate the descending index to raise the constant to that instead of just raising to the power of the index your currently on. They have the exact same effect.

[@user-og6hl6lv7p]

Beautiful explanation of basic string hashing, thanks!

[@songsmania1681]

why are we taking g as 31?

[@pressgreen]

It is a prime number which reduces the chances of collisions. I think lol

[@goutham24693]

From the explanation he gave, I think the code should be for (i = 0 ; i < size; i ++) { hash += s.charAt(i) * (pow (g,i)); } Not sure how he came up with, 116 + g(104 + g(105 + g(115 + g))) at 7:56. if I expand this I get, 116 + 104g + 105(g^2) + 115 (g^3) + (g^4) can someone explain this and the specific use of 31 ? Thanks.

[@Zach-cv4gu]

31 is optimal for computing hashing results

[@imanelamnaoir590]

Both methods are correct , the video used what we call the Horner method ; Horner's method is a technique used to efficiently evaluate a polynomial at a particular value ( the value is the famous g=31)

[@mayaayaviri1493]

im testing it right now and i get two different numbers using the two different methods@@imanelamnaoir590

[@karlloveridge8818]

Loved his explanation. If Hollywood ever needs to do a biopic about Donald Pleasence, this is the guy! He even sounds like him!

[@ZerofeverOfficial]

This video made me get it. Thank you for making it.

[@ashuvssut]

He applied Horner's Rule at 07:33 Applying this rule reduces the number of mathematical operations required to solve a polynomial. I came by this rule today morning only! See this vid kzbin.info/www/bejne/j2W1kHxvg8-fgqs

[@kirktelia]

Thanks a mill this made sense out of nonsense for me

[@goldenotis9703]

Thanks for that end part information. The strings get really big in the program where I’m trying to implement this function and I need to optimize it for speed.

[@_paralaks_]

I am autoliking these lectures. Like literally new video starts from the playlist, I hit like so I don't have to pause or go back to like.

[@code3design]

g = 31 is salting the hash? If 31 is for the purpose of a prime number, why 31 specifically? Nonetheless, one of the best lectures in explaining hashes. Thank you professor Edwards!

[@CapiEtheriel]

nope, it's not. you just needed to pick a G, any G would work as long as you used the same G everytime. 31 is a prime though, I know that helps avoiding collisions but I'm not 100% sure why.

[@OneStopMusic.]

there are a few reasons to use 31. 1. 31 being a prime number, it makes the distribution of hashes more uniform in comparison to a non prime number. The reason for this is that there is a high chance that prime number will be coprime with your table size (We are talking in terms of probability here, so it is not a 100% thing that it will be coprime). And thus it will reduce any patterns or cluttering of hashes to same value as there would be no common factors. 2. we don't want to use a larger prime number to avoid more time consuming arithmetic calculations. Feel free to add more reasons.

[@omparikh4426]

excatly what i was looking for!

[@Tin98Tin]

You solved my homework, thanks!

[@danielrnuttall]

@6:04 hahaha!

[@srijaljoshi3421]

Glad I'm not the only one who noticed lmao

[@justindoane7482]

Is he writing backwards?????

[@kamoroso94]

No they flipped the video in post.

[@uhmmcool2862]

no he is writing backwards

[@brandonlovatt]

look up The Learning Glass (he gives credit at the end of the video)

[@vaisuliafu3342]

he actually wrote it upside down but they flipped it post

[@catteixeira18]

@ops t170 I spat my tea reading this

[@nadimkazi2038]

Nice explained.

[@EvgenyAleshin]

Amazing explanation and presentation

[@syedasadalizaidi55]

why are we taking g as 31?

[@Skraticks]

Won't the hash number get really big for a large string? Would the hash number not pass the maximum allowed int?

[@Warrior33016]

After you get the hash number, modulo it by a prime number

[@diogodionisio8924]

Great job!

[@julianrivadera1224]

Grande pelado!!! me vas a hacer aprobar!!

[@nicolabombace2004]

2:15 is going to compile because of implicit Typecasting. There is no overload by return type!

[@robertt8748]

Thanks, this was very helpful!

[@shivendrasaxena2199]

which software is being used to make this. M curious

[@sliderBro]

I don't think you need any special software. Use a transparent slab of glass as your whiteboard, film from the other side (not the side the professor is writing on) and then use the mirror image of the frames.

[@xerxius5446]

they just flipped the image on horizontal axis and then they are showing it on the projector to the students ( and us )

[@kariabraham2998]

Great video

[@anudeepb5400]

Correct me if I'm wrong but charAt method is not overloaded and you cannot overload a method in java just based on its return type. It works because char is a subset of integer type.

[@gadirrustamli6216]

That’s correct. Int is 32 bits and char is 16 bits. So, smaller size types can be casted to bigger ones but not vice-versa. This is the increasing order: byte < short, char < int, float < long, double

[@switchwithSagar]

Hi, Thanks for the explanation, really appreciate the lectures. But I have some doubts. 1. Shouldn't the hash function @7:59 be -> 116 + g*(104 + g*(105 + 115*g)). 2. The code explained @10:15 generates the hash function -> ((116*g+104)*g+105)*g+115, This is not similar to the hash generated by the method we have discussed in the lecture. Below is the hash generator which I wrote -> I have pasted my hash generator just for reference (C++) int hashCode(const string& str, int g) { int index = str.size() - 1; // Take the last char of the string. int hash = 0; while (index >= 0) { hash = (hash * g) + str[index]; --index; } return hash; } Can someone help me out, on the doubts, or please correct me if I am going wrong somewhere?

[@Elxnicorojas]

His mistake was the way he visited all the positions of the array. His for() function should be like the next: (int i = str.size() - 1 ; i >= 0; i - -) Your solution is right bc it goes through the array in the same way tho. Sorry for my bad english and for answering this 4 weeks later

[@mattp6460]

thank you

[@rahulbawa6864]

heavy breathing! I hope the professor is keeping well. But such an amazing teacher.

[@bw2619]

very helpful, thanks

[@j1952d]

A bit late to the party, but IIRC (I'm old) origiinal ASCII was only 7 bits ( 0 - 127), leaving 1 bit in an 8-bit byte for parity.

[@miroslavsavel7560]

In which string can by hash value negative? Can you please give me example where the hashCode() return negative value? Thank you

[@SKeeetcher]

Never. Unicode is always positive

[@pleasethink4789]

1:25 m is incorrect for parameter 6. class Main { public static void main(String[] args) { String s = "my name is Rob."; char c = s.charAt(6); System.out.println("c is " + c); } } OUTPUT: c is e

[@robimez]

lost it at the Sh*t joke , never met many teachers with a sense of humor , take my like and subscribe even if you probably don't need it.

[@mernaiskander4607]

Are you right handed or left handed?

[@cristianmoldovan1429]

Got a like from me for the shit joke :))

[@TheCaffeinatedDrive]

6:05

[@simrandotdev]

He indeed is a funny teacher. I took one of his courses at SDSU.

[@DavidMwangikamau]

6:08 🤣🤣🤣

[@Capitalust]

Amazing

[@Alkis05]

Why aren't we counting from 0? I'm confused.

[@vamsisaivenkat]

man how its even possibile writing in backword ???

[@syedasadalizaidi55]

Perfect! but why are we taking g as 31?

[@qapoo5438]

I guess it's random thing. I picked g as 2 and it's working fine.

[@syedasadalizaidi55]

Isn't it a prime number thing?

[@htxdy]

the collision rate for bigger numbers are small when g is prime

[@amirnia47]

because characters in the ASCII chart starts from 32

[@daniyaniazics]

LOVE IT

[@pranavprabhu698]

Can you restore the string from this

[@fahimhuq2768]

AFAIK hashes are one way ; so, no.

[@markrayne5382]

this is wrong the hashcode produced should match by 116*31^0 + 104*31^1 + 105*31^2 + 115*31^3 = 3,425,965 the algorithm should give this hashcode also but does not the algorithm gives the hashcode - 3,559,070 *edit the reason for this was the professor represented the wrong expression as another comment said the expression is (116g^3 + 104g^2 + 105g + 115) and not (116 + 104g + 105g^2 + 115g^3)

[@altf4thc]

is this guy writing backwards though?

[@MammadovAdil]

Character at 6th index is not m, but not important )

[@大王-b1k]

Adil Mammadov should be e

[@aysenur3057]

space is also a character. so 6th is m. it's correct. not starting at 0.

[@phil5053]

He was about to write shit at 6:07

[@gngn2973]

how do they do this see through glass sorcery? my brain hurts every time i see it. I figured it might be a mirror but then his head should block text that hes written, but it doesnt. then thought it might be a see through white board. but then he would have to write everything backwards for it to be forward for us. i guess the only explanation is some type of hollywood movie magic? I dont know anything about cinematography though. Great video, wish it was longer. Cheers.

[@mohammadshahin4922]

they simply flip the video around and show it backwards

[@rukna3775]

6:05 - shit 😂

[@hazemyahea1588]

why 31 ?

[@yanivsh]

Actually CharAt works by starting at index 0 so his example is a bit wrong ('m')

[@tamdnf3214]

Wouldn’t g * hash always result in 0 since hash’s value starts at 0?

[@Lyser11]

No, you are adding s.charAt(i) to hash, so the first value of hash (after 0) will be the value of the first char of the string.

[@davidgeismar6531]

@@Lyser11 yes but that s different from the explanation he gave before when he was raisong g to the power related to the position of the char... so that confused me also

[@woofelator]

You should have used "sith" as one of the anagrams of this haha

[@ericlongteaches]

Position 6 should be e. Strings as char are 0 indexed

[@aminemaghous]

The problem with this technique is that if we have a long string, 1000 character for instance then in that case g^1000 can't fit in any number or lets it will be inefficient if it fits like in python

[@miladzamanzadeh2881]

I think he should return hash%31

[@abhishekavr1848]

I have a doubt . The logic he used in the for loop is different from what he explained. Is it??

[@JimmyCroissant69]

Can you please wear a black balaclava next time for better readability?

[@soniaxrp7353]

Didn't anyone else notice his charAt example was wrong? charAt starts at 0 index so should be 'e'! 2 minutes in, and it pissed me off.

[@MaxiLR_]

U r right

[@z08840]

kinda BS - you can't overload method by return type in java - code will compile because of implicit conversion char to int

[@JCiverJPonest]

Like

[@ericlongteaches]

Bro you worry too much about the math. We just wanna learn the concept man

[@WaseemHuweih-ql8bw]

my name is Jeff

[@laneroberts8747]

charAt() is not overloaded. Overloading a method can only allow it to have multiple input types, it does not allow it to have multiple outputs. This video is mediocre at best.

[@ohaRega]

Oh, you must be a genius XD We all know that what he *meant* was: the constructor for an Integer is overloaded, meaning, it has a version that takes in a character.

[@laneroberts8747]

@@ohaRega That is not true, I assume that you are saying, like any constructor there can be many ways to instantiate. That is the idea of overloading. However in this case, he is creating int i. int is primitive(which means that it is not a class) and as such has NO constructor... So no, he is still wrong, and ig now I can add you to the "Wrong list." lmao nice try though

[@ohaRega]

@@laneroberts8747 Actually, yes, you're right. That's my bad.

[@cybermindable]

way too much unnecessary personality and so very dumb writing actual code on the blackboard, especially semicolons ever heard about pseudo-code doc?

[@rocknroooollllll]

Robert! Please speak like a proper Englishman! It sounds so odd when you say "zee"! Can't you just say "zed" and let the students adapt?

[@reecebuckle397]

Are you kidding... with the amount of Indian tutorials with thick accents on youtube (not that I have a problem with that) and you're complaining about a rare white guy who's not only extremely easy to understand, but also goes at a slow detailed pace

[@markrayne5382]

he's not a proper Englishman though if he was he would be a professor in an English uni

[@kenanthompsonkilledmydog4753]

What was g? the hash table size?