Questions tagged [hashing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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
1answer
25 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
25 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 ...
1
vote
1answer
48 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 ...
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 ...
1
vote
1answer
2k 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
240 views

Practicality of compressing data with hashing algorithms

I want to compress the string 0cc175b9c0f1b6a831c399e269772661. I can do so by storing the string a, and, when decompressing, using a as input for the MD5 hash algorithm to get the original string. I ...
1
vote
1answer
66 views

Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?

Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that $$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$ Where two ...
1
vote
1answer
150 views

Collision resistant Hash function in chaos cryptography

In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat ...
1
vote
2answers
169 views

Method for finding Hyperrectangle that a coordinate is within

I have a problem at work where I have set of hyperrectangles, in no particular order, that do not overlap and when unioned create a hyperrectangle with no gaps. At the moment I am looking for a way to ...
1
vote
1answer
65 views

Generate collision resistant identifiers with two-way hashing

Objective: We want to generate a unique and reproducible identifier for a given slice of bytes and avoid collisions. High-level idea: Compute $$fK := hash(k_1)\; and\; sK := hash(k_1^{-1})\; where\; ...
1
vote
1answer
39 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 $\...
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-...
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 ...
1
vote
2answers
243 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
271 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 ...
1
vote
2answers
1k views

Cuckoo hashing proof of cycle

If we come to the situation when we have to insert again the original key into the original table, I believe we have found a cycle. Is there a way to prove this?
1
vote
1answer
125 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 ...
1
vote
1answer
51 views

Is this some kind of hashing?

Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d \}...
1
vote
1answer
133 views

Different probabilistic statement for Simple Uniform Hashing

Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them ...
1
vote
0answers
17 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:...
1
vote
0answers
33 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
0answers
13 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
77 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
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 ...
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{...
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
50 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....
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. ...
1
vote
1answer
114 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
1answer
570 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
0answers
102 views

Bloom filters vs storing hashes as numbers

In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
1
vote
1answer
36 views

Unique ID from date and rotating offset

Hopefully this is the right board for my question, We are facing an issue creating a unique ID from the following inputs : datetime (can be present more than once in the same set, cannot not be ...
1
vote
0answers
26 views

Prove you computed hash^r(input) for some cryptographic hash function [closed]

What is the most efficient way to prove that a person computed r rounds of some cryptographic hash function (ex. sha256) on an input?. The trivial solution seems to be to show all r hashes, where <...
1
vote
0answers
31 views

Time complexity of finding duplicates across multiple lists using hashing

If I have m lists with n elements each, how would I go about finding duplicates in them (i.e. an element is in more than one of the lists)? My idea is to use hashing on the elements inside the list, ...
1
vote
0answers
84 views

Checking whether a given Hashing Function fulfills Uniform Hashing Condition

I am learning about Hashing and have struggles with the following assignment: $U$ is a universe of keys with $Z(m)=\{0,\ldots, m-1 \}$ the amount of possible hash-values. Given $U= \mathbb{Z}_{55} = ...
0
votes
2answers
681 views

Hash functions and pathological data sets

So I'm watching an Algorithms course in Coursera, and we are currently discussing hash tables. He's talking about the importance of a good hash function, and about how an ideal hash function would be ...
0
votes
2answers
404 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
1answer
260 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 ...
0
votes
2answers
890 views

Probability of hash collision in the case of two parallel hashes

I understand how to calculate the probability of a hash collision. I am designing a DB and have a potential case where a record could have the inherited hash of its parent plus its own hash, meaning I ...
0
votes
1answer
108 views

Reading CLRS analysis of hashing with chaining

I'm currently reading an analysis hashing with chaining, and it goes over two examples: In the first, the search is unsuccessful; no element in the table has key k. In the second, the search ...
0
votes
1answer
258 views

Hashing Probabilities

I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a ...
0
votes
1answer
33 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
1answer
38 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 ...
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) ...
0
votes
1answer
31 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
1k 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 ...
0
votes
1answer
71 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 ...
0
votes
1answer
726 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
1answer
30 views

Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1

This is an exam question from my algorithms and data structures course. You imagine an hash function with h: U->{0,..m} (this is from the original question, but i think m-1 would be correct) and n ...