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

176 questions
Filter by
Sorted by
Tagged with
67 views

27 views

### Universal hashing family

I'm not really sure this question is proper for MathExchange but I have found it more suitable than StackOverFlow. So, I'm taking the course of Data Structures and Algorithms and we got some example ...
72 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 ...
40 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 ...
55 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: ...
169 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 ...
124 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 ...
97 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 ...
68 views

### Distinguishing between hash function digest and message corruption

As an initial disclaimer, I know virtually nothing about coding theory. I apologize in advice for incorrect or inappropriate terminology. The problem space I'm exploring is ensuring the integrity of ...
1k views

### Chance that first 6 characters of a SHA-1 hash matching another SHA-1 hash?

Just what the question says -- what is the chance that the first six characters of a SHA-1 hash will match the first six characters of any given SHA-1 hash?
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: ...
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 ...
12 views

### Equivalance of statement

I was studying this paper Similarity Estimation Techniques from Rounding Algorithms by MS Charika Inside specifically had this ...
932 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 ...
68 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 ...
149 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. ...
465 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) ...
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 ...
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 ...
157 views

### “Unique” number from several values

I'm trying to create a unique unsigned "long" number (64 bits) from a list of 4 other numerical values. Some function f(n1, n2, n3, n4) = x. The order of the values ...
117 views

15 views

### Probability of Hashing function to be perfect

Suppose we have a table of size M and we want to map N elements using a hashing function. This question had a lot of sub parts - The first one was that find the expected number of collisions which I ...
31 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 ...
219 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 ...
20 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 ...
31 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)$. ...