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
292
questions
1
vote
1answer
43 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 ...
0
votes
1answer
16 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 ...
0
votes
0answers
22 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 ...
0
votes
1answer
37 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
0answers
20 views
Average-case retrieval time
The book CLRS claims these statements before introducing the topic of universal hashing:
If a malicious adversary chooses the keys to be hashed by some fixed hash function,
then the adversary can ...
2
votes
1answer
34 views
Quadratic probing variant scheme
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-...
0
votes
0answers
16 views
A successful search takes $\Theta(1 + \alpha)$ time on average when resolving collisions by chaining
I would to discuss a proof found in CLRS book please.
Theorem: In a hash table in which collisions are resolved by chaining, a successful search takes time $\Theta(1 + \alpha)$, on the average, under ...
1
vote
1answer
31 views
If $(h_2(k),m) = 1$ then $h_1(k)+ih_2(k) \bmod{m}$ is a permutation of $0,\ldots,m-1$
The following question appears in Introduction to Algorithms (CLRS):
Suppose that we use double hashing to resolve collisions; that is, we use the hash function $ h(k, i) = (h_1(k) + ih_2(k)) \bmod{m}...
0
votes
1answer
26 views
Can possiblity of hash collision be "zero" when we hash same file in different formats?
Let's say I have a file A, which is any normal file (pdf, jpeg, mp3 etc.)
Now I get the binary dump of file, say another file B{A}.
And the hexdump of file say, file H{A}.
Now I hash all the three ...
0
votes
0answers
17 views
Prove that if $k$ was the $(i+1)$st key to be inserted into the hash table, then $E[probes(k)]=\frac{1}{1-\frac{i}{m}}$
Theorem: Inserting an element into an open-address hash table with load factor α requires at
most $1/(1 − α)$ probes on average, assuming uniform hashing.
By following unsuccessful search strategy, we ...
1
vote
1answer
35 views
Number of probes in a unsuccessful search in open address hashing
Theorem: Given an open-address hash table with load factor $α = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1−α)$, assuming uniform
hashing.
Let us define the ...
1
vote
1answer
74 views
Can one brute force entries to create the whole file?
I want to know if one can brute-force a large list of entries (>10,00,000) in linear time to form a whole file.
For example:
I have an ebook and i extract all the words and symbols from that ebook....
1
vote
1answer
52 views
Prove that the expected length $E [n_{h(k)}]$ of the list containing key $k $ is at most $1 + \alpha$
Theorem: Suppose that a hash function $h$ is chosen from a universal collection of hash functions and is used to hash n keys into a table $ T$ of size $m$, using chaining to resolve collisions. If key ...
0
votes
2answers
60 views
Can 2 files have "same" "many" "different" types of hash?
I know that hash collision is possible with large number of files. But i want to know if 2 files can share "many , different" types of hash. I have 2 hashes SHA256 and BLAKE256 (Both will ...
2
votes
0answers
52 views
Proving that a successful search of hash function is $\Theta(1+\alpha)$
Question: Prove that successful search of hash function with chaining (list at each slot) takes $\Theta(1+\alpha)$.
Given a dictionary or hash table that has a chain at each slot in case we have a ...
2
votes
2answers
226 views
Implement a dictionary by using direct addressing on a huge array
For the following question from Introduction to Algorithms book, "We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage,...
1
vote
1answer
41 views
Why we get at most $N^2$ probe sequences using double hash function
Question:Given the following double hash function:
$$h(k,i) = (h_1(k) + i\times h_2(k)) \bmod{N}$$, where $h_1(k): key \to \mathbb{Z}$. $h(k,i)$ can generate $N^2$ probe sequences at most and $h_2(k)$ ...
0
votes
0answers
33 views
Prove that Horner's method produce only 6 collisions on 50000 English words
Polynomial for producing hash values:
$p(z)=a_0+a_1z+\cdots, a_{n-1}z^{n-1}$
Honor's method for that polynomial:
$$
p_0(z)=a_{n-1} \\
p_i(z)=a_{n-i-1}+zp_{i-1}(z), (i=1, \cdots, n-1)\\
$$
Problem: For ...
6
votes
1answer
254 views
Hashing using Horner’s Rule
When hashing a (key, value) pair where the key is a string, I have seen the following hash function in use:
E.g. $c_n + 256c_{n-1}+ 256^2c_{n-2}+...256^{n-1}c_1$, where this represents the string $...
2
votes
0answers
18 views
Does there exist a locality sensitive hashing for $\ell_p$-norm distance where $p>2$?
It is well known that the $p$-stable distribution can be used to generate locality sensitive hash code for $\ell_p$-norm distance measure where $p \le 2$. However, it seems that the situation for $p&...
0
votes
1answer
14 views
Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table
Context
Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions.
The table has a finite recycled memory (key % p is the <...
1
vote
1answer
33 views
Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash
I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
4
votes
1answer
149 views
Count Sketch probability bound
I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
1
vote
1answer
16 views
Universal hash function for strings of unbounded length
Is there a (weakly) universal hash function for strings without any assumption of the string length?
I did not find one on Google / Wikipedia.
2
votes
0answers
30 views
Finding the longest power subsequence
A power sequence is a sequence containing consecutive powers of a number starting from power one. for example $3^1, 3^2, 3^3$ is a power sequence. The question is to find the length of the longest ...
0
votes
0answers
17 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
65 views
Shuffling Bits For Uniform Distribution
I am writing a hashing algorithm to be used in the 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 ...
0
votes
0answers
19 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
21 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
23 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?
2
votes
1answer
110 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
50 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
46 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
48 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
64 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
91 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
55 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
231 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
31 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
144 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
39 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 ...
1
vote
0answers
69 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
20 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
25 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
46 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
84 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 ...
