# Questions tagged [hashing]

The tag has no usage guidance.

130 questions
Filter by
Sorted by
Tagged with
1answer
38 views

0answers
21 views

### If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?

I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?
2answers
445 views

### Number of probes in a successful search in open address hashing

Given an open-address hash table with $\alpha$ < 1, the expected number of probes in a successful search is at most $\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$ I read this in a book and the proof ...
2answers
67 views

1answer
82 views

### Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)

I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function. The versions are as follows: ...
1answer
31 views

### Hash function, $h(k) = \lfloor km \rfloor$ is simple uniform for real $k$ independently, uniformly distributed in the range $0 \leq k < 1$

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following statement: If the keys are known to be random real numbers $k$ independently and uniformly ...
1answer
87 views

### Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
2answers
345 views

### Double Hashing with Strings as key

How would you choose the second hash function with for double hashing with string as key? My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is ...
1answer
46 views

### Analysis of Universal Hashing

I was reading universal Hashing from Introduction to Algorithms by Cormen et al., and came across the following corollary regarding search, insert and delete functions on Universally Hashed tables: ...
1answer
40 views

### Is there a way to hash a turing machine?

If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
0answers
45 views

### Hashing algorithm which minimizes distribution

Consider applications A1, A2 .. AN having properties P11, P12,... PN1, PN2.. Also consider buckets ...
1answer
131 views

### Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list

Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus ...
3answers
110 views

0answers
51 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 ...
1answer
33 views

### What is the best of given hashfunctions?

In our exam on algorithms there was a question, where given 3 hashfunctions we had to chose one and explain why it's the best. h_1(x,i)=(x+5*i) mod 1000 h_2(x,i)=(x+17*i) mod 1000 h_3(x,i)=(x+32*i) ...
1answer
83 views

### In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?

See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time ...
1answer
48 views

### Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?

I believe primary clustering is a problem with the linear probing method of hash collision resolution. But the description makes it sound like there can be multiple clusters of contiguous blocks. I ...
1answer
42 views

2answers
1k views

### Hash function to return only positive number from integer

What would be a good hash function that will return a positive integer value, even if the key is an negative integer value? How do I pick a hash function? So what I would want is to associate negative ...
4answers
235 views

### How do you find a hash function that respects a custom equality function?

I've been tasked with hashing arbitrary types in C++, with the caveat that A == B implies hash(A) == hash(B) even if equality of ...
0answers
33 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 ...
0answers
65 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....
3answers
1k views

### Simple Uniform Hashing Assumption and worst-case complexity for hash tables

Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)? It says in the Wikipedia article that this assumption implies ...
0answers
17 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. ...
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$ "...
1answer
153 views

### Given a family of hash functions in table form, how can I know whether it's universal?

I've been given the following two families of hash functions: H and G Each family has three functions $\{0,1,2,3,4\} \to \{0,1,2\}$ that can be seen in the tables above. For each family I need to ...
1answer
566 views

### is modulo of hash function is evenly distributed?

if I take the result of a 32bit hash function(the param is random string) and apply module N on the result - will the values be evenly distributed? so if I have a histogram of values [0,N-1] will the ...