Stack Exchange Network

Stack Exchange network consists of 174 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.

0
votes
0answers
33 views

probability of collision in a hash function

I have asked a question here: https://cs.stackexchange.com/questions/102385/probability-of-collision but anybody could help me to solve this problem mathematically. If you have an idea please give ...
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
27 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
122 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
40 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
45 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
38 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
68 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
34 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
44 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
51 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
40 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
65 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
76 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 ...
0
votes
0answers
47 views

Bloom Filter: The probability of false positive in a certain situation.

My question is about Bool Filter's false positive probability in a certain condition. Background: In general, Bool Filter (BF) is a bit string that allows us to insert a set of elements in it. Then, ...
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
83 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 ...
0
votes
0answers
37 views

Hash on 128 bit string

Due to wanting to limit processing time required to run I have a bit string function that blindly generates 128 bit strings and I need a way to know when I have the 128-bit string I wanted, generated. ...
1
vote
1answer
113 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
57 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
214 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 ...
2
votes
1answer
737 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
51 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
50 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
30 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
411 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
48 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
68 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
71 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
128 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
44 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
341 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
42 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
987 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
153 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
41 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
102 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
146 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
101 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
74 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
105 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
628 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
59 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
61 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
376 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 = \...
0
votes
1answer
92 views

Hash function that can determine set similarity

I'm trying to come up with an effective way of handling slight variations in sets of numbers when hashing in an Information Retrieval system. I have a simple solution that is reasonably effective and ...