# All Questions

7 questions
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)...
1answer
19 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 ...
1answer
62 views

### General name for linked lists based on hashes

I am thinking of a particular datastructure, but don't know the name of it. A sequence of elements may be modeled by a collection of some X, where each X consists of: The element, serialized as a ...
3answers
2k views

### Hash function to hash 6-digit positive integers

Let UID denote a unique identifier. UID's are represented as 6-digit positive integers. I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for ...
1answer
90 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 ...
1answer
346 views

### Is FKS hashing really linear space?

In FKS hashing, I wonder if the size of the table $G[ 1..n]$ (used to record the functions $g_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability ...
1answer
50 views

### Finding a (minimal?) program that maps $M$ items to indices $[0,M)$

Let's say there are $M$ strings that we are trying to create a perfect hash for such that we get as output of the hash $[0,M)$ with no collisions, when hashing those $M$ items. I know that there are ...