Questions tagged [hashing]
The hashing tag has no usage guidance.
95
questions
1
vote
3answers
246 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
153 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 ...
0
votes
0answers
30 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
votes
0answers
25 views
Doubt in Expected number of probes in successful seach in open address hashing
My attempt:
I need to find exected number of probes in case of successful search. I am assuming, n elements and m slots in hash table
E(# of probes) = average of {1st probe success , 2nd probe ...
0
votes
2answers
42 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 ...
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
129 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
56 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
21 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
23 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
29 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
10 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
33 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
50 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
89 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
49 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
61 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
30 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
Probability in 1-universal hash function
I am trying to prepare for an exam and I am not sure how to solve this task:
Given is a hash function with m buckets, which uses a 1-universal hash function h: U -> H and handles collisions with ...
0
votes
0answers
30 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
69 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
38 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 ...
0
votes
0answers
48 views
How minimal perfect hash functions are discovered / created
I have been looking at How to create minimal perfect hash functions, and come across resources such as these:
Finding Succinct Ordered Minimal Perfect Hash Functions
$$h(x) = \Bigg[\sum_{j=0}^{m-1}g(...
2
votes
1answer
147 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:
...
0
votes
0answers
31 views
Dynamic Perfect Hashing and Lower Bound
I am writing a Seminar about dynamic perfect hashing and its lower bound by the FKS schema using the the adversary method mentioned here by using a Tree data structure. But somehow i don t get how ...
6
votes
3answers
171 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
38 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
66 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
120 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
439 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
196 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
29 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
633 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
106 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
149 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 ...
38
votes
5answers
40k 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
530 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
20 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
137 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 ...
0
votes
0answers
1k views
Rolling Hash calculation with Horner's method
I understood how Horner's method reduces the complexity(number of operations) while evaluating a polynomial.
I have a character array derived from a string
...
2
votes
1answer
57 views
Avoiding correlated values and reduced collision resistance in multiple hash states
I need to design a hash function that fits this criteria:
Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
Produces an n-bit hash digest, ...
0
votes
1answer
22 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 ...
2
votes
0answers
1k views
Open hashing vs closed hashing
What are advantages of closed hashing over open hashing?
I know the difference between those two but can't figure out why would closed hashing be better in any way.
Thanks.
1
vote
1answer
1k 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 ...
2
votes
1answer
39 views
Is there a heuristic or function to determine if two arrays of integers are alike or similar
What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say a = [0, 1, 2, 3, 4], <...
0
votes
2answers
715 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 ...
1
vote
0answers
98 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
142 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 ...
