Questions tagged [hashing]
The hashing tag has no summary.
162 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
0
answers
23
views
Why is the universal hash function defined as Hp,m={ha,b(k)∣a,b∈{0,...,p−1},a=0}?
I understand the basic division hash function h(k)=k mod m, and the use of this function
but I don’t understand why the universal hash function introduces the parameters a and b and uses a prime ...
0
votes
0
answers
48
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 ...
3
votes
1
answer
75
views
Does having fixed "partitions" make Consistent Hashing impossible?
Some tools such as Riak claim to use consistent hashing. They have a fixed number of partitions/vnodes, each "physical" node controlling a portion of them. "Specifically, the vnodes in ...
1
vote
1
answer
447
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:
...
3
votes
3
answers
288
views
How to select hash functions for cuckoo hashing?
In cuckoo hashing, an insertion failure occurs when there is an infinite loop of displacements. This is detected by a "max iterations" count on the insert function.
When the insert fails, the table is ...
2
votes
1
answer
70
views
What type of clustering would occur if one of the functions in double hashing is constant?
If the hash is calculated as h(k, i) = (h1(k) + i*h2(k)) mod |T|
What would happen if h1(k) or h2(k) is constant? Would that produce primary or secondary clustering? I think both would produce ...
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(...
2
votes
1
answer
76
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 ...
0
votes
1
answer
59
views
Cormen chapter 11 probability of two keys being assigned the same slot simple uniform hashing
I have been reading Cormen's chapter 11 and I stumbled upon the following statement on page 260 (3rd Edition):
Let xi denote the ith element inserted into the table, for i = 1, 2 ... n, and let ki = ...
14
votes
9
answers
8k
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 ...
1
vote
1
answer
96
views
Does there exist some ``partial" universal hashing?
Suppose we have sets $X$ and $Y,ドル $|X|=m,ドル $|Y|=n$. $H$ is a universal family of hash functions from $X$ to $Y$. Let $S\subsetneq X$ be a proper subset of $X$. Does there exist some "partial"...
0
votes
2
answers
216
views
How might we hash two trees?
Suppose that you had two trees.
Our goal is to convert the two trees into two integers such that two trees are the same if and only if the two integers are the same.
Suppose that we have a function ...
1
vote
0
answers
138
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. ...
1
vote
1
answer
143
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$ ...
0
votes
1
answer
261
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{...