Questions tagged [hashing]
The hashing tag has no usage guidance.
133
questions
0
votes
0answers
14 views
Order-preserving perfect hashing of integer tuples
There is an $M \times N$ integer matrix $A = [a_{ij}]$, $M \gg N \ $,
$\forall j \ \exists a_{max_j} \leq N \ \forall i : 0 \leq a_{ij} < a_{max_j} \ $,
$\forall j \ \forall n \in [0, a_{max_j}) \ ...
1
vote
1answer
30 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
0answers
47 views
Confused about a corollary in MIT.Introduction.to.Algorithms(CLRS), seek help
Desc'
I was reading CLRS Book's chapter 11 Hash Tables, and encountering some problems.
There is an corollary in CLRS book, in Page 275 (quoted on the bottom of post), which discussed the expected ...
0
votes
1answer
42 views
Proof the probability of a collision for a hash function
I don't know how to prove the following:
Let $a$ be randomly chosen out of $\{ 1,..., p-1\}$ and $b$ randomly chosen out of $\{ 0,..., p-1\}$.
Let $m$ be a natural number smaller than a prime number $...
1
vote
2answers
351 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 ...
0
votes
1answer
13 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
86 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 ...
0
votes
1answer
84 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
36 views
Obtaining an expectation in uniform hashing
long shot question but I am super stuck.
Donald Knuth has proven (p. 8 here, equation 12) that the probability that the maximum value in uniform hashing is smaller than $n/2$ is equal to 0.288. I ...
2
votes
1answer
43 views
How do we pick and switch hash functions from a universal family?
When we have a universal family of hash functions, it gives us a few useful mathematical guarantees. But, if we pick a specific function from the family and use it all the time it's effectively like ...
0
votes
0answers
30 views
Bloom filter variant(using only half of it)
A Bloom filter is an array $B[1..m]$ of bits, together with a collection of $k$ independent ideal random hash functions $h_1,h_2,...,h_k$. To insert an item $x$ into a Bloom filter, we set $B[h_i(x)] ←...
2
votes
2answers
709 views
Number of probes in a successful search in open address hashing
Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$
I read this in a book and the proof ...
0
votes
0answers
21 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?
4
votes
2answers
67 views
Why is tabulated hashing 3-wise independent but not 4-wise independent?
Tabulated hashing uses tables of random numbers to compute hash values.
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $...
1
vote
0answers
20 views
How are virtual nodes placed / calculated to implement consistent hashing
I am reading about consistent hashing for system design and I understand the application of consistent hashing and the use of virtual nodes. I want to understand how to calculate the optimum number of ...
0
votes
0answers
13 views
What are overlay & underlaying topologies in DHT?
We are covering Distributed Hash Tables in my "Networks" class and one of the subsections is about the improvements that can be made to increase the performance of the chord. Here, the ...
1
vote
2answers
206 views
Constraint on Universal set of hash functions
I was reading hashing from CLRS. In it author says:
Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a ...
0
votes
0answers
13 views
At what tier does consistent hashing get implemented?
Where does the code for consistent hashing reside? I have read how it is implemented (at a high level), but am unsure if it is exposed as a microservice between the web server and the app servers or ...
2
votes
3answers
114 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 $...
1
vote
2answers
53 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 $$(...
5
votes
2answers
3k views
simple uniform hashing: unclear definition of probability
I am trying to understand the assumption of Simple Uniform Hashing (SUHA) as e.g., in CLRS textbook; or other courses about hashing.
The usual description given to SUHA is (cf. CLRS):
"we shall ...
1
vote
1answer
126 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 ...
1
vote
1answer
62 views
Using hashing to solve 4-sum problem
The famous 4-sum problem is to find 4 elements at unique indices in an array which sum to a given X. I was looking at one solution I found:
...
0
votes
0answers
39 views
Quadratic probing in hash tables
I need to construct a hash table with initially $7$ empty entries. Now add $6$ values to the table using the quadratic probing function
$$
s(j,k) = \lceil j/2 \rceil^2 (-1)^j
$$
such that for some ...
0
votes
0answers
216 views
How does secondary clustering occur in hashing?
One of my friends said me that secondary clustering is the phenomenon occurring when the probe sequence has the same initial value. This definition shows that secondary clustering occurs in linear ...
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
37 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
25 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
41 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
67 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
31 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
1answer
89 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 ...
1
vote
1answer
47 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
40 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
45 views
Hashing algorithm which minimizes distribution
Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
0
votes
1answer
140 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 ...
4
votes
0answers
116 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
1answer
58 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
42 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
58 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
50 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
33 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) ...
3
votes
1answer
2k 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,...
9
votes
4answers
18k 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{...
2
votes
0answers
58 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
1k 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 ...
3
votes
3answers
1k 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 ...
4
votes
0answers
449 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 ...