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
342
questions
3
votes
1
answer
49
views
Where was DJBX33A first published?
Daniel J Bernstein's "Multiply 33 and add" simple hash is surprisingly hard to find the original reference to. Googling provides descriptions in language implementations such as PHP ...
- 723
1
vote
0
answers
15
views
Effect of using signed vectors for LSH Random Projection (Simhash)
Simhash is an text similarity algorithm proposed by Moses Charikar in his paper "Similarity Estimation Techniques from Rounding Algorithms". However, in his original paper, he proposed to ...
- 111
1
vote
2
answers
76
views
Transform any string into the shortest coherent/unique numeric identifiant
Is there some algorithm that can transform any string input (of any length) into a shortest possible coherent/unique numeric identifiant.
By "coherent", I mean that the same input will ...
- 111
1
vote
1
answer
90
views
Understanding Polynomial Rolling Hash Function by Modular Arithmetic
I was learning the Polynomial Hash function in python, the one used in Rabin Karp Algorithm
This is the implementation I was taught:
...
1
vote
1
answer
66
views
How bad re-hashing can cost?
Lets assume that the load factor of a hash table of size $n$ became inappropriate.
The process of re-hashing involves choosing a new hash function.
A good choice of a new function will make the cost ...
- 185
1
vote
1
answer
122
views
Using XOR operation, a MOD operation compute a function f(n)
I had a difficult assignment in my Data Structures and Algorithms class.
We need to implement a program that computes a function f(n) based on the following known values of n and f(n):
n : 9689 ...
- 11
0
votes
1
answer
14
views
Hash function for use with hash table, given power distributed integers
Suppose I have integers that follows a power distribution:
$P(n) \propto 1/(n + 1)^\alpha, n \geq 0$
What hash function is a good choice to avoid collisions. The usecase is keys in an ...
- 149
0
votes
1
answer
52
views
Can you unwind a cryptographic hash function's last round?
Given a cryptographic hash, $ \text{hash}(A || B || C) $, and the last block added to the hash, $ C $, can you determine $ \text{hash}(A || B) $?
In other words, can you roll back the last round of a ...
- 145
0
votes
2
answers
72
views
A good way to hash two numbers with known properties together
I have two 64-bit numbers a and b which have a few properties: only 49 out of the 64 bits are used (15 bits are always 0), and ...
1
vote
1
answer
41
views
Find a pair $a,b$ with a range condition in Hash table
Given an array with the size of $n$ of integer numbers. Our goal will be to analyze the expected running time of an algorithm that uses a hash table to find (if exists) a pair $(a,b)$ subject to $2<...
- 1,962
1
vote
2
answers
189
views
Reversible streaming hash function
Do any streaming hash functions exist that provide the same result if the input is reversed?
That is to say, is there some hash function, $h$, such that:
$$ h(h(h(h(0, x_1), x_2), ...), x_n) = h(h(h(h(...
- 145
2
votes
1
answer
35
views
Hash function that returns the same result when the input is reversed
Do any hash functions exist that provide the same result if the input is reversed?
If this is impossible, why is it impossible?
I am interested in sending packets of constant size around a circuit in ...
- 145
10
votes
1
answer
665
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 ...
- 263
1
vote
1
answer
135
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] ...
- 11
1
vote
1
answer
80
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 ...
- 11
0
votes
1
answer
387
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 ...
- 23
0
votes
0
answers
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.
- 1
3
votes
1
answer
54
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 ...
14
votes
9
answers
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 ...
- 241
1
vote
1
answer
57
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 ...
0
votes
0
answers
30
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 ...
- 121
0
votes
1
answer
28
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 ...
- 306
5
votes
1
answer
163
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, ...
- 105
1
vote
2
answers
208
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), ...$
...
- 297
1
vote
0
answers
98
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. ...
- 111
1
vote
1
answer
77
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$ ...
- 297
0
votes
1
answer
191
views
Simple Uniform hashing with chances of no collision
I know that if I have $n$ different values in an array of size $m$ (where $m>n$) under simple uniform hashing, the average probability of the total number of collisions is:
$$\sum_{i=1}^{n-1}\frac{...
- 33
1
vote
2
answers
125
views
Order-preserving hashtable for integer tuples
There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) ...
- 297
1
vote
2
answers
205
views
How to use a worst case scenario in Rolling Hash: Rabin Karp Algorithm when the given string only contains the occurrences of "a and b?"
Issue: I am having a hard time figuring out how to use the worst case for Rolling Hash, especially if the occurrences are only "a and b" for the string. Not only that but it is a bit of a ...
- 13
0
votes
0
answers
66
views
Why using nC2*1/365 to calculate the birthday paradox is incorrect
The birthday paradox is basically that assume there are 365 days in a year(ignore the effect of Febuary 29th), each person's birthday is uniformly random in these 365 days and independent with others. ...
0
votes
2
answers
62
views
Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)
I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than
O(N²)
...
1
vote
1
answer
30
views
Sampling unique records from a large dataframe
Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe?
Some sort of sampling algorithm?
- 11
1
vote
1
answer
64
views
Universal family of hash functions — dependent on table size?
Given the following family of hash functions:
$$
\mathbb{H} = \{h_c(x) = (12x + c) \bmod
m \mid c \in \mathbb{N} \},
$$
where $m$ is the key size.
Prove that $\mathbb{H}$ is not a universal ...
- 11
-5
votes
1
answer
594
views
Implementing Flajolet–Martin algorithm in Python
I am stuck on what to do.
I am trying to create a simple implementation of the Flajolet–Martin algorithm using Python. The stream will be the contents of a text file and you will produce an ...
0
votes
2
answers
237
views
the load factor in hash table
What is numerically the best value or range of values used as a reference for the load factor used in the hash table?
What is the pseudo-code of the “rehashing” method, which is applied when many ...
- 9
1
vote
1
answer
567
views
Hash / Compression algorithm to shorten text?
I desperately need a hash / compression function that is suited to shorten text.
The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ...
- 131
0
votes
1
answer
268
views
Consistent Hashing Algorithm Without Distribution / Load Balancing
I need some help finding or creating a consistent hashing algorithm with the following properties:
Given N buckets, only distributes keys to bucket N.
When number of buckets are increased from N to N+...
- 61
1
vote
2
answers
2k
views
Averege time complexity of open addressing
I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
- 115
1
vote
0
answers
49
views
Where does 2^32 come from with bitcoin?
Several months ago I was doing research into calculating mining revenue for several crypto currencies. When trying to calculate BTC revenue I found this value 1/2^32 which was described somewhere ...
- 51
2
votes
1
answer
59
views
How do these Crypto terms relate to each other and what do they all mean?
Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and ...
- 51
0
votes
2
answers
70
views
What happens in the event of a collision in a crypto hash function?
I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of ...
- 51
1
vote
0
answers
23
views
Algorithm Complexity Question
this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can.
I was doing some ...
- 51
1
vote
1
answer
57
views
Locality Sensitive Hashing for Sets
Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer ...
2
votes
1
answer
102
views
Splitting the output of a wide hash in lieu of multiple independent hashes
Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of ...
- 21
1
vote
1
answer
625
views
Optimal parameters for a Bloom filter
My first question here. Please do not judge me much if this is a too simple.
Some text consists of $n=12\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ ...
- 125
0
votes
1
answer
45
views
Confused about the appropriate slot in linear probing
The following paragraph is from the book CLRS:
Given an ordinary hash function $h' : U \rightarrow \{0, 1, ..., m - 1\}$, which we refer to as an auxiliary hash function, the method of linear probing ...
- 411
1
vote
1
answer
45
views
Fingerprint functions for set equality checks?
Given I have two sets of objects $A =\{a, b, c\}$ and $B = \{a, b, c, a\}$
Based on the set equality, I want the fingerprint of these sets to be the same $F(A) = F(B)$.
Additionally I want to be able ...
- 123
2
votes
1
answer
180
views
Analysis of a calculation of expected number of collisions in hashing
For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al
Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
- 1,152
0
votes
1
answer
79
views
Finding a hash function, so that the set of hash functions is universal
Problem:
Let $U = \{0,1,2,3,4,5\}$ be a universe of keys and $T = \{0,1,2\}$ we observe follwing 5 hash functions which map from $U$ to $T$ :
$$h_1(x) = (x+1) \mod{3} \hspace{5mm} h_2(x) = (x+2) \mod{...
- 25
0
votes
3
answers
184
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 ...