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
345 questions
0
votes
0
answers
47
views
Can the constants of FNV1A be computed for a specific set of strings to make it a perfect hash function?
I am hashing a bunch of strings made up of a finite number of known keyword strings (n many keyword strings). Here I want to generate a perfect hash s.t. each ...
- 187
0
votes
0
answers
33
views
Identifying the DMAC Literals Representing Internal Processes (Message Schedule, T1, T2, etc.) in SHA-256 CNF Conversion Using CGen Tool
When using the CGen tool to convert the SHA-256 algorithm into Conjunctive Normal Form (CNF), the input and output bits are represented by DMAC literals. However, I am specifically interested in ...
0
votes
0
answers
55
views
How virtual nodes affects consistent hashing ring?
Given the consistent hashing ring system, i.e., with $S$ serves, $C$ clients and a random hash function $h$, how can we choose the number of virtual nodes per server $V$, so that the probability that ...
- 377
3
votes
1
answer
130
views
Two-Level (Perfect) Hash Tables in Practice
For $n$ elements, a two-level hash table contains an $O(n)$ top-level hash table whose entries are hash tables also. Each table samples from a 2-universal family. To hash an element $x$, we first hash ...
- 31
1
vote
1
answer
67
views
How to make a pseudorandom generator that has the longest possible period in a range?
I want to generate numbers in the range $0 \leq n < 2000$ in a random order. The risk of using "generic random number generator" $\mod 2000$ is that it will cycle sooner in that range, or ...
user64055
3
votes
1
answer
178
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 ...
- 630
1
vote
2
answers
146
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
444
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
108
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 ...
- 341
1
vote
1
answer
168
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
53
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
1
vote
1
answer
102
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 ...
- 155
0
votes
2
answers
251
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
78
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,954
1
vote
2
answers
265
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(...
- 155