Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [hashing]

The tag has no usage guidance.

2
votes
1answer
25 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 ...
5
votes
0answers
209 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 $...
2
votes
0answers
994 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.
2
votes
0answers
92 views

What is the deterministic time complexity of obtaining the set of distinct elements?

Consider a sequence $s$ of $n$ integers (let's ignore the specifics of their representation and just suppose we have can read, write and compare them in O(1) time with arbitrary positions). What's ...
1
vote
0answers
22 views

What's the problem with deletion in FKS perfect hashing?

In FKS perfect hashing we construct two levels of tables. To lookup an element we first check in the first table which points us to the correct second level table that will contain the element if it ...
1
vote
0answers
90 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
29 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
54 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
22 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
25 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
41 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
25 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
87 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
794 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
38 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 ...