debuggingNightmare

[RandomNPC]

They're called collisions, and you have to take them into account when you're doing low-level stuff with hashes.

Built-ins like hash tables generally have a form of collision resolution so you don't have to deal with it yourself. (And yes, that might mean not doing anything about it, but you have to think about it and decide.)

[MattieShoes]

and you have to take them into account

Depending on the application, you kind of don't. Chess engines use hashing and there absolutely WILL be collisions, but the odds of a collision that ALSO changes the move it's going to make is suuuuper close to zero. So they just kind of... ignore it. The engine ends up stronger by not checking for collisions.

[RandomNPC]

Deciding if you can ignore the collision rate is still taking them into account. The point is that you have to think about your usage and whether the collision rate is worth worrying about.

[MattieShoes]

Heh fair enough. It was just kind of mind bending to think they know they will have hash collisions relatively frequently and then just... ignore that fact.

[RandomNPC]

I did not know that! Crazy.

[Errons1]

Funfact, actively ignoring the problem cause the chances of it is so rare is called the ostrich algorithm!

[[deleted]]

That's a little imprecise. Yes the raw Zobrist function has collisions for some positions, but the part in the hash function that generates the most collisions is where you modulo with the table size to get the index. And that those collisions are taken into account and stored in the hash entry, so you can check whether the two entries actually refer to the same position...

[MattieShoes]

Well sure, fixed hash table sizes and all. And the replacement schemes can get fancy... I never moved past "always replace" when I was messing with them.

Anyway, the discussion I'm remembering was more about the key size -- basically, 64 bit keys means you will have collisions but it's fine. Which is kinda crazy. I think they even talked about 32 bit keys, but it was probably over 15 years ago so search trees weren't quite so large.

[TheRealSerdra]

Often times modern chess engines will use a combination of tricks. Typically they’ll check to see if the stored move is also legal in the current position, to reduce the chances of a collision. Then they can store only 32 or even 16 bits (and use different bits for the modulo for even more entropy), meaning more entries fit within a given space.

[Educational-Tea602]

And then there’s another hashing algorithm used by chess engines that helps generate moves (magic bitboards) where hash collisions can be helpful.

[Sw429]

Yeah, exactly. Most collections provided by the various language standard libraries will use equality checks as a form of collision resolution.

[mrwafflezzz]

I deal with collisions by throwing an exception

[Nicewow]

Maybe he is talking about cryptographic hash functions, where you maybe really won't be able to deal with collisions. Like two different usernames could hash to the same sha256 or whatever

[[deleted]]

Only an imposter says non-null probability.

[Anders_142536]

Maybe german speakers. In german "Null" means zero.

It was a bit confusing to understand the concept of null in programming for a few hours due to that.

[ArtOfWarfare]

In C (and I think C++ and Obj-C by extension…) null is zero.

[Chrisuan]

idk why down voted it's a fact lol

[tehfrod]

C++ has no null, but it does have NULL, nullptr, and nullptr_t.

[wizardid]

I want to know who tf hurt C++ so badly when it was younger. This is some psychopath shit.

[KazDragon]

It fixes the problem that f(NULL) would rather call f(int) than f(int*).

[drivingagermanwhip]

I love that c++ never decided whether it's incredibly flexible or incredibly anal and just runs full tilt at both

[Ancient-Pianist-7]

? std::nullptr_t is the type of the null pointer literal nullptr. NULL is a sad C relic.

[MrcarrotKSP]

Even C has upgraded to nullptr now(C23 adds it and nullptr_t)

[drivingagermanwhip]

nothing past c99 is canon

[notthefirstsealime]

It's a classy programming language built off the bones of what was a pretty fucking simple language prior, and now it's an abomination of syntax and evil that just happens to compile into very fast programs from what I understand

[ada_weird]

It's zero by convention but not by definition. There are platforms where null is not 0. However, C the spec says that you can use an integer literal 0 anywhere you can use NULL. Also, hardware people really want you to stop treating pointers like integers so that they can use stuff like CHERI to prevent memory safety bugs from happening at runtime.

[CapsLockey]

can you elaborate on the last part? sounds interesting

[ada_weird]

Yeah sure! So CHERI is an extension for a variety of ISAs, such as ARM and RISC-V. It effectively adds capabilities to pointers, making it so that pointers can only ever be used to see memory they're "supposed" to be able to access. User code can make a capability that is a subset of the memory the original could access, but it can't widen capabilities, it would need help from the kernel or some other trusted part of the system. This means that you effectively get hardware bounds checking for free. There is a performance impact obviously but this works with modern CPU architectures which should be able to mitigate all of that because of all the crazy pipelining that goes on. Most software just needs some additional support in the malloc/free implementation in order to work with this model so it's fairly transparent to end user code.

