# 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.

175 questions
168 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 ...
120 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 ...
12 views

### Equivalance of statement

I was studying this paper Similarity Estimation Techniques from Rounding Algorithms by MS Charika Inside specifically had this ...
85 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 ...
122 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 ...
889 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 ...
72 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$ ...
66 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 ...
433 views

172 views

### Likelihood for a random hash function not to be surjective

Let us define a hash function \begin{align*} H \colon A &\to B\\ a &\mapsto b \end{align*} $$|A| \geq |B|$$ Assuming it is perfectly random (Hyp 1), we estimate the probability that ...
41 views

### Probability of x modulus a prime = a

I am working on a project that involves analyzing the distribution of simple hash functions. One such construction relies on the fact that given a primes $p,q$, the unit group for $p$ $U_p$, a random ...
425 views

### Balls and Bins- Hash Table: a Concrete Example

My question is related to this: https://cs.stackexchange.com/questions/49027/balanced-allocation-hash-table-overflow-probability/49030#49030 In [1,2], it is said that if we throw $n$ balls into $k$...
87 views

### How do I design a hash function for this given case?

My professor gave me the following problem. You are to store objects identified by integers from the interval $[0..10^9 − 1]$. You expect never to have to store more than 1400 objects. Design ...
108 views

### Solve for n: 1 - e^((-k (k - 1))/(2 n)) - z = 0?

With the knowledge that the probability of a hash collision is (see: Hash Collision Probabilities): 1 - e^((-k * (k - 1)) / (2 * n)) Where k is the number of input values and n is the number of ...
74 views

### How to prove the probability of 2 times expectation is less than 1/2? [closed]

Suppose X is a non-negative random variable and E(X) = m. Then how to prove the probability P[X ≥ 2m] ≤ 1/2, more generally P[X ≥ cm] ≤ 1/c, where c > 1?
66 views

### A Hashing Problem

Hashing: You are to store objects identified by integers from [0..N − 1]. You expect never to have to store more than K objects. How would you design the hash function? Describe a general approach to ...
89 views

### How to create the smallest possible unique number from one or many unordered numbers?

What I am looking for is very similiar to this question and that one, too. I need to connect two SQL tables by a many-to-many relationship (artists and song names). To achieve what I'm trying to do I ...
If someone says: 4-wise independent sign (hash) functions $s_1,s_2, s_3 : [d] → \{+1, −1\}$, then what does it means? I cannot use k-wise Independence variables (the definition 1 http://www.math....