Questions tagged [hashing]

The tag has no usage guidance.

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
259 views

Mean and variance of number of buckets of length $i$ in hashing with chaining

Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $...
3
votes
0answers
154 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 ...
2
votes
0answers
32 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/...
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
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
24 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
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. ...
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
0answers
30 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
69 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}...
0
votes
0answers
31 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{...
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)$-...
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$ "...
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 ...
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(...
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 ...
0
votes
0answers
143 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)...
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 ...
0
votes
0answers
42 views

Verification of extendible hashing proof

I have to proof this theorem: "An extendible hashing table always contains at least one bucket where only one pointer points to after an element is added". I made this proof, but I'm not completely ...