People who code: we want your input. Take the Survey

# 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

272 questions
Filter by
Sorted by
Tagged with
1answer
72 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
453 views

### How to get all in constant time?

We are planning to design a system where following operations are supported. ...
1answer
72 views

### Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p

Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely. Could you explain ...
3answers
123 views

### Is the capacity of a hash table a constant value?

In this paper, page 4, it is said: "...there is always a constant expected number of elements that map to the same slot" Assume we have a set $S$ of $n$ values, and we want to insert them into a ...
1answer
152 views

### Clarification reg. jump consistent hashing

I was reading the paper on Jump consistent hashing, and I'm having some trouble understanding one particular line (page 5, paragraph 2) "Since we want P(j ≥ i) = (b+1) / i, we set P(j ≥ i) iff r ≤ (b+...
1answer
222 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$ ...
0answers
234 views

### Is this PJW hash function incorrect?

I came across this implementation of PJW and it seems incorrect: ...
1answer
78 views

### Bounds on probe lengths and number of rehashes with universal hashing

Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $x\neq y$ are mapped to the same hash-value is bounded by $k/m$ when I have $m$ bins and ...
0answers
111 views

### Approximate dot product between neural network output layer's parameter vector and input activations with winner-take-all hashing

In the paper Deep Networks with Large Output Spaces, Vijayanarasimhan et al. describe their approach to approximating the dot product between a neural network's output layer's parameter vector and ...
2answers
710 views

### Perfect (or almost perfect) Hash function for n bit integers with exactly k bits set

I have a a data set with 2598960 elements of of unsigned integers of (at most) 52-bit length. The data set has a property that exactly 5 bits set. This is only 1 data sets – I have similar data sets ...
1answer
11 views

### Method for eliminating spent hashes from a large collection?

Consider a DB with a large set of numbers, like hashcash tokens, where new numbers are constantly added(spent). Only numbers that has not been already added can be accepted. Is there a functional way ...
0answers
358 views

### Proving a hash function family is weakly universal

$H$ is a family of weakly universal hash functions if for two elements $x,y$: $$P(h(x) = h(y)) \le \frac1m,$$ where $m$ is the size of the domain, and $h$ is chosen at random from $H$. Given a hash ...
1answer
57 views

### Can anyone find a mapping from the set of all possible string to the natural numbers?

Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$? $$h : S^* \rightarrow \mathbb{N}$$ Assume $S$ is finite. I would prefer an ...
1answer
28 views

### Bloom Filter which does not fit in RAM [closed]

Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?
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 ...
1answer
940 views

### How to actually implement universal hashing?

I sort of get what it is, but I don't understand how its actually supposed to be used in algorithms. Suppose the hash function is $h_{ab}(x) = ((ax+b) \mod p ) \mod m$ where $a$ not equal to 0. If I ...
1answer
105 views

### Avoiding correlated values and reduced collision resistance in multiple hash states

I need to design a hash function that fits this criteria: Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system) Produces an n-bit hash digest, ...
0answers
221 views

### Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree. With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
0answers
806 views

### Why is the module of the second function in double hashing a prime number?

When using double hashing, the second hash function is defined as $$h_2(x)=A-x\mod A,$$ where $A$ is a prime number less than the capacity of the hash table. But why must $A$ be a prime number? (This ...
1answer
282 views

### Will Java's hashCode() reduce collisions regardless of table size?

for a class project we have to count the number of collisions from inserting words from a plaintext document into a hashtable. I read that using prime numbers for table sizes can offset the collisions ...
0answers
29 views

### Is it possible to retrive the Hash from an encrypted folder?

So first of all I've a software which basically locks/encrypts a folder with a given password. Afterwards it's almost impossible to open the folder without entering the password through the software. ...
1answer
137 views

### Surprisingly high collision rates when hashing a short list with few buckets

I'm trying to help my daughter with her CS assignment on hashing. She has an input list of about 4000 English words, each 5 letters long. The prof has limited her to 4000 output buckets (digests? -- ...
1answer
26 views

### Function to generate longer bit-sequence from shorter sequence with certain properties

im not familiar with the terminology of computer-science which makes it pretty difficult to search for the problem I have. I'm looking for a function that generates a sequence of bits (B) of a given ...
1answer
246 views

### Deterministic algorithm to find number of collisions

Let $h:U \to[m]=\{0,1,\dots,m\}$ be hash function, which can calculate $h(u), \forall u\in U$ in $O(1).$ Let $D \subseteq U$ be a subset of size $n.$ I'm looking for a deterministic algorithm, ...
1answer
48 views

### Computing 'score' of string which preserves < relation

Is there a way to calculate some kind of numerical 'score' for arbitrary strings which when compared with score of some other string will preserve '<' relation? I've searched for order preserving ...
1answer
512 views

### Can Double Hashing return the same value 2 times?

$h(i,k)=(h^{}_{1}(k)+i * h^{}_{2}(k)) mod |T|$ as it defined in wikipedia I would like to know if it possible that Double Hashing return the same value for given $k$ when $i=1$ and $i=2$. Or from ...
1answer
52 views

### Is there a heuristic or function to determine if two arrays of integers are alike or similar

What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say a = [0, 1, 2, 3, 4], <...
0answers
55 views

### Double Hashing Collision

Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) mentioned that we can use $g_i(x) = (h_1 (x)+ih_2 (x))\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two ...
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 ...
2answers
1k views

