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.

0
votes
1answer
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 ...
0
votes
0answers
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 ...
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
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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$ ...
0
votes
1answer
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 ...
2
votes
1answer
433 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
98 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 ...
-3
votes
1answer
170 views

Voting scheme based on a hash function $H$

A hash is a one-way (hard to invert) function $H$ which can take an input of any size and produce a fixed-size output. Typical requirements for good hash functions are: • Pre-image resistance: given $...
1
vote
0answers
117 views

How to randomly hash a 64-bit int

I am trying to write a hash function to map a 64-bit integer to another "random-looking" 64 bit integer. Here are my requirements: I can only use /, ...
0
votes
0answers
65 views

Calculating 2 unknowns in mod 2^32 addition?

My question is fairly simple. Given equation: r = ( a + b + c ) mod m Where m = 2^32, and values r and a are known values. Assuming: Edit: b + c < m Is it possible to calculate a specific ...
1
vote
2answers
88 views

Constructing hash table to elect the representative

I'm having difficulty with the following question: There are 338 seats in the house of common. We are trying to elect speaker for the house of common. Suppose that m politicians are candidates and ...
0
votes
1answer
95 views

How to associate a unique integer to a matrix with integer elements in $[-1 , 100]$ [closed]

I have a $n \times m$ matrix $A$ with entries $A_{i,j} \in [0 , 100] \cap \mathbb{Z}$. with a great likelihood of 0 I would like to represent this matrix by the smallest integer value possible. What ...
0
votes
0answers
81 views

Hash table are collision events independent

Say I have some universal hash table of size $m$ and random input data set of size $n$. Let's define $I_{i}$ indicator RV as probability that while inserting ith key to the table collision happened. ...
0
votes
1answer
147 views

Probability of collision in linear hashing?

Take an $u × m$ matrix $A$ filled with random bits(0,1). Given a non-zero vector $x$ in $\{0,1\}^u$, what is the probability that $x$ is in null space of $A$. All calculations are done modulo 2. ...
1
vote
1answer
127 views

A question about r-universal hash family definition

