# 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

273 questions
Filter by
Sorted by
Tagged with
68k views

### Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$H = k \bmod \ 11$$ Now all the values will be placed ...
3k views

### Is there an anti-Bloom filter?

A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in ...
6k views

### Could quantum computing eventually be used to make modern day hashing trivial to break?

Simply put, if one were to build a quantum computing device with the power of, say, 20 qubits, could such a computer be used to make any kind of modern hashing algorithm useless? Would it even be ...
200 views

697 views

### How to avoid cascading resizes when resizing hash tables?

With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability ...
1k views

### Bloom filter and perfect hashing

A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position. To mitigate the effect of hash collision, multiple ...
332 views

### 1-to-1 cryptographically secure bit shuffling

Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes). The function should have the following qualities: It should be 1-to-1 so that all inputs ...
315 views

### Is it known whether the MD5 algorithm is surjective?

Does MD5 map to all possible 128 bit numbers? To put it another way: For every 128 bit number y, does there exist at least one x ...
398 views

### Can proofs-of-work be probabilistically checkable?

I have been lurking for a while; this is my first post here. I’m sorry if my question is ill-formed or formatted poorly. This question came out of some ideas in another question from a sister site. ...
224 views

### Most space-efficient lossy dictionary?

Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)? Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
862 views

### Double Hashing and Variations for Bloom Filters

I am reading a few papers on Bloom Filters – Bloom Filters in Probabilistic Verification (Dillinger and Manolios) suggests the following allocations for double and triple hashing respectively ...
433 views

### Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?

From Wikipedia A hash function is any algorithm or subroutine that maps large data sets of variable length, called keys, to smaller data sets of a fixed length. For example, a person's name, ...
5k views