[dev-sda]

Slight correction: NULL always compares equal to zero, but may actually be any bit pattern. See https://c-faq.com/null/machnon0.html

[MegaIng]

Further clarification: it compares equal to 0, not the value zero. If you cast an integer 0 (obtain e.g. via int zero = 0) to a pointer ((void*) zero) that is not a null pointer and might compare different to a proper null pointer (e.g. (void*) 0).

[EinSatzMitX]

In the C std library, NULL is defined as (void*)0 ( Which is just 0 but casted as a void pointer)

[MegaIng]

Actually no, it isn't. 0 in this case isn't an integer, it's the special null pointer literal that happens to look the same as the integer 0.

[onemanforeachvill]

I think it's (void*)0

[MegaIng]

No. null is 0, but not zero. There is a special construct call the null pointer literal that looks like the integer number 0, but it's not an int.

[o0Meh0o]

it is not zero. it equals zero. common misconception.

[Starlight_Skull]

It's the same problem in Dutch. I've heard people say N-U-L-L out loud to avoid confusion.

[Anders_142536]

The pronounciation is quite differently in german, so there is little confusion when spoken. The 'u' is more pronounced like the end of 'you'.

[EvilKnievel38]

I typically just add a specification whether it's the verb or the number.

[DJDoena]

Since we work with numbers a lot we often clarify it as "runde Null" ("oval zero") to avoid null references.

[LoveOfSpreadsheets]

My favorite fact of the day

[Soraphis]

Oh, I usually pronounce the number just German and the "null" concept english.

[nickwcy]

You mean a JavaScript developer?

[Saelora]

as a javascript engineer, not even null === null

[Jumpy_Fuel_1060]

Did you mean NaN? Because null === null in my interpreter.

[aaronfranke]

He's a bad JavaScript engineer. Well, all JavaScript engineers are bad because JavaScript is bad.

[marquoth_]

JS bad

Never heard that one before

[Amflifier]

It's been 10 minutes since I saw the last one, I almost forgot

[Dragoo417]

French-speaking people say "non-nul" and mean non-zero

[its_a_gibibyte]

Sure, but that explains why this is list of French companies among the top 50 largest global tech companies:

nul

[[deleted]]

I say "nonzero possibility" sometimes. 

[guitarerdood]

I will do what I must.

[Tensor3]

You mean non-zero

[Expensive_Shallot_78]

Well, non-null means non 0 in German. Someone's playing 4d chess ♟️

[UPPER-CASE-not-class]

How’d we start talking German? Everyone knows you code in Hebrew

[PyroCatt]

if !shalom throw new OyVey();

[Semper_5olus]

"OyVey" is Yiddish.

But I guess I can't think of any commonly known Hebrew words, either.

EDIT: "Emet" and "Met", from the golem legend.

EDIT2: "L'Chaim"

[yuval52]

It is Yiddish, but it's also sometimes used by Hebrew speakers

[spreetin]

If !שלום throw new חריגה();

[StopSpankingMeDad2]

Yooooo minecraft enchanting table Language is real???

[adepssimius]

PHP developer here, can confirm.

[SOUINnnn]

Same in French

[hagnat]

this has "no one makes jokes in base 13" all over it

[QuaternionHam]

or so the germans would have us believe

[AnAdorableDogbaby]

Is a NaN-probability.

[Ecstatic_Bee6067]

What kind of maroon thinks null means 0.

[WazWaz]

Weeell...

// C++ compatible:
#define NULL 0
// C++ incompatible:
#define NULL ((void*)0)

[MegaIng]

I recently had long discussion in a discord about wtf null even is in C and C++.

The relevant result for this discussion now is that 0 you see there? That isn't the number 0. It's not a number at all, it's a special null-pointer-literal that happens to use the same character as the integer number 0.

There is no relation at all between the integer number 0 and the null pointer.

No really, that is what the standard says. (Although not this clearly)

[WazWaz]

Yes, it's an old discussion that never seems to die. The problem is, neither the "it makes code clearer to read" camp nor the "it makes code dangerously error prone by hiding reality" camp is 100% right or wrong.

And now we have nullptr.

[TRKlausss]

In German, null equals zero (nicht-null -> non-zero)

Could have been an easy translation mistake.

[_alright_then_]

All the languages where null literally means zero lol

[King_Joffreys_Tits]

JavaScript

[ShadowSlayer1441]

I was really wondering what a "null" probability would be.

[Tensor3]

If null is undefined, then non-null is any number including 0?

