# Questions tagged [hash]

Mathematical function that maps arbitrarily-sized data to fixed-size integers, often used as keys in hash tables or to help ensure data integrity

332 questions
Filter by
Sorted by
Tagged with
605 views

### Are there associative cryptographic / collision resistant hashes?

Git uses SHA hashing as a content address key. This relies on their being a vanishingly small probability that two different pieces of content will ever hash to the same key. For content ...
25 views

### Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)

Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element. Any subarray array[start, end] ...
40 views

### How to create a 'hashing' function that maps up to 1 to N numbers uniquely to numbers 1 to N

I would like to use or create a hashing algorithm that takes K inputs from 1 to N and maps them uniquely to different numbers on 1 to N. K can be 1 to N. Ideally I would like the hashing alg to be ...
57 views

### What would happen SHA-256 collision were to be found?

As far as I and this wikipedia page know, there are no collisions (2 inputs with the same output) found in SHA-256 (yet). what would happen if a collision were to be found, 1. would it be easier to ...
16 views

### Suppose some hash family H satisfies $$Pr_{h_{\in_{R}} H}[h(x_1) = h(x_2)] = \frac{1}{|Y|}$$ Does it mean H is 2 universal?

Suppose some hash family H satisfies $$Pr_{h_{\in_{R}} H}[h(x_1) = h(x_2)] = \frac{1}{|Y|}$$ Does it mean H is 2 universal? The converse is true, but I'm not sure about this.
39 views

### What is the definition of security of universal hashing

As a cryptographic primitive, universal hashing should have somewhat a criterion on its security. How is its (computational) security defined? Or, in other words, what "breaks" a universal ...
7k views

### Do passwords need a max length?

I understand that password storage generally uses hashing for security due to it being irreversible and that the stored hash is just compared to the hash of the password inputed by a user attempting ...
39 views

### On the equivalence between two definitions of universal hashing

Let $H=\{h|h:X\to Y\}$, $|X|=n$, $|Y|=m$. $H$ is a universal hash family if Def 1. For any $x_1,\ x_2\in X$, $x_1\neq x_2$, $\left|\left\{h\in H\middle| h(x_1)=h(x_2)\right\}\right|\leq |H|/m$. (or ...
25 views

### If the data that I input for locality sensitive hashing is sensitive, should its resulting hash also be considered sensitive?

Is it correct to assume that if the input that I hash is sensitive, that I should also consider the locality-sensitive hash generated for that input to be sensitive? I presume that, if an attacker has ...
60 views

### Universal hash functions and prime number modulus scheme

Definition of a universal hashing function $h: U \rightarrow[m]$ (where $[m]=\{0, \ldots, m-1\}$) is that for any given distinct keys $x,y \in U$, when $h$ is picked at random (independently of $x$ ...
16 views

### Reversible computing as a path to a useful PRNG or hash function?

There's a question I've long had about reversible computing: do non-trivial algorithms usually end up generating strongly pseudorandom data as an artifact of the computation? The most straightforward ...
94 views

### Self referential hash function possible?

Is there a hashing function $f$ that for each input $x$ if $f(x) = y$, then $f(x \, || \, y) = y$? In other words, if we concatenate its output with the input, the result will not change. Furthermore, ...
1 vote
123 views

### Perfect ordered hash function on ordered sequence

I have a sequence of integer tuples $t_1, t_2,..., t_N$ of different sizes in lexicographic order, e.g.: $(1, 1), (1, 2), (1, 3, 5), (1, 3, 6), (1, 5), (3), (3, 2, 3), (3, 7), (3, 8, 1), ...$ ...
1 vote
66 views

### How to properly save Zobrist Keys?

In a project of mine, I want to represent states as efficiently as possible. Initially, I went ahead with a BitBoard representation and some clever tricks to speed up the evaluation of the game tree. ...
54 views

### In the complexity of open addressing, why it is necessary take the sum to $\infty$?

When estimating the average calculation complexity of open addressing, I found following explanation: Let $B$ be the number of backets and $N$ be the number of elements already in the hash table. The ...
1 vote
75 views

### Perfect hash function that weakly preserves leading zeros

I need a perfect hash function that maps 2 integers into one integer twice the size (i.e. $(Int64, Int64) \rightarrow Int128$). The function preserves sum of leading zero bits: $(0, 0) \rightarrow 0$ ...
124 views

150 views

### How do i delete one single unequal element from an array of equal elements without using hashing?

The rules of the question state that: Only one element is different. Rest are all same. Array A size is 8. I need to find the different element and remove it (Hashing cannot be used). I have not ...
1 vote
57 views

### How to efficiently see if a value is in a set

I was curious is there a really efficient way to see if a value is in a set? This question comes from me thinking about youtube views. As far as I understand youtube view count goes up for every ...
320 views

### A question about hash problems in CLRS book

Consider the following problem 11.2-6 from CLRS book: Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, ...
1 vote
178 views

### A hash function for a 2D hash table with a scattering property?

I have an $n\times n$ matrix, and want to find a bijective function $h:[n^2] \to [n]\times [n]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. ...
1 vote
48 views

### Check if string contains pattern (with respect to one-to-one symbols mapping) [closed]

I'm trying to solve following problem: Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original ...
1 vote
110 views

### Expected Lookup Length in Open Addressing Hash Table with Simple Uniform Hashing

In several proofs of the expected lookup length in an open addressing hash table, an assumption is made (which is said to follow from the "simple uniform hashing assumption": Given a hash ...
66 views

### What are the chances of hash collision given large input and small hash?

I have an input of 128 bits (binary, 0s and 1s) and want to hash this input with 32 bit CRC. But I am not sure if collision rate is moderate or too high ? Is it 2^128/2^32 = 2^98. And does that ...
1 vote
48 views

### Finding a full collision within a large array

I apologize for the vagueness of the title, but this question is quite difficult for me to describe. For that reason, I'm unable to directly convey my problem. In an effort to circumvent this, I've ...
463 views

### hash-tables - Expected-time for an unsuccessful search

The following question is from MIT-OCW 6.006, Spring-2008, Problem-Set 2, Q-3.c. Suppose you have a hash table where the load-factor $\alpha$ is related to the number $n$ of elements in the table by ...
1 vote
Suppose that we are given a key $k$ to search for in a hash table with positions $0, 1, \dots , m-1$, and suppose that we have a hash function $h$ mapping the key space into the set \$\{0, 1, \dots , m-...