Here is the one possible definition of the universal hash family (from my professor's book): A family $\{h_a | a \in A\}$ of functions $X \to Y$ is an r-universal hash family if, and only if, for ...
0
votes
0answers
56 views

minimum number of bits required to perfectly hash/map ChessBoard pawns occupancy

What is the minimum (and how to calculate it?) number of bits required to perfectly hash/map pawn occupancy with black and white pawns treated differently (meaning a position with black pawns and ...
0
votes
1answer
217 views

Monotone one-way hash function

I am sitting on a contradictory requirement in which I would need a function that is a one-way hash, but that is also monotone. One-way: if $y=h(x)$, then computing $x=h^{-1}(y)$ is intractable, or ...
1
vote
0answers
58 views

Probability that an arbitrary element of a field has a specific structure.

This question is related to : https://crypto.stackexchange.com/questions/37351/encoding-an-element-in-r-rhr-way that I asked couple of weeks ago. The difference is that I did not take the collision ...
1
vote
1answer
464 views

How to prove pairwise independence of a family of hash functions?

I want to prove pairwise independence of a family of hash functions, but I don't know where to start. Given the family of hash functions: H with h(x) = a * x + b (mod M). ( Say h: U -> V, then: M ...
1
vote
1answer
71 views

Bijective function from $\Bbb N ^{n \times m}$ to $\Bbb N$?

I'm working on a hash function and I was wondering if there is a function which can tansform a matrix into a natural being bijective. For example: $A=\begin{bmatrix} 0&0&1\\ 2&0&1\\ 0&...
1
vote
0answers
55 views

An m-dimensional space with each 'point' in the space having an n-dimensional value

Say I have an $m$-dimensional space (continuous or discrete) such that every point in that space has a value, and that value is an $n$-dimensional vector (continuous or discrete). My question is how ...
2
votes
1answer
158 views

Why the upper bound on parameters of a Linear Congruential Generator?

The Linear Congruential Generator used as a basis for Universal Hashing is defined by the equation using parameters $a$, $c$ and $m$: $$X_{n+1} = (a\cdot X_{n} + c) \mod m$$ with the following ...
2
votes
1answer
487 views

What math do I need to know for MD5?

This could fit into a lot of areas of SO but I feel like mathematics will know best. What area of math is used for something like an MD5 or SHA algorithm? Is there a mathematical equation/skeleton ...
0
votes
1answer
456 views

Girth of directed graphs

The definition of girth of an undirected graph is defined as the length of the smallest cycle in the graph. Some directed graphs have no cycle (a directed path that stars and ends at the same vertex) ...
0
votes
0answers
105 views

Calculation of the avalanche effect coefficient.

Given a strict avalanche criterion matrix/dependence matrix for a hash function,how do I calculate the avalanche coefficient for it. I want to calculate a single parameter(value) which represents the ...
0
votes
1answer
48 views

does calculating the arithmetic mean of a serie of standar deviation measures make sense?

I'm trying to test if a hash function mantains a even distribution of values. My plan is to generate a set X of hashes and a integer Y symbolizing "slots" to see how many of the hashes maps to the ...
0
votes
0answers
37 views

Does this function satisfy the Uniform Difference Property?

Does $h_{a,b}(x) = ((ax + b) \bmod 2^w)/2^{w-M}$ satisfy the Uniform Difference Property: given constant integers $w, M: w >= M$, and for any choice of distinct $x$ and $y$ in $[0, 2^w]$, $h(x) - h(...
1
vote
2answers
546 views

permutation symmetric hash function

I'm searching for good hash-function for N-dimensional vector of M-bit integer numbers with a property that any permutation of the coordinates gives the same result. e.g. $ h(x,y,z) = h(x,z,y) = h(y,...
5
votes
2answers
11k views

How can I convert this unique string of characters into a unique number?

I have an unusual programming problem and the math side of it has me stumped. It's probably a simple answer but math isn't my strongest area. I've generated a unique string of 7 characters which are ...
2
votes
1answer
589 views

probability of collision from hashing

So i have a hash table that can hold 100 elements. It currently stores 30 elements. What is the probability that the next 2 inserts will result in at least one collision? What i did was figure out ...
0
votes
1answer
39 views

Special-purpose hash functions

I am trying to create a special purpose hash function that will have as few collisions as possible. $99\%$ of the input will be sequential numbers, from $1$ to $N$. The size of the hash table will be ...
0
votes
2answers
82 views

equation to create unique value

I have a list of n objects say [ apple, orange, carrot, cherry, banana ] Now I am trying to come up with an equation which will generate an unique number for ...
0
votes
1answer
182 views

What does “4-universal hash function” mean?

I encountered the notion of 4-universal hash function and I cannot understand what exactly it means. This article https://en.wikipedia.org/wiki/Universal_hashing did not really help to clarify it. ...
4
votes
2answers
485 views

Where do hash functions come from?

I have some basic understanding of how hash functions work, however, I have no idea of how mathematicians created them. Were them a byproduct of a non cryptografics related research or were them a ...
3
votes
0answers
528 views

Finding a minimal perfect hash function for small sets quickly

I'm trying to solve the computer science problem "Minimal perfect hash function" (MPHF). I have an algorithm that can generate a MPHF for very large sets in $O(n)$ that only needs 1.54 bits/key, very ...
1
vote
0answers
45 views

How to calculate the expectation $E[\sigma(1)\sigma(2)\sigma(3)]$, given a 2-wise hash function $\sigma: [d] \rightarrow \{-1,+1\}$

Given a 2-wise hash function $\sigma: [d] \rightarrow \{-1,+1\}$, i.e., $\sigma(a)$ will map any positive integer $a\leq d$ into real number $-1$ or $+1$ with equal probability. Then how to calculate ...
2
votes
0answers
167 views

The hash collision probability approximation

I am comparing the actual probability of no collisions to the probability approximation formula of no collisions from the Understanding Cryptography text. The approximation is as follows: $$P(\...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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$...
0
votes
0answers
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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?
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
105 views

the meaning of 4-wise hash function

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....
0
votes
0answers
31 views

Type(s) of Hashing function that keeps the ordering information

I am asking this question from a perspective that we need to store a set of hashed data that can be queried later for in an ordered fashion. My situation is that some data has to be encrypted, I am ...