Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hash-function]

For questions about hash functions: functions from a big set to a smaller one such that the same output $f(x_1)=f(x_2)$ for different input $x_1\ne x_2$ is unlikely, especially if $x_2$ differs from $x_1$ by a random error or is crafted by an adversary.

2
votes
1answer
75 views

Why Proof of Work is Hard

I am finally beginning to understand how Proof of Work (PoW) works, and am wondering briefly why it is considered "hard" mathematically to solve. The whole goal of it (it sounds like) is for it to ...
0
votes
1answer
22 views

True or False: After inserting '(2/3)m' elements into a hash table of size 'm', the probability of a collision upon the next insertion is at least 1/2

I was asked this question today, and my initial thought was - let's check a numeric example. So $m$ is obviously a multiple of $3$, and the smallest possible value is $m=3$. I divided the sample ...
1
vote
0answers
15 views

Non-reversible primitive operations on integers [closed]

Along the lines of How to map 256 unique strings to 256 unique but effectively arbitrary integers, I am wondering how to generate basically a hashing function. For this question I am wondering if ...
0
votes
1answer
93 views

Expected maximum number of collisions for universal hash function

If we hash a set $S$ of $n$ keys into a table of size $n$ with a universal hash function $h$, what is the expected maximum number of keys that collide? We break down this computation into a sequence ...
0
votes
1answer
19 views

Hash function that describe solid tetromino in the table

I'm trying to find a hash function that describes solid tetromino in a matrix 4x4 consisting of '0' and '1'. Here is what I mean: 1) 1111 0000 0000 0000 - solid tetromino, all this ones have the same ...
0
votes
1answer
28 views

Distinguishing cryptographic properties: hiding and collision resistance

I saw from Another question the following definitions, which clarifies somewhat: Collision-resistance: Given: $x$ and $h(x)$ Hard to find: $y$ that is distinct from $x$ and such that $h(y)=h(x)$. ...
2
votes
4answers
124 views

Can different source files produce the same hash value?

It is often said in judicial opinions and legal briefs that the hash value derived from a file is like a fingerprint that uniquely corresponds to the source file. While this may be true in a practical ...
0
votes
0answers
42 views

What enables hash function to produce uniform distribution given any distribution of input

I always take the uniformity of hash output as a given and didn't think much of it. Now I am kind of curious, how does good hash function like sha guarantees output uniformity. Intuitively, given 1:1 ...
0
votes
1answer
51 views

What is the probability that the first collision occurs at the Kth insertions?

Question Consider a hash table with $n$ buckets, where external (overflow) Chaining is used to resolve collisions. The hash function is such that the probability that a key value is hashed to a ...
0
votes
1answer
39 views

How to calculate Pool reward for Race of Work?

I invented a new concept called Race of Work. It's based on Proof of Work, except there is no difficulty. Instead, there is a predefined time in each hour that consider being Block time. During the ...
1
vote
2answers
75 views

Why are those hash functions considered a bad choice?

Given Hashtable $T[0,..,m-1]$ and $U = \{0, . . . , n − 1 \}$ set of possible keys $k$ with $m \ll n$ Let $$h: U \rightarrow \{0, . . . , m − 1 \} $$ I am trying to understand why the hash ...
1
vote
1answer
35 views

Given a square grid of side length N and m objects, design a bijection between each object and a unique set of coordinates

Given a square grid of side length N and m objects, can I design a 1-1 relationship between each object and a unique set of coordinates in that 2-D plane? Imagine the context being something like ...
1
vote
1answer
45 views

Given a boolen hash function (based on XOR), find the $n^{th}$ key for a specific hash.

A boolen hash function is given that takes a hexadecimal key as input and returns the hash for that key (hash can be only 0 or 1). The hash function is based on XORing bits of the key. For example, ...
-1
votes
1answer
73 views

Finding collision probability of hash function using modulo operation

I have a hash function which maps elements from a set A to another set B. The size of the two sets are n and m respectively (with n >> m). The hash function is of the form - $h: x' = x \; (mod \; m) \...
1
vote
1answer
42 views

Days required to collide at least one hash? [closed]

Sorry I am new here and learning mathematics and cryptographic problems. Assume an hash algorithm is collision resistant like SHA256, and the hash value is 64bit in length, (2^{64} possibilities) ...
1
vote
0answers
79 views

Hash without overflow

