Questions tagged [hashing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
18 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 $...
2
votes
0answers
13 views

Expected search times with linear vs quadratic 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. ...
0
votes
1answer
29 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
27 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
17 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 ...
2
votes
1answer
54 views

Static Perfect Hashing - FKS

I am trying to understand perfect hashing aka FKS, but I have a few questions. From my understanding, perfect hashing is a two level hashing in which you take a hash function from a universal family ...
0
votes
1answer
18 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
28 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
38 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
87 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,...
6
votes
4answers
13k 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 ...
2
votes
0answers
38 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
52 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
167 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
18 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
427 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
193 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
1k 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
8 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
146 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
59 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
25 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
39 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
48 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
55 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
155 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
58 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
65 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
31 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
34 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
96 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
40 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
210 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
195 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 ...
2
votes
1answer
39 views

Is there a way to theoretically compare hash functions?

Say I am given two hash functions f1 and f2 is there anyway that I can prove one hash function will produce fewer collisions ...
1
vote
1answer
85 views

Prove hash family is 3-wise independent

Let $q$ be a prime number and let $\mathbb{Z}_q = \left\{1,\dots,q-1\right\}$; I need to prove that the family $\mathcal{H} = \left\{h_s \colon \mathbb{Z}_q \rightarrow \mathbb{Z}_q\right\}_{s \in \...
1
vote
2answers
177 views

Why does Locality Sensitive Hashing use multiple sets of hash tables? How does it guarantee similarity?

With locality sensitive hashing (specifically multi-probe hashing http://www.cs.princeton.edu/cass/papers/mplsh_vldb07.pdf) how are the guarantee of similarity returns made? Why are there multiple ...
1
vote
1answer
541 views

Probability that a random hash from a universal family is injective

This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows: In class we saw universal hashing as the solution to ...
1
vote
1answer
238 views

In most locality sensitive hashing implemensions of SimHash, why is the cosine distance used and not the euclidean distance?

In Chapter 3 of Mining of Massive Datasets, the basis of locality sensitive hashing is explained. They notably mention simhash for the cosine distance, where random hyperplanes are generated, and for ...
0
votes
1answer
37 views

Do not understand a concept in analysis of open-address hashing

I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor α=n/m<1, the expected number of ...
0
votes
1answer
887 views

How is this the expected number of of probes in open-address hashing?

I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor $\alpha = n/m < 1$, the expected ...
2
votes
1answer
109 views

Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation

In this blog the author states that the following So we now have a rather poor estimate of the number of values in the dataset based on bit patterns. How can we improve on it? One ...
3
votes
1answer
164 views

non-binary locality-sensitive hashing with random projections

I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to ...
39
votes
5answers
43k views

What exactly (and precisely) is “hash?”

I have heard the word "hash" being used in different contexts (all within the world of computing) with different meanings. For example, in the book Learn Python the Hard Way, in the chapter on ...
0
votes
1answer
608 views

How to actually implement universal hashing?

I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I ...
0
votes
0answers
21 views

Hashing routine explanation [duplicate]

As the title states, I would like to know what a hashing routine is. I found online about hashing algorithms but I heard it, being used in a different context.
0
votes
0answers
172 views

Proof of expected number of probes in an unsuccessful search (open addressing hashing)

I'm seeking some clarification on the proof of the expected number of probes in an unsuccessful search in open addressing hashing. The proof is given in CLRS on page 275, section 11.4 (Open addressing)...
1
vote
1answer
52 views

Generate numeric or string ID for a sequence of elements

How to generate a numeric or string id(not very large text) for a sequence of elements where ordering doesn't matter. Example: [41,1001,32] should generate the ...