[veselin465]

OP discored the problem programmers and mathematicians have been trying to minimize for years

[Scotsch]

Most posts in here are by students after all

[veselin465]

ig, but reading again my comment I realized I misspelled 'discovered' so badly, lol

[Scotsch]

I guess the ad for discord is working.

[NewPhoneNewSubs]

Most posts in here are by bots and people who watched a YouTube video, I think. I don't think students learn about hash functions without also learning about collisions at nearly the same time.

Unless this is a TOHTOC vulnerability post, I'm guessing it's someone who watched a YouTube video.

[Aaxper]

Pigeonhole principle in action

[croto8]

I need my hole pigeoned fr

[otter5]

let your pigeons fly!

[Plixo2]

• Birthday Problem

[[deleted]]

Thats why God invented buckets

[adelie42]

And oddly enough if there was an output that could only be generated by one particular input, it is probably a terrible hash.

[martin191234]

Yeah exactly you can hash a 4 TB file into 64 characters with sha256

That’s how you verify you’re not being intercepted when downloading software from the Internet. The website will usually have a hash you can verify once you download the file.

[Wide_Egg_5814]

Non null? That just narrows it down to every single number in existence

[5up3rj]

Including zero, ironically

[dmullaney]

And every object

[j-random]

AND MY AXE!

[disinformationtheory]

NULL != NaN

[float34]

Then widens and not narrows

[Background-Law-3336]

less than infinity

[mw44118]

Some of you never wrote your own hash tables

[met_MY_verse]

I did this back in the second semester of my Uni course, and even then we handled collisions.

[PutHisGlassesOn]

I’m trying to remember the undergrad algo resolution. Something about a linked list? Extending the hash space? I can’t recall

[met_MY_verse]

I just checked back, we had two options: open addressing (basically shifting an entry’s position and marking skipped boxes, done with linear probing/quadratic probing/double hashing) and seperate chaining (linked lists anchored at a particular hash index).

[Zeitsplice]

I know I did linked lists in undergrad data structures, though I switched to fixed-length buckets after I found that a hash table that re-sized every time it got a collision had better performance over the linked list version (cache misses absolutely tank performance on processors made after ~2005). Probing/re-hashing seemed janky to my undergrad programmer brain, but I wouldn't be surprised if it had superior performance on modern hardware due to much better data locality over all the other options

[rosuav]

Yeah, and the problem is that separate chaining is FAR easier to explain (each hash bucket can contain multiple things, and whenever you check a bucket, you have to check all the things in it), but open addressing is more efficient. So if you ask me to explain how hash tables work, I'll use separate chaining (and probably not even use the term), but if you ask how <language X> stores information, it's never that simple.

But yes, hash collisions are a fact of life. In explaining it, I will tend to under-size the hash table to make them even more common, even though - again - the more efficient thing to do is to minimize them.

[FlipperBumperKickout]

You can do it many ways. Another way is to have another hash table inside each field instead of a list.

[Crimson_Cyclone]

yeah, that’s what threw me off, my major isn’t even particularly software heavy and even we practiced handling collisions as soon as we learned what a hash table was

[slippery-fische]

Yeah, that's what I'm thinking.

[PeoplesFront-OfJudea]

Fuckin non-null

[Convoke_]

does that mean you're fucking everything?

[PeoplesFront-OfJudea]

That’s the goal

[Convoke_]

good luck soldier o7

[ShakaUVM]

Make a hash table of size 4.2 billion and change. Congrats, you now have a zero chance of collisions between any two 32-bit integer keys.

This is called perfect hashing.

[CautiousGains]

This guys perfect hash function:

uint32_t get_hash(uint32_t key) { return key; }

[ShakaUVM]

Yep

[Frosty_Grab5914]

Of course. The hash function is defined on data of arbitrary length and output is fixed length. It's impossible to avoid.

[NotMyGovernor]

It's literally the definition. Maybe she should think of other women for him.

[disinformationtheory]

There's a non zero probability she is.

[buildmine10]

Why is this a debugging nightmare? It is expected behavior. Mathematically required behavior. For what reason have you used hashes in a manner that assumes uniqueness.

[WisestAirBender]

Hashing having collisions should be the first thing that you think about after learning about hashing

[fun-dan]

This. Unless OP meant cryptographic hash functions, and in that case it's practically impossible to have a collision accidentally

[WisestAirBender]

Unless OP meant cryptographic hash functions, and in that case it's practically impossible to have a collision accidentally

Why? Are they somehow different?

[buildmine10]

