Questions tagged [hashing]
The hashing tag has no usage guidance.
117
questions
1
vote
2answers
71 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
15 views
Space complexity of using a pairwise independent hash family
I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011, https:...
2
votes
0answers
30 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, ...
1
vote
1answer
39 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 $\...
1
vote
0answers
32 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:
...
1
vote
1answer
13 views
Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following statement:
If the keys are known to be random real numbers $k$ independently and uniformly ...
1
vote
0answers
12 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 ...
2
votes
1answer
48 views
Uniform Hashing. Understanding space occupancy and choice of functions
I'm having troubles understanding two things from some notes about Uniform Hashing.
Here's the copy-pasted part of the notes:
Let us first argue by a counting argument why the uniformity property,
we ...
0
votes
0answers
8 views
Analysis of succefull and unsuccefull search in a sorted hash table that resolves collision by chaining
I am trying to solve a problem where we have to analyze the expected time for successful and unsuccessful search in a hash table of $n$ elements and $m$ slots . But the hash table has a property that ...
1
vote
1answer
22 views
Analysis of Universal Hashing
I was reading universal Hashing from Introduction to Algorithms by Cormen et al., and came across the following corollary regarding search, insert and delete functions on Universally Hashed tables:
...
1
vote
1answer
24 views
Is there a way to hash a turing machine?
If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
0
votes
0answers
44 views
Hashing algorithm which minimizes distribution
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
0
votes
1answer
30 views
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus ...
0
votes
0answers
13 views
Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(Lā (1+1/Ī±))
This question is from CLRS. The following is what I understand:
The procedure is as follows:
1. First we randomly choose one index in T[m]
2. Let nk denote the number of elements in the chosen slot T[...
0
votes
0answers
15 views
Are elements of the Hash Table's backing array Linked Lists from the initial point when using Separate Chaining?
As usual, did quite a research in different books and academic articles, but can't really get a clear picture.
For the Hashing Collision resolution in Hash Tables, we have one very popular strategy ...
4
votes
0answers
58 views
Expected search times with quadratic vs linear probing
Why exactly does quadratic probing lead to a shorter avg. search time than linear probing?
I fully get that linear probing leads to a higher concentration of used slots in the hash table (i.e. ...
2
votes
2answers
45 views
Building a perfect hashing table
My understanding is that one way to build a perfect hash, as per CLRS, is to use two levels of hashing, with universal hashing functions at each level.
More specifically, CLRS shows that assuming $...
0
votes
1answer
37 views
Bit representation of the hashing multiplication method
In the picture below from CLRS, I fail to understand why exactly $h(k)$ = the $p$ highest-order bits of the lower w-bit half of the product.
For context, this is supposed to compute
$h(k) = \lfloor ...
1
vote
1answer
35 views
Universal hashing - insert / search / delete
I don't understand the highlighted text below in CLRS 3rd Ed.:
I'm not sure I even understand what the sentence is trying to say. For example:
What do they mean by "... operations containing $\...
0
votes
0answers
19 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
1answer
28 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 ...
0
votes
1answer
29 views
What is the best of given hashfunctions?
In our exam on algorithms there was a question, where given 3 hashfunctions we had to chose one and explain why it's the best.
h_1(x,i)=(x+5*i) mod 1000
h_2(x,i)=(x+17*i) mod 1000
h_3(x,i)=(x+32*i) ...
1
vote
0answers
40 views
In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?
See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time ...
2
votes
1answer
350 views
Flajolet-Martin Algorithm : question about use of certain hash functions
this is a question given in a PDF about streaming algorithms (this isnt an assignment but im trying to understand)
Exercise 4.4.1 : Suppose our stream consists of the integers 3, 1, 4,
1, 5, 9, 2,...
7
votes
4answers
14k views
Two-way Hash Functions
While I'm aware most (good) hash functions are one-way (or at least mostly so), I'm wondering if there's any construct (not necessarily called a hash function) which behaves in many ways like a hash ...
1
vote
0answers
40 views
Find a non-minimal sequence of elements covering the support set
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in $O(1)$ time with arbitrary positions). Denote $\text{...
3
votes
0answers
53 views
Probability of colisson for classes of hash functions
I am going through some old exams in one of my courses, and I don't have access to solutions. I've found a problem which I am not sure how to tackle. I am not looking for the answer but some help/...
0
votes
2answers
359 views
Hash function to return only positive number from integer
What would be a good hash function that will return a positive integer value, even if the key is an negative integer value? How do I pick a hash function? So what I would want is to associate negative ...
0
votes
0answers
22 views
learning the private key by reusing same random variable k in ELgamal
i wonder: if for some reason, someone, say alice, sends unencrypted messages to bob and signs it using elgamal signature, can oscar,the adversary, gain knowledge of the private key if alice reused the ...
1
vote
3answers
583 views
Simple Uniform Hashing Assumption and worst-case complexity for hash tables
Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)?
It says in the Wikipedia article that this assumption implies ...
3
votes
0answers
222 views
Time complexity of obtaining the set of distinct elements in a sequence?
Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we can read, write and compare them in O(1) time with arbitrary positions). What's known ...
1
vote
3answers
2k views
How does Rabin fingerprint finds breakpoints (chunk boundary)?
I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin ...
0
votes
0answers
9 views
Creating a specific hash setup
While solving a practice exam, this is the question I could not answer. Any help is appreciated. I am new to hashing and have no idea how to solve this question.
Let $H$ be a $(0.15, 0.85, 0.9, 0.1)$-...
5
votes
4answers
167 views
How do you find a hash function that respects a custom equality function?
I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of ...
1
vote
2answers
63 views
Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?
This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy ...
1
vote
0answers
28 views
Linear probing and tabulation hashing
I'm currently reading the paper "The Power of Simple Tabulation Hashing" by Mihai Patrascu and Mikkel Thorup [1] because I want to adapt the proof of the constant time complexity of linear probing for ...
1
vote
0answers
49 views
Structure Preserving Continuous Hash Function
This question was originally posted on super user, but redirected here based on some suggestions.
I am completely new with computer science, and not only recently did I run into the notion of hashing....
2
votes
1answer
60 views
Given a family of hash functions in table form, how can I know whether it's universal?
I've been given the following two families of hash functions:
H
and
G
Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to ...
1
vote
0answers
13 views
While computing signature matrix in min hashing, can I take nth row of the permutation P in which document d has value 1?
I am learning about some techniques to find similarity between documents. One of the methods is Min Hashing. According to Min Hashing we can find a signature matrix given a random permutation, P. ...
0
votes
0answers
34 views
Construction of hash function with a given distribution
Two questions about the construction of a hash function:
Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
3
votes
1answer
64 views
The expectation of the total number of pairs of keys in a hash table that collide using universal hashing
I am reading CLRS relating to perfect hashing. When computing the
$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]
$$
where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
0
votes
1answer
234 views
is modulo of hash function is evenly distributed?
if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed?
so if I have a histogram of values [0,N-1] will the ...
1
vote
2answers
64 views
Check whether all elements are different
Assume we have $n$ double elements $a_1 \dots a_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer ...
0
votes
1answer
69 views
Does this excerpt from the linear probing Wikipedia page make an assumption?
Here is the excerpt from the linear probing page at Wikipedia.
To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and ...
1
vote
1answer
35 views
What are the k-collections described in ch. 8 of “An Introduction to the Analysis of Algorithms” by Sedgewick
In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425.
My confusion is how to identify the k-...
0
votes
0answers
39 views
Search operation in hash table
Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining.
Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and ...
3
votes
1answer
111 views
Small space hash functions that are weakly but not strongly universal
This is a follow up to this this question about weakly universal hash functions
A family of hash functions $H_w$ is said to be weakly universal if for all $x \ne y$ :
$$P_{h \in H_w}(h(x) = h(y)) \...
1
vote
1answer
43 views
additive hash function
Do functions with the following properties exists for x being arbitrary stream of bytes:
op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation ...
2
votes
1answer
241 views
Ketama hash explanation
(I originally posted this on stackoverflow but thought it would be a better fit here)
I'm trying to understand the Ketama hash code used in consistent hashing.
link and snippet below:
...
6
votes
3answers
213 views
Can we remove duplicates faster than we can sort?
The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers):
Given a sequence $S_\text{in}$ of $n$ integers, produce a ...
