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

Filter by
Sorted by
Tagged with
1
vote
2answers
50 views

Why can't hash coding be reversed?

Why is it impossible to reverse a hash code? There could be some way to crack this coding?
1
vote
1answer
531 views

Can we do 4-sum algorithm in O(n^2)?

this is related to the following question: Generalised 3SUM (k-SUM) problem? Without loss of generality, let's only consider even $k$, or just $k=4$. My question is, after summing all pairs of ...
0
votes
1answer
62 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 ...
0
votes
1answer
310 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
0
votes
1answer
54 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 ...
1
vote
3answers
87 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 ...
2
votes
1answer
107 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+...
6
votes
1answer
178 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$ ...
0
votes
0answers
135 views

Is this PJW hash function incorrect?

I came across this implementation of PJW and it seems incorrect: ...
3
votes
1answer
59 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 ...
2
votes
0answers
84 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 ...
-1
votes
2answers
496 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 ...
0
votes
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 ...
0
votes
0answers
226 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$. ...
0
votes
1answer
52 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 ...
0
votes
1answer
26 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?
0
votes
0answers
1k 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 ...
0
votes
1answer
552 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 ...
2
votes
1answer
59 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, ...
3
votes
0answers
128 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 ...
0
votes
0answers
426 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 ...
0
votes
1answer
157 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 ...
0
votes
0answers
28 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. ...
2
votes
1answer
104 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? -- ...
0
votes
1answer
25 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 ...
1
vote
1answer
68 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, ...
1
vote
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 ...
0
votes
1answer
384 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 ...
2
votes
1answer
39 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], <...
1
vote
0answers
44 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 ...
5
votes
2answers
1k views

Hash size: do prime numbers “near” powers of two are bad?

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 ...
0
votes
2answers
739 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 ...
1
vote
0answers
63 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 ...
1
vote
1answer
9k 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 ...
-2
votes
1answer
91 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, ...
5
votes
2answers
2k 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 ...
1
vote
0answers
99 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)...
1
vote
1answer
52 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 ...
2
votes
1answer
174 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. ...
3
votes
1answer
600 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 ...
2
votes
1answer
355 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 ...
0
votes
0answers
85 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, ...
6
votes
1answer
374 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 ...
1
vote
2answers
83 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: ...
2
votes
1answer
187 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 ...
-1
votes
2answers
130 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 ...
3
votes
2answers
266 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 ...
0
votes
0answers
27 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 ...
1
vote
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 <...
7
votes
1answer
358 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. ...