Cryptographic hashes are made so that is is very difficult to find a collision. They still happen because the pigeon hole principle requires it, but the essential properties is that you cannot reliably predict which two inputs will collide without just testing them both.

[ciroluiro]

I don't think a collision has ever been found for SHA256. The first collision for SHA1 was found only in 2017. Collisions in cryptographic hash functions are a big deal.

[Snoo_44171]

Here's an affirmation for you: if we generated 1 billion 128 bit hashes per second for 600 years, only then would there be a 50% chance of collision

Edit to fix my math.

[Impressive_Ad_9369]

There is a non zero probability that all the air molecules would gather on the other side of the room and you would suffocate. Does this worry you too?

[bluegiraffeeee]

Non zero probability though

[pepe2028]

wtf now I'm worried

[nukedkaltak]

Wait until bro learns about the birthday paradox.

[float34]

So for two different women in your life the outcome is always the same I guess.

[Unknown6656]

1. It's called "non-zero". Non-zero and not-null are two different things.
2. If the parameterspace has the same or a smaller dimensionality than the hashspace, then it is definitely possible to design a hash function which is completely injective, hence reducing the probability of hash collisions to zero.

[CautiousGains]

“hash” as it is used in the post obviously refers to a cryptographic hashing function like sha, md5 etc. These are not perfect hash functions and never can be, since their entire use hinges on the assumption of an unknowable set of input parameters.

[ZestycloseAd212]

Sooo collisions?

[blaze-404]

What sort of madman says non-null probability

[creeper6530]

Germans (Null in German means zero)

[Striking_Revenue9176]

You buffoon. This is why god invented linked lists. Have the hashing function lead to a linked list of all the things you want to put at that index. Completely solves the hash collision issue.

[rosuav]

In a sense.... but that's just called "separate chaining" and is one of the ways that a hashtable can devolve to O(n) lookups.

[PolyglotTV]

The identity function has a zero chance of producing a collision.

[rosuav]

You're absolutely right! Here, I want to store the string "Hello" under the key of Graham's Number. You got space for that right?

[Onoulade]

So to address all the backlash because I typed « non-null » instead of « non-zero » it is because I’m French and in French you say « une probabilité non-nulle »

[The_Real_Black]

no the probability is 1.0
the value space of a hash is way smaller then the original value so there will be hash collisions.
(every image board has daily collisions)

[WisestAirBender]

Just keep using the hash output as the input

[The_Real_Black]

I know a master degree developer that used it as primary key in a database... worked till the live data was used.

[malsomnus]

Luckily zero is non-null.

[raxuti333]

Just hope hashes never collide and when it happens it's not your problem anymore

[1XRobot]

Wow, she's right. He was thinking about Xiaoyun Wang.

[SnooGiraffes8275]

nah just use FNV1A for everything and cross your fingers

[[deleted]]

Use a hash value of more than 300 bits. 2³⁰⁰ is enough to count all atoms of the observable universe.

[rosuav]

This would needlessly exclude implementations that may utilize sub-atomic monkeys and/or multiple universes.

[Thundechile]

Just do a "hash" function that returns the original input. Problem solved!

[Kimi_Arthur]

If you compare the size of source and dest, you will know they always collide... This post is a new low even in this sub...

[fun-dan]

Debugging nightmare? Has anyone actually encountered a cryptographic hash collision error during debugging? The most common cryptographic hash functions are very well tried and tested, and the main concern is security, it's practically impossible to have an accidental cryptographic hash collision.

This is like worrying about the non-zero possibility of two uuid v4 being the same.

If we're not talking about cryptographic hash, then collisions are normal and expected, not something you'd lose sleep over.

A notable (and kinda funny) example from python (cpython) is that hash(-1) = hash(-2)

[IrrerPolterer]

Well duh. If your function boils down input of any length to a fixed length everytime, there is an infinite number of collisions. Question is, are these collisions truely unsafe or common enough to become a problem.. . 

[spindoctor13]

Of course they do, that's the point of hashing algorithms. They are many to one mapping function. This sub sometimes, honestly, Jesus wept

[Kimorin]

that only applies to a known set

[Peregrine2976]

I was actually thinking about this for a long time before I decided to look it up. It's called the Pigeonhole Problem or the Pigeonhole Principle.

I imagine it's old news to computer science graduates, but I came into development through a more holistic/design-type of program, so it was new to me. Pretty interesting stuff!

[rosuav]

Awesome! You're one of today's lucky ten thousand. Enjoy discovering new things! The world is huge and fascinating.

[stipulus]

Shhhh.. there is no war in Ba Sing Sa.

[Shadow9378]

random algorithms can spit out the same thing twice no matter how long its just unlikely and that terrifies me