### Probability of hash collision in the case of two parallel hashes

I understand how to calculate the probability of a hash collision. I am designing a DB and have a potential case where a record could have the inherited hash of its parent plus its own hash, meaning I ...
0answers
150 views

### why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states Let H be class of hash ...
1answer
12k views

### Explain Hashed page tables in operating system

I have a difficult time understanding hashed page tables used in virtual memory management. Here is picture of the slide that I am referring to: I understand that p is hashed and then the hash is ...
1answer
100 views

### Is a powerful two-way hash function provably impossible?

A two-way hash function that could hash complex strings to a fixed length would change the world. Imagine the decreased load on wires around the world if, for example, HTML pages could be hashed, ...
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 ...
0answers
110 views

### Bloom filters vs storing hashes as numbers

In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
1answer
53 views

### Problem about getting a value of the hashed password [closed]

Given a database with usernames and the first six bytes of their hashed passwords. A standard hashing function has been used for hashing. admin 827ccb0eea8a user c3981fa8d26e operator 5f4dcc3b5aa7 ...
1answer
224 views

### range / interval query algorithm

I've an hash (base 32 for what it's worth): hash = 'ab352eghjhngd4' And I've subscribers that want to listen to new hashes in a range. ...
1answer
705 views

### Knuth's proof of O(1) for linear probing

I'm currently reading Knuth's proof about O(1) number of probes in linear probing. I have a small question on the page 536 (Volume 3, 2nd Edition). Knuth says Let $f(M, N)$ be the number of hash ...
1answer
498 views

### Universal family of hash functions

How to prove that a $k$-universal family of hash functions is $(k-1)$-universal family? I tried to prove it by definition of k-universal family of hash functions but I didn't know how to use the ...
0answers
88 views

### Existence of perfect hash function

In their original paper, Storing a sparse table with O(1) worst case access time (Fredman, Kolmos and Szemeredi, Proc. FOCS '82, IEEE, 1982), the authors show that a perfect hash function must exist, ...
1answer
473 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 ...
2answers
98 views

### Are there any hash functions/stateless RNGs that do not use XOR, but produce good quality visual randomness?

I'm looking for a small function from integers to integers - in a language that only has floats - that can act as a visual RNG. Normally I would use a function such as the one described here: ...
1answer
231 views

### “Hash” Probing?

While there are many types of probing in hash tables, such as linear probing, quadratic probing, and more, I haven't encountered a so-called "hash-probing" (maybe this method which I describe below ...
2answers
152 views

### Does this problem offer any insight into $P$ vs $NP$

What is the input of a given hash? The problem can be verified in polynomial time (using a hash that executed in polynomial time), and I suspect that it may be possible to prove that there is ...
2answers
433 views

### What is the reasoning behind magic constancs in hash code calculations found in programming practice?

In real-world programming, we frequently need to compute hash codes for complicated objects. The main desired properties are that the values should be deterministic and have few collisions. Let's ...
0answers
28 views

### Hash function for searching, is that feasible?

I have a set of sorted values $\left\{a_j \right\}_{1 \leq j \leq n}$, suppose now a number $x$ is given and we would like to find out the index $j$ such that $a_j \leq x < a_{j+1}$ (you can assume ...
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 <...
1answer
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. ...
0answers
38 views

### Altering the size of a Hash

Does removing the leading(or trailing) n bits of any given hash have any negative effects other then increasing the likeliness of collisions? Does appending 2 hashes of the same object with different ...
1answer
84 views

### What hash algorithm is it?

I've found a simple multiply-with-add hash function in an old Usenet post. Can someone identify what hash algorithm is it? An algorithm name or any attribution? ...