Chat for kelalaka and Aurelius

« first day (1 day earlier) last day (15 days later) »

Ella Rose

17:40

← 147 messages moved from The Side Channel

kelalaka

yes

Aurelius

why?

kelalaka

Did you solved your issue?

Aurelius

I am trying to switch to another strategy

the problem with the SHA is that i get numbers that are too big

kelalaka

The problem is the approxiamations.

Aurelius

17:45

I wanted to use it as an almost perfect hashing function

for any type of data

kelalaka

almost perfect?

Aurelius

as input

almost perfect because a perfect hashing function would never have collisions

Perfect hash function

In computer science, a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. In mathematical terms, it is an injective function. Perfect hash functions may be used to implement a lookup table with constant worst-case access time. A perfect hash function has many of the same applications as other hash functions, but with the advantage that no collision resolution has to be implemented. == Application == A perfect hash function with values in a limited range can be used for efficient lookup operations, by placing keys from...

SHA just has a very low collision probability

with 256 bits

so I came up with almost perfect

kelalaka

well, if we assume that the input size > output size, the collisions are inviitable.

Aurelius

not every hash function has a fixed output

bust sha does

even if we could take a sha with 2048 bits

and have an input lower or equal to 2048

we would still get "addresses" that are extremely huge and unusable

things like

98198198719719794984984984984984984984223294487176121899554298419849

you can't use that number to address anything in a computer

kelalaka

do you want addressing?

Aurelius

17:54

yes

but basically I wanted to build some sort of hash table

kelalaka

Then, a collision resistant any function is enough for you.

Aurelius

Cuckoo hashing

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table, with worst-case constant lookup time. The name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches; analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location in the table. == History == Cuckoo hashing was first described by Rasmus Pagh and Flemming Friche Rodler in 2001. == Operation == Cuckoo hashing is a form of open addressing in which each...

how about this?

what do you mean by that?

kelalaka

This subject goes into CS :)

Q: What are the advantages of cuckoo hashing over dynamic perfect hashing?

Dynamic perfect hash tables and cuckoo hash tables are two different data structures that support worst-case O(1) lookups and expected O(1)-time insertions and deletions. Both require O(n) auxiliary space and access to families of hash functions for their operations. I think that both of these d...