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
268
questions
0
votes
0answers
15 views
Propose a family of hash functions with $mod p^2$ for some prime number $p$
I need to define a family H of universal functions $\{0,1, ..., p^k−1\} →\{0,1, ..., p^2−1\}$.
Now based on a similar example I was thinking of something like:
Given some $a= (a1, a2, ..., ak)∈\{0, ......
0
votes
1answer
40 views
Shuffling Bits For Uniform Distribution
I am writing an hashing algorithm to be used in key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to be ...
0
votes
0answers
15 views
Hash tables for storing data in an application that supports partial search
Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is?
I would have thought ...
0
votes
0answers
17 views
What is the order of magnitude of bitwise operations involved in a SHA-256 hash?
Specifically, how many bitwise operations (approximately, could be just order of magnitude) occur each time a Bitcoin ASIC miner performs a SHA-256 hash in typical mining computation, i.e. as it ...
0
votes
0answers
15 views
If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?
I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?
1
vote
1answer
103 views
Constructing 2-Universal Families
Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications?
I don't even know where and how to ...
1
vote
1answer
45 views
How 'Avalanche Effect' got its name?
I wonder how or why Avalanche Effect got its name.
Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (...
1
vote
1answer
42 views
Why mod operation can be used as hash function
I'm new here, and I'm currently trying to understand why mod operation can be used as a hash function.
For example, consider the function $h(x)=x\mod 2^{256}$, where $x$ can be a string of any length. ...
1
vote
1answer
26 views
How to show independence and uniform distribution of hash codes from k-wise independent hash functions?
Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\...
1
vote
1answer
55 views
How can I prove or disprove that the following function is bijection?
For a research project, I tried to prove or disprove that a function called xxhash128_low is a bijection from 64 bit unsigned integer to 64 bit unsigned integer. I have shown that it is sufficient to ...
4
votes
3answers
87 views
Integer set disjointness query on sketches with something like homomorphic hashing
Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. ...
1
vote
2answers
42 views
Question regarding the proof that quadratic probing always finds an empty slot if the table is less than half full
to prove this statement I assume the probing function as: $$h(i,x)=h'(x)+i^2 \text{ mod t} $$
And for $0\leq i,j < \frac{t}{2}$; $i\neq j; t \text{ prime}$: $$h(i,x) = h(j,x)$$
This results into $$(...
1
vote
1answer
91 views
Universal hash functions - Proof
Problem statement
Let $K$ be a set of keys with $|K| = n$ and define the index set $I = \{0, \ldots, m-1\}$. Now let $H = \{h \mid h : K \to I\}$, i.e. $H$ contains all hash functions which map the ...
0
votes
0answers
19 views
Bad data for hash function
Is it possible to choose such a nontrivial set of queries so that the amortized running time for a hash table with a public key and a function like $(a_{N − 1}k^{N − 1} +... + A_{1}k + a_0) (mod \: p)$...
0
votes
1answer
29 views
Why is this implementation of the hash function bad?
I have a task of hashing DNA sequences. Let the DNA be long sequences of four amino acids, which we will denote by the letters $A, T, G$ and $C$.
My hash function $h$ take DNA as an input and return ...
1
vote
2answers
130 views
Store a n-bit string using only O(log n) space
Is it possible to somehow store a $n$ bit string using only $\mathcal{O}(\log{n})$ space? I am thinking if the string could be stored using a hash function, but I am not sure if it is even possible.
1
vote
0answers
30 views
Is there a standard name for this property of hash functions?
A hash function $H$ operating on strings can have the following property:
Let $x$ be a string and $c$ a character. Given $H(x \cdot c)$ and $c$,
$H(x)$ can be determined uniquely (where $\cdot$ stands ...
0
votes
1answer
19 views
Choosing the right function
I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining).
What is a good hasing function that guarantees a good ...
0
votes
1answer
45 views
oone exmple in hash topics?
Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is ...
0
votes
0answers
33 views
Minimal perfect hash function for set of integers
This might be a trivial question, but I have the following problem: I want to (perfectly) hash a number of lists of integers of length $n$, with all entries between $k_{min}$ and $k_{max}$. How can I ...
0
votes
0answers
61 views
Pairwise independent hash function family?
I am looking for a family of pairwise independent hash functions $\mathcal{H} = \{h \mid h:[n]\rightarrow [m]\}$ that is easily computable.
As an example that doesn't seem to work, choose a prime $p &...
1
vote
1answer
16 views
Clarification on evenly dispersing modular hashing [duplicate]
I'm going over "Algorithms fourth edition" by Robert Sedgewick and Kevin Wayne.
In the chapter on hash tables I have encountered an easy hashing method called "modular hashing"
<...
0
votes
0answers
23 views
Expected runtime for hashing with a binary search tree as collision handling
I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
0
votes
0answers
38 views
Simple incremental hash funcion
I have permutations:
4 1 2 5 3
4 3 2 5 1
numbers can be order magnitude of 1000 (fits in two bytes)
I want compute 32 bit (or better 64 bit) hashes, it should be ...
-1
votes
1answer
77 views
What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case
Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
0
votes
0answers
25 views
Double Hash Family Universality
Here I am given 2 hash families and I need to prove the universality of the double hash, but I am stuck as to how to prove this. I know the properties of an epsilon-universal family is that the ...
1
vote
1answer
94 views
When and Why do I Rehash?
I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash?
One reason to ...
3
votes
2answers
73 views
Merkle tree sorting leaves and pairs
I am implementing a Merkle tree and am considering using either of the two options.
The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input ...
2
votes
0answers
35 views
In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim:
Universal Hashing uses randomization.For the example of a compiler's symbol table, ...
0
votes
1answer
61 views
Difficulty in understanding few steps in the proof: “The class $\mathscr{H}_{p,m}$ of hash functions is universal”
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\...
0
votes
1answer
58 views
Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)
I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function.
The versions are as follows:
...
0
votes
0answers
24 views
In Hashing-collison resolved by chaining: Intuition behind $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$
Hashing-collison resolved by chaining: $O(1) + \alpha= \Theta(1+\alpha)=O(1)+1+\frac{\alpha}{2}-\frac{\alpha}{2n}$
I was going through the text Introduction to Algorithms by Cormen et. al. and in the ...
1
vote
2answers
253 views
Double Hashing with Strings as key
How would you choose the second hash function with for double hashing with string as key?
My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is ...
1
vote
0answers
64 views
Variance of chain length in hashtable
I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it.
What would be variance of chain length when such $n/2$ numbers are being added ...
0
votes
0answers
28 views
Is this example in Skiena's Algorithm Design Manual correct?
i think the above is incorrect; specifically, i think H isn't bijective. say our alphabet is the lowercase letters [a-z] and ...
-2
votes
2answers
37 views
1
vote
1answer
33 views
Size of order-preserving minimal perfect hash family
Suppose we have a universe of $u=|U|$ elements. We called a set of $H$ function $(U,m)$ order-preserving minimal perfect hash family (OPMPHF) if for every subset $M\subset U$ of size $m$ has at ...
0
votes
3answers
131 views
What is the best hash functions for millions of String keys?
I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value.
The problem that the retrieval process is too slow and I want to ...
1
vote
2answers
45 views
Theoretical question about Zobrist hashing and chances of collision with slight modification
I have a hash table that uses zobrist hashing to calculate the hash for various positions. The hash table is used to look up various transpositions. For some positions I do not want to allow any ...
0
votes
0answers
45 views
Hashing algorithm which minimizes distribution
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
3
votes
1answer
62 views
How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?
Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental information it ...
2
votes
2answers
61 views
Rolling hash hacking
The hash value of a string $s$ is given by
$$
h(s) = \sum^{|s|}_{i = 1} s_i \cdot p^{|s| - i} \mod m; \text{ $m$ is prime, $m < 10^{12}$}.
$$
The string $s$, $p$, $m$ is given,
$|s| \le 14$, ...
0
votes
1answer
350 views
Separate Chaining hashing: time complexity of successful search
In a simple uniform hashing with chaining collision, the time complexity of a successful search is: $Θ(1 + (1 + \frac{α}{2} - \frac{α}{2n}))$ where $α=\frac{n}{m}$, but I don't understand how to ...
0
votes
1answer
49 views
Formal definition of hash function
I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote.
I cannot find a ...
0
votes
0answers
41 views
How to generate unique keys for different two dimensional matrices having different sizes?
No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it ...
0
votes
0answers
29 views
Protecting a specific sized message with some limitations
So I make a research on my own. I have a device it allows a 64bit message. I wanted to secure it but I 64bits arent just enough to hash it and encrypt it. Is there really any good Hash function out ...
0
votes
0answers
23 views
Hashfunction for unique character distributions
The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of ...
3
votes
1answer
106 views
generalizing ball-bin problem to k-universal family
I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal ...
0
votes
1answer
46 views
Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?
I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I ...
1
vote
2answers
103 views
Looking for memory-efficient way to detect hash collisions
Given a hash function H, it's possible that H(a) = H(b) = c
Let's assume we have a big data set [N1 ... Nk], with K items and we hash each item in this set
After operation is done, we'd get a set of ...