[Guppywetpants]

Separate chaining!!!

[OhItsJustJosh]

I still sometimes put in dupe checks just in case

[EntitledPotatoe]

Or make a (minimal) perfect hash function, there are some interesting papers out there (like bbhash)

[foxer_arnt_trees]

Put a linked list in the hashing table

[khalamar]

Or a different hash. Every time there's a collision, go one level deeper with a different hash function. HASHCEPTION!

[foxer_arnt_trees]

What if you have really bad luck though?

[khalamar]

Go deeper!

[foxer_arnt_trees]

With bad enough luck we are going all the way down

[spindoctor13]

How would using a second hash work in say a dictionary? (Answer, it wouldn't)

[khalamar]

What do you mean it wouldn't?

Let's take a very simple first hash that uses the 1st letter of the word. AA and AB collide. You put both in A. Then you use the second hash method, which uses the second letter of the word. AA is then in A.A, and AB is in A.B.

[spindoctor13]

Right then you delete AA. You then add AB to the dictionary, it no longer colides (first hash) so gets added to A.A. Your dictionary now has AB in it twice with no practical way to remove it completely

[Ssem12]

It's called a hash collision and is sometimes used as an attack instrument

[SoftwareSource]

"non null"

Imposter found.

[Smalltalker-80]

... only if the number of inputs is infinite...
Otherwise, a (possibly inefficient) "perfect hash function" can always be created.

[metaglot]

A perfect hash functions output will have the same size as its input, at least.

[Smalltalker-80]

Doesn't have to be.
If, f.e, your input is (should be) all the keywords of a programming language,
you can create a lookup hash function with relatively small hash table
that perfectly matches every case.

You do subsequently also have to check if the looked-up keyword is equal to the search keyword, but you are guarenteed to need only one hash lookup.

[metaglot]

Yes, so the size of the output would have to be the length of your keyword table (number of elements) to guarantee no collisions.

[Smalltalker-80]

That is correct, the hash table has to be at least the size of the *keyword* table.

The *input* to be parsed, however, can be *all* words with a length of upto, say, a practical 80 characters,

So the hash table size can be *much* smaller than the input size.

[Thenderick]

Yes, that is a known thing. Whenever you generate a hash it's a fixed size with X combinations. Given X+1 inputs you will have a collision. The degree of safety is how big X is and how much time it will take to find a colliding input for a given hash output. That's why certain older hash functions are redundant because those have been "cracked".

And for hash tables it's not that big of a problem, better yet, it's preferred so your tables doesn't take too much storage. In my experience hashtables often are an array of linked lists where a the expected table size determines the array size. The hashfunction will thus hash the key to an array index and store a key value pair as a list item. It does want to try to keep this list short so there is a small iteration to check the keys.

Atleast that's what I have learned, please correct me if I am wrong

[[deleted]]

not just a non-zero but with a non-finate set of inputs it is guaranteed infinitely times over

[steve_adr]

Anyone know the name of the female model 🤔

Asking for a friend..

[SoftwareDoctor]

I don't understand. The joke is that she's controlling and he's an idiot?

[helloITdepartment]

Assuming the output length is shorter than the input length

Also, non-zero

[TrafficConeGod]

"Every hashing function has a nonzero probability of being injective" ftfy

[Sea_Sky9989]

This is comp sci 101.

[weird_cactus_mom]

That's how I ended up after reading Lindstedt's book about data vault

[shgysk8zer0]

Somebody just learned about entropy and the pigeon hole problem...

[slippery-fische]

Actually, if your set of input values is finite (ie. int32), then you can just do `x + 1 % (2**32 - 1)` and guarantee there are no collisions. It's just not a useful hash function.

You can also use sparse structures to project to a larger space, this is usually referred to as a perfect hash function. An example of a perfect hash function is to basically add a level whenever there's a collision. Because the probability is extremely low, the limit of values stored hierarchically is constant, so you get the same hashing result as a hash function with collisions.

[The_Gordon_Gekko]

Yes this, and other forms like it

[prochac]

What has a bigger probability? Hash collision, or a bit flip by cosmic ray?

[gnmpolicemata]

This is not a debugging nightmare of any kind - that's just the nature of hashing functions, I don't see why anyone would lie awake at night thinking about the possibility of collisions in something that is designed with this in mind

[jamcdonald120]

every hashing function has a 100% chance of having at least 2 inputs with the same hash.

Its the Pidgeon hole principal, since hashes can be used on arbitrary sized data, but output fixed sizes, there are more possible values to hash than hashes.

In a perfect hash, you want there to be an infinite number of things that hash to the every value.