Questions tagged [hashing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
173 views

Using random projections for locally sensitive hashing

I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents. The proof is such that based on cosine similarity to the vector. In other ...
0
votes
1answer
2k views

How would you prove a family of functions is universal?

A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a ...
0
votes
1answer
165 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
0answers
8 views

Analysis of succefull and unsuccefull search in a sorted hash table that resolves collision by chaining

I am trying to solve a problem where we have to analyze the expected time for successful and unsuccessful search in a hash table of $n$ elements and $m$ slots . But the hash table has a property that ...
0
votes
0answers
45 views

Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
0
votes
0answers
13 views

Describe a procedure that selects a key uniformly at random from among the keys in the hash table and returns it in expected time O(L⋅(1+1/α))

This question is from CLRS. The following is what I understand: The procedure is as follows: 1. First we randomly choose one index in T[m] 2. Let nk denote the number of elements in the chosen slot T[...
0
votes
0answers
15 views

Are elements of the Hash Table's backing array Linked Lists from the initial point when using Separate Chaining?

As usual, did quite a research in different books and academic articles, but can't really get a clear picture. For the Hashing Collision resolution in Hash Tables, we have one very popular strategy ...
0
votes
0answers
21 views

How to generate unique keys for different two dimensional matrices having different sizes?

No. of rows in the table (as given in image) is not known beforehand . The problem I am dealing with generates different 2-D matrices based on the input data given. As soon as a matrix generates it ...
0
votes
0answers
23 views

learning the private key by reusing same random variable k in ELgamal

i wonder: if for some reason, someone, say alice, sends unencrypted messages to bob and signs it using elgamal signature, can oscar,the adversary, gain knowledge of the private key if alice reused the ...
0
votes
0answers
9 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
34 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
39 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
21 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
191 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
2k 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
44 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 ...
-1
votes
1answer
181 views

Help in understanding calculation of hash collision from a document

UPDATE In an earlier question of mine asked here : https://math.stackexchange.com/questions/2206095/beginner-level-understanding-concept-on-how-to-derive-probability-of-hash-collis , I got the answer ...
-2
votes
0answers
22 views

Probability of false positive for lookup in hashtable

I am going over Mikkel Thorups notes on hashing, as revision, and I came to the following exercise that i cannot see how to tackle (even initially - I know this is not ideal for a question.) $$ \...

1 2
3