# Questions tagged [hashing]

The tag has no usage guidance.

90 questions
Filter by
Sorted by
Tagged with
0answers
12 views

### Linear probing and tabulation hashing

I'm currently reading the paper "The Power of Simple Tabulation Hashing" by Mihai Patrascu and Mikkel Thorup  because I want to adapt the proof of the constant time complexity of linear probing for ...
2answers
65 views

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

My question: 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 ...
0answers
14 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....
0answers
118 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 can read, write and compare them in O(1) time with arbitrary positions). What's known ...
1answer
23 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 ...
0answers
10 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
30 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
35 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 ...
2answers
1k views

### How does Rabin fingerprint finds breakpoints (chunk boundary)?

I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin ...
1answer
49 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 ...
2answers
48 views

### Check whether all elements are different

Assume we have $n$ double elements $a_1 \dots a_n$. We want to find out if two of the elements of the array are identical. And we have a hash function $h(x)$ which assigns each double value an integer ...
1answer
59 views

### Does this excerpt from the linear probing Wikipedia page make an assumption?

Here is the excerpt from the linear probing page at Wikipedia. To search for a given key x, the cells of T are examined, beginning with the cell at index h(x) (where h is the hash function) and ...
1answer
29 views

### What are the k-collections described in ch. 8 of “An Introduction to the Analysis of Algorithms” by Sedgewick

In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425. My confusion is how to identify the k-...
0answers
26 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 ...
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 ...
1answer
54 views

1answer
106 views

### Ketama hash explanation

(I originally posted this on stackoverflow but thought it would be a better fit here) I'm trying to understand the Ketama hash code used in consistent hashing. link and snippet below: ...
0answers
27 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 ...
1answer
39 views

### Is there a running hash algorithm that can efficiently handle arbitrary updates to a file's contents?

This question is about file-hashing/fingerprinting algorithms (similar to SHA-1 and MD5 and so on). Those algorithms are handy ...
3answers
149 views

### Can we remove duplicates faster than we can sort?

The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers): Given a sequence $S_\text{in}$ of $n$ integers, produce a ...
1answer
36 views

### Is there a way to theoretically compare hash functions?

Say I am given two hash functions f1 and f2 is there anyway that I can prove one hash function will produce fewer collisions ...
1answer
43 views

1answer
30 views

### Unique ID from date and rotating offset

Hopefully this is the right board for my question, We are facing an issue creating a unique ID from the following inputs : datetime (can be present more than once in the same set, cannot not be ...
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 ...
0answers
26 views

### Prove you computed hash^r(input) for some cryptographic hash function [closed]

What is the most efficient way to prove that a person computed r rounds of some cryptographic hash function (ex. sha256) on an input?. The trivial solution seems to be to show all r hashes, where <...
2answers
969 views

### Cuckoo hashing proof of cycle

If we come to the situation when we have to insert again the original key into the original table, I believe we have found a cycle. Is there a way to prove this?