# Questions tagged [hash]

Mathematical function that maps arbitrarily-sized data to fixed-size integers, often used as keys in hash tables or to help ensure data integrity

342 questions
Filter by
Sorted by
Tagged with
49 views

### Where was DJBX33A first published?

Daniel J Bernstein's "Multiply 33 and add" simple hash is surprisingly hard to find the original reference to. Googling provides descriptions in language implementations such as PHP ...
• 723
1 vote
15 views

### Effect of using signed vectors for LSH Random Projection (Simhash)

Simhash is an text similarity algorithm proposed by Moses Charikar in his paper "Similarity Estimation Techniques from Rounding Algorithms". However, in his original paper, he proposed to ...
• 111
1 vote
76 views

### Transform any string into the shortest coherent/unique numeric identifiant

Is there some algorithm that can transform any string input (of any length) into a shortest possible coherent/unique numeric identifiant. By "coherent", I mean that the same input will ...
• 111
1 vote
90 views

### Understanding Polynomial Rolling Hash Function by Modular Arithmetic

I was learning the Polynomial Hash function in python, the one used in Rabin Karp Algorithm This is the implementation I was taught: ...
1 vote
66 views

### How bad re-hashing can cost?

Lets assume that the load factor of a hash table of size $n$ became inappropriate. The process of re-hashing involves choosing a new hash function. A good choice of a new function will make the cost ...
• 185
1 vote
122 views

### Using XOR operation, a MOD operation compute a function f(n)

I had a difficult assignment in my Data Structures and Algorithms class. We need to implement a program that computes a function f(n) based on the following known values of n and f(n): n : 9689 ...
14 views

### Hash function for use with hash table, given power distributed integers

Suppose I have integers that follows a power distribution: $P(n) \propto 1/(n + 1)^\alpha, n \geq 0$ What hash function is a good choice to avoid collisions. The usecase is keys in an ...
• 149
52 views

### Can you unwind a cryptographic hash function's last round?

Given a cryptographic hash, $\text{hash}(A || B || C)$, and the last block added to the hash, $C$, can you determine $\text{hash}(A || B)$? In other words, can you roll back the last round of a ...
• 145
72 views

### A good way to hash two numbers with known properties together

I have two 64-bit numbers a and b which have a few properties: only 49 out of the 64 bits are used (15 bits are always 0), and ...
1 vote
41 views

1 vote
205 views

### How to use a worst case scenario in Rolling Hash: Rabin Karp Algorithm when the given string only contains the occurrences of "a and b?"

Issue: I am having a hard time figuring out how to use the worst case for Rolling Hash, especially if the occurrences are only "a and b" for the string. Not only that but it is a bit of a ...
66 views

### Why using nC2*1/365 to calculate the birthday paradox is incorrect

The birthday paradox is basically that assume there are 365 days in a year(ignore the effect of Febuary 29th), each person's birthday is uniformly random in these 365 days and independent with others. ...
62 views

### Is there any algorithm to find all unique pairs of People with age equal to a given number in less than O(n²)

I have a problem where I have to find all the pairs of a list of People where the sum of their age is equal to a given number under time complexity less than O(N²) ...
1 vote
30 views

### Sampling unique records from a large dataframe

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe? Some sort of sampling algorithm?
1 vote
64 views

### Universal family of hash functions — dependent on table size?

Given the following family of hash functions: $$\mathbb{H} = \{h_c(x) = (12x + c) \bmod m \mid c \in \mathbb{N} \},$$ where $m$ is the key size. Prove that $\mathbb{H}$ is not a universal ...
• 11
594 views

### Implementing Flajolet–Martin algorithm in Python

I am stuck on what to do. I am trying to create a simple implementation of the Flajolet–Martin algorithm using Python. The stream will be the contents of a text file and you will produce an ...
237 views

### the load factor in hash table

What is numerically the best value or range of values used as a reference for the load factor used in the hash table? What is the pseudo-code of the “rehashing” method, which is applied when many ...
1 vote
567 views

### Hash / Compression algorithm to shorten text?

I desperately need a hash / compression function that is suited to shorten text. The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ...
• 131
268 views

### Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
1 vote
2k views

### Averege time complexity of open addressing

I get that it depends from the number of probes, so by how many times the hash code has to be recalculeted, and that in the best case there will only be one computation of the hash code and the ...
• 115
1 vote
49 views

### Where does 2^32 come from with bitcoin?

Several months ago I was doing research into calculating mining revenue for several crypto currencies. When trying to calculate BTC revenue I found this value 1/2^32 which was described somewhere ...
• 51
59 views

### How do these Crypto terms relate to each other and what do they all mean?

Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and ...
• 51
70 views

### What happens in the event of a collision in a crypto hash function?

I was reading about hash functions in crypto and a website had mentioned that they were collision free, which obviously isn't possible if there are infinite input values that are mapped to outputs of ...
• 51
1 vote
23 views

### Algorithm Complexity Question

this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can. I was doing some ...
• 51
1 vote
57 views

### Locality Sensitive Hashing for Sets

Are there locality sensitive hashes that work nicely with sets? Each set would get a hash, the order of the elements in the set does not change the hash, and sets that share more elements are closer ...
102 views

### Splitting the output of a wide hash in lieu of multiple independent hashes

Certain algorithms require two independent hash functions. An optimization I've seen is to split the output of a wide hash function and use the parts instead of the two independent hash functions of ...
1 vote
625 views

### Optimal parameters for a Bloom filter

My first question here. Please do not judge me much if this is a too simple. Some text consists of $n=12\,500$ distinct words. I would like to construct a Bloom filter with $\epsilon=10^{-2}$ ...
• 125
45 views

### Confused about the appropriate slot in linear probing

The following paragraph is from the book CLRS: Given an ordinary hash function $h' : U \rightarrow \{0, 1, ..., m - 1\}$, which we refer to as an auxiliary hash function, the method of linear probing ...
• 411
1 vote
45 views

### Fingerprint functions for set equality checks?

Given I have two sets of objects $A =\{a, b, c\}$ and $B = \{a, b, c, a\}$ Based on the set equality, I want the fingerprint of these sets to be the same $F(A) = F(B)$. Additionally I want to be able ...
• 123
180 views

### Analysis of a calculation of expected number of collisions in hashing

For a formal problem statement, I quote from the text Introduction to Algorithms by Cormen et. al Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. ...
• 1,152
Problem: Let $U = \{0,1,2,3,4,5\}$ be a universe of keys and $T = \{0,1,2\}$ we observe follwing 5 hash functions which map from $U$ to $T$ : h_1(x) = (x+1) \mod{3} \hspace{5mm} h_2(x) = (x+2) \mod{...