I am trying to hash an $n$-character string into one of $m$ slots by treating the string as radix-128 number without overflowing a 32-bit word, where $0 < m < 2^{31}$. I utilize the properties ...
1
vote
0answers
87 views

2-universal family of hash functions and $\varepsilon$ good

Let $V=\{0,1\}^m$ and $H\subseteq V\to V$ a 2-universal family of hash functions. Fix two sets $A,B\subseteq V$. Call a hash function $h\in H$ $\varepsilon$-good for $A,B$ if: $$ |\Pr_{x\in V} [x\in A ...
1
vote
1answer
17 views

Existence of a Perfect Cryptographic Hash Function

Is there a hash function that satisfies all the following properties: 1. It is 1 to 1 (no collisions). 2. It can take any size input. 3. For any input, and some desired set of characters, there ...
2
votes
1answer
115 views

Representing a String of n characters, as a unique integer

So I have been following the lecture series on algorithms from MIT. I got to the part on Rolling Hashes and Karp-Rabin algorithm Karp Rabin Notes The way I understand it is in order to represent ...
1
vote
1answer
183 views

Calculating probability of no hash collision

Given a 64-bit hash function that takes arbitrary inputs, what is the probability that feeding 10 million inputs into the hash function will outputs 10 million unique outputs. I've came up with this: $...
1
vote
0answers
53 views

What is the graph of my chances to mine a bitcoin?

Consider the next hashing definishion of $f(x)$ $$f(1) = 100$$ $$f(x) = \operatorname{SHA-256}(f(x-1))$$ Where $x$ is a positive integer and SHA-256 is the hash algorithm. You can think of SHA-256 ...
5
votes
0answers
79 views

Bloom Filter with an interval input

I have been trying to design a variant of a bloom filter that can insert an interval of values at once, as well as query if a certain interval is in the bloom filter. I haven't been able to think of a ...
0
votes
1answer
79 views

Universal hash function with probabilty of multiple collisions

The problem is: Consider the universal hash function: $h(x, r) = x_1 r_1 + ... + x_d r_d \mod m$, with $m$ prime, where for an integer dimension d>0 you break up the key $x=(x_1,x_2, . . .,x_d), 0 \...
5
votes
0answers
219 views

Bloom filter optimization on an interval of inputs

I'v been tackling a problem with bloom filters. I have a basic version working on paper, but I need to be able to put a large interval of numbers into the filter at a given time. Let ...
3
votes
1answer
868 views

What's the difference between a fingerprint and a hash?

My understanding is that both a fingerprint and a hash are functions that take as input some arbitrarily long bitstring, and output a bitstring of a fixed size. The Wikipedia page for Hash Functions ...
0
votes
1answer
52 views

Expected number of unique selections

If I'm selecting $N$ elements uniformly at random (with replacement) from $\{1, \dots, M\}$, what is the expected number of values that are selected exactly once? The basis for this question ...
0
votes
1answer
53 views

Finding all keys that hash to the same index

In my algo class, we discussed how uniform hashing algorithms aren't the best since it is possible to generate many keys that all hash to the same location. Take this hashing algorithm for example: ...
1
vote
1answer
31 views

Hash function to determine whether two vectors had an equal entry on some row

Do you know about a hash function, that approximates (in probability) the following function: Original function: Two vectors collide if there is a row where their entries are equal. $$ \text{E.g., }\...
1
vote
1answer
454 views

If k-universal hash family then (k-1)-universal hash family

A family of hash functions $H = \{h: U \rightarrow \{1, \ldots , m\}\}$ is called k-universal (or k-independent) if for every distinct $\{x_1, \ldots, x_k \} \in U$ keys and for every $\{i_1, \ldots, ...
0
votes
2answers
52 views

Sum of weighted integers.

I have to calculate hash value for an array of integers. The array has $8$ integers always, and the integers are a permutation of the integers from $1$ to $8$. For example, the array can be like this: ...
1
vote
0answers
80 views

Gradient noise hashing.

I'm working on a gradient noise function based on Simplex noise that uses simple squares instead of triangles (for performance and to avoid the patent for 3D noise). The original Simplex noise ...
1
vote
1answer
72 views

P vs NP, Has anyone proved there is no such thing as a collision-less one-way function. [closed]

I know that there has not been a proof against or for, the existence for a true one-way function. But i was wondering has such a thing been proven for collision-less (injective) one-way functions.
1
vote
0answers
153 views

Universal Hashing - probability of collision

I can't seem to get my head around a following conclusion: Def: H is a finite set of hashing functions from U to [m] (set of size m). We'll call H universal if: $\forall x,y; x\ne y $ there exists $\...
1
vote
1answer
45 views

3 Letter Initial Phone Keypad Hash Distribution

I have written a c++ function that generates a 3 digit number corresponding to each letter in a random 3 letter initial and their location on a phone keypad. For Example, my initials MSG, would return ...
0
votes
0answers
372 views

Why is this hash function for english words is perfect hash?

I have a question that seems really intuitive to me but I can't think of a way to prove it. Assume we a have a file with words that are different from each other and contain digits only for example ...
0
votes
1answer
54 views

Hash Table Dynamical Resizing

I read the concept about dynamical resizing hash table from this lecture. And for my understanding, it claims that the average run time of all insertions is $O(1)$ for each iteration. Now, suppose we ...
3
votes
1answer
48 views

What is the distribution of $x^2\pmod p$ where $p$ is a prime number, and $x \in \mathbb{Z_p}$?

Let $p$ be a prime number. How will numbers get distributed in $\mathbb{Z_{p}}$ upon doing $x^2 \pmod p$ where $x \in [0,p]$ is an integer? My approach: Let $p = 97$. Then, $x^2 \equiv (97-x)^2 \pmod{...
0
votes
2answers
1k views

Are there any reversible hash function?

I read about hash function and I know that there can be some $x$ values which lead to the same $y$ ($x$ is the parameter of the hash function, $y$ is the result). Is there a way, given a $y$ and a ...
1
vote
2answers
207 views

How many SHA-256 hashes of emails are duplicates of each other?

There are $5$ billion unique email addresses in the World. If I created a database containing their SHA-256 hashes, how any unique hashes would we expect that database to contain? By my crude methods,...
1
vote
1answer
46 views

Birthday paradox over power law distribution

In the classic birthday paradox problem we assume a uniform distribution of birthdays across the year, i.e. $p(x)=\frac{1}{365}, x=1,2,...,365$. What is the coincidence probability of two birthdays if ...
1
vote
0answers
107 views

MinHash single vs multiple hash functions

I'm trying to get familiar with MinHash function, and there are a few things a do not understand: Why to use multiple hash function version over single hash function alternative? MinHash wiki says - ...
0
votes
1answer
158 views

Beginner level understanding concept on how to derive probability of hash collision

A hash function indexes all items in hash tables and searches for near items via hash table lookup. The hash table is a data structure that is composed of buckets, each of which is indexed by a hash ...
0
votes
0answers
106 views

Generalization of Birthday Problem over Sets of Dates

At the classic version of the birthday problem we check for collisions of scalars $ b_i $ sampled from a uniform distribution. How can this be generalised over sets with more than one samples per ...
0
votes
1answer
12 views

Equivalance of statement

I was studying this paper Similarity Estimation Techniques from Rounding Algorithms by MS Charika Inside specifically had this ...
0
votes
0answers
80 views

Ordinal hash function

Suppose I have a set of integers from 0 to 100. Is there a non-invertible operation where the result is guaranteed to have the same ordinality as the input? In other words, given ...
0
votes
2answers
108 views

Understanding locally sensitive hashing

I recently studied about locally sensitive hashing an a follow explanation was given to me. To produce a hash for a particular vector X with dimensions 5, Draw 10 random vectors to form a plane ...
0
votes
1answer
763 views

is it possible to hash a range?

OK. I am not a math guy. I'm a programmer, so forgive me for the non-math lingo. let's say I have 3 ranges ...
0
votes
1answer
63 views

Why do we pick ax + b when doing universal hashing?

Why can't we pick just $x + b$ for example? I know that for universal hashing the Pr[$h(x) == h(y)$] $\leq 1/|n|$ But with the same hash function, just without the $a$ we can get $h(k) = (($k$ + b$ ...
0
votes
1answer
62 views

Generating hash function from given hash table?

I need help with understanding the following problem: In a factory, machines are making cars (1-n) along the production line. One machine is making one part on the existing construction (part 1 is ...
2
votes
1answer
403 views

Mathematical notation for Hash Tables

A matrix is nice for modelling arrays, eg const A = [1, 2, 3, 4] const a1 = A[0] const a2 = A[1] const a3 = A[2] const a4 = A[3] can be modelled with $$ A = \...