I need some help understanding the problem statement in CLRS 11.3-4 pg 269. It says: Consider a hash table of size $m = 1000$ and a corresponding hash function $h(k) =\left \lfloor m(kA \bmod ... 2answers 193 views ### Is the following intuition valid for understanding$k$-wise independent hash functions? I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on$k$-wise independent families of hash functions. I'm perfectly comfortable ... 1answer 1k views ### Why does the Count-Min Sketch require pairwise independent hash functions? The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each ... 1answer 477 views ### How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work? Given a hash function$H:\{0,1\}^*\rightarrow\{0,1\}^n$, a difficulty$d\in\mathbb{N}$, and data$D\in\{0,1\}^*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce$c$such ... 1answer 219 views ### Two definitions of universal hash functions I have seen two definitions of universal hash functions in the literature. For any$i \geqslant 2$let$[i]=\{1,\ldots,i\}$. Definition 1: A family$\mathcal H$of hash functions from$[n]$to ... 1answer 3k views ### Find longest common substring using a rolling hash The longest common substring (LCS) of two input strings$s,t$is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring ... 2answers 2k views ### Hash size: Are prime numbers “near” powers of two a poor choice for the modulus? Cormen et al.'s "Introduction to Algorithms" says the following about the division method hash function$h(k)=k \text{ mod } m$: A prime not too close to an exact power of 2 is often a good choice ... 3answers 2k views ### What is the point in hashing a value? I apologise if this is not the right place for this question... I didn't want to ask on Stackoverflow or CodeReview as it will closed in minutes as "too broad". A client of mine is writing an API ... 2answers 5k views ### why not just use a random number generator as a hash function? I guess at the heart of this is that I don't really understand hash functions. One article says any function mapping objects to an object of fixed size: A hash function usually means a function ... 3answers 2k views ### How should I design a hash table where all the keys are permutations? I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys. Given that I know how all the keys look ... 4answers 225 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 ... 2answers 3k views ### Why is Big O not defined here for a hash table? In this cheat sheet, average time complexity for access to a hash table is listed as N/A. I'm curious as to why. Since a hash table is mostly mathematical, I would assume it would be O(1) like the ... 3answers 862 views ### Building static hash table with particular collisions Is there efficient algorithm to encode keys in hash function with provided collisions? By efficient I mean with low-ish runtime of lookup operation (taking constants into account) and realistic time ... 1answer 555 views ### What is an example of a weakly universal hash function that is not pairwise independent? A family of hash functions$H_w$is said to be weakly universal if for all$x \ne y$: $$P_{h \in H_w}(h(x) = h(y)) \leq 1/m$$ Here the function$h:U \rightarrow [m]$is chosen uniformly from the ... 1answer 2k views ### What exactly is a hash function? I have no idea how I managed to get this far in life without ever really grasping this but as it happens I'm still very confused on the concept of a hash function. I did some googling/wikipedia-ing, ... 1answer 303 views ### A hash function with predicted collisions As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides ... 1answer 482 views ### Fixed point of hash Are hashing algorithms constructed to guarantee that no fixed point exists? My assumption is not, because I don’t see what utility that would have. (Please correct me if I’m wrong.) As such, purely ... 1answer 373 views ### Hash-Table in Practice I have a set of$n$values,$v_i$and want to insert them into a hash-table,$HT$, in a way that each bucket (or hash-table cell) has at most$d$values. I set$k=\frac{n }{d}$, where$k$is the number ... 2answers 615 views ### Understanding of hash tables I am currently studying hash tables in an introductory course to computer science. I was taught that hash table is a data structure that associates a key to an index (a hash table) and then to the ... 3answers 89 views ### Integer set disjointness query on sketches with something like homomorphic hashing Suppose I have two sets of integers$A$and$B$and I have a sketch data structure described by a function$\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$that returns a bitstring of size$n$. ... 1answer 2k views ### Finding hash of a substring$[i, j]$in$O(1)$using$O(|S|)$pre computation Given a string$S$of length$n$characters, is it possible to calculate the hash of its substring$[i, j]$(from index$i$to$j$, both inclusive) in$O(1)$using some form of precomputation? Can we ... 1answer 146 views ### Count Sketch probability bound I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ... 1answer 1k views ### How can one find an element in a Merkle tree? How can one find an element in a Merkle tree, as effectively as possible? Each internal node has a hash value. So I think, first, hash the value to find, and if an internal node has the same value ... 1answer 169 views ### Indexing Edge Permutations for the Rubik's Cube I'm working on a Rubik's Cube solver that implements Korf's algorithm, as published in his 1997 paper, Finding Optimal Solutions to Rubik's Cube Using Pattern Databases. His method involves creating ... 1answer 96 views ### Reversible Merge of Integer Hash Values Context: I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's ... 1answer 233 views ### Hash for verifying both compressed and uncompressed data? Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart? Trivially one could just use a hash function twice (once ... 1answer 959 views ### Finding similar high dimensional real vectors I have a collection of vectors$v_1,v_2\in [0,1]^n$and I want to find similar pairs quickly. For similarity, I want to use the Euclidean distance metric$L: [0,1]^n \times [0,1]^n \longrightarrow R$. ... 1answer 660 views ### Hashing algorithm for millions of variable length strings (URLs) The goal is to distribute approximately 100 million variable length strings, average length 100 characters, uniformly among 100 million buckets. Perfection not required, just no egregious clumping. ... 1answer 78 views ### Prove the probability of which a hash function is collision-free Suppose$H = \{h_1, ..., h_T\}$be a family of pairwise independent hash functions mapping$\{0, 1\}^n$to$\{0, 1\}^{n/2}$. Let$M = \frac{2^{n/4}}{10}$and let$x_1, ..., x_M$be any M distinct ... 1answer 499 views ### What is the complexity class of solving hash decision problems? With$hash_n$, I mean a standard cryptographic hash like sha256, scaled up to have arbitrary length$n$of its output with the same underlying principles. What is the time complexity class of the ... 0answers 369 views ### Mean and variance of number of buckets of length$i$in hashing with chaining Consider a hash table with$m$buckets, with chaining as collision resolution policy. Given the set$S$that will be stored in the hash table, let$X_i$be the number of buckets whose chain length is$...
I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that? I know two 2-wise independent ...