Questions tagged [hashing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
36
votes
5answers
38k 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 ...
2
votes
3answers
338 views

What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n_j = T[j]$ be the size of the ...
3
votes
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 ...
2
votes
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 ...
2
votes
1answer
711 views

Locality-sensitive hashing random projection

I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r_{i}} \sim \mathcal{N}(0, 1)^d$ that ...
1
vote
0answers
94 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
260 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 ...
0
votes
1answer
135 views

Help in understanding how to apply nonlinear function in hashing

Can somebody help in brainstorming how to apply the map as a hashing function? I am aware that chaos is used in cryptography but I fail to understand how to apply it. Most popular hashing techniques ...
0
votes
2answers
501 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 ...