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
votes
1answer
86 views

Find the approximate number of messages (n) that need to be tried

Find the approximate number of messages (n) that need to be tried before finding two that had the same message digest (size k) with probability 0.8. You need to find n as a function of k . What is n ...
1
vote
1answer
1k views

How to explain the steps in the implementation of hashing functions like SHA1

I was reading the article about the SHA1 hashing function (I know it is not secure anymore) and I've found a pseudocode implementation on Wikipedia. I can see that there are a lot of mathematical ...
11
votes
2answers
8k views

Fast hashing: combination of different techniques to identify changes in a file?

I want to create a fast way to detect whether a file might or might not be the same. For almost 100% sureness I would use an existing hash algorithm, e.g. SHA256. However, the files are expected to be ...
0
votes
1answer
501 views

Is there an adjustment for Adler32 algorithm so it works well on short messages?

The Adler32 algorithm has a shortcoming as noted on Wikipedia: Jonathan Stone discovered in 2001 that Adler-32 has a weakness for very short messages. He wrote "Briefly, the problem is that, for ...
3
votes
5answers
238 views

Efficient set data structure supporting insert and set equal

What's the best way to represent sets that support the following two operations: Insert(s, i) - adds nonnegative integer i to set s Equal(s1, s2) - Tests if s1 and s2 are the same set. In addition, ...
2
votes
1answer
54 views

Find $k$ subsets containing a particular element quickly

Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $ (< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers. To that effect, ...
2
votes
0answers
608 views

Distance preserving projection for Euclidean distance

Suppose I have two vectors $V_1, V_2 \in R^l$. Can they be converted into bit vectors $B_1,B_2 \in \{0,1\}^l $ such that if $V_1, V_2$ is close in Euclidean distance, $B_1,B_2$ is close in hamming ...
3
votes
1answer
147 views

Why does appending permutations of servers at the end of hash table avoid bottlenecks?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf The paper has a TLT (tract locator table) for identifying where to write in each ...
3
votes
1answer
67 views

Why does the following function distribute things in a binomial distribution?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf and it says that the the following hash function does not distribute things uniformly ...
1
vote
1answer
150 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
3
votes
1answer
2k views

Why is the initial state of Zobrist hashing random?

When generating a board for Zobrist hashing, why are the initial elements random? How can you detect changes to elements later if the initial values are random?
1
vote
1answer
126 views

Help in understanding exactly how lattices used as one way functions for hashing

(This question is related to homework) I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority ...
0
votes
1answer
2k views

Transform values of hash functions like MD5 into numbers

I have read about the hash function MD5. I found an online calculator which counts the value of MD5 for different data. But the MD5 function returns as result strings like ...
1
vote
2answers
189 views

Hashing a Specific Range Of a Character Array [closed]

I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my ...
7
votes
2answers
6k views

How does taking modulo 1 make sense?

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 ...
1
vote
0answers
70 views

Min/max of hash function (Whirlpool)

The Whirlpool hash function generates a 128-digit hexadecimal number. Could that number ever be ...
2
votes
2answers
425 views

What is Harrison hashing, its applications in web search engines?

What is Harrison hashing and what are its applications in web searching? Can some one give me some relevant information? Update: I found it here , and is a part of M.Tech syllabus of a friend ...
5
votes
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 ...
0
votes
1answer
2k views

Retrieving data from hash table ordered by insertion time

By default, a hash table is unordered. I have a simple question on the retrieval of elements in a hash table Can we retrieve elements from a hash table in the same order as they are put inside?
3
votes
1answer
2k views

Find similar vector by Locality Sensitive Hashing

I have many vectors in my database. They are in high dimensions such as: $v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$ $v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$ ... I will ...
1
vote
1answer
735 views

Double hashing - probe count probabilities

From TAoCP, Vol. 3 by Knuth we know that expected (mean) probe counts for hash tables with open adressing and double hashing collision-resolution are: $1 \over 1 - \alpha$ - for unsuccessful search ${...
-2
votes
1answer
92 views

Complexity of a hash tables with balanced trees in the buckets

If I use a balanced tree instead of lists in a hash table implementation, and also after initializing my table I don't enlarge nor reduce the size of the table, what would be the worst case complexity?...
2
votes
0answers
97 views

Collisions of a compression function

I tried posting this in the math forum but I didn't get any responses. I was hoping someone could give me some advice for how to approach the following problem. If $n$ is a positive integer, let $...
2
votes
1answer
642 views

Proving calculating Minhash

I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h_\min(S)$ is the minimum hash of set S, i.e. $h_\min(S) = \min(h(s))$ for ...
4
votes
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. ...
2
votes
1answer
3k views

How to get expected running time of hash table?

If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
2
votes
1answer
1k views

Hash function - uniformity / strong universality

I am currently learning how randomised Hashing works. So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$. That class is called "...
9
votes
1answer
395 views

Attack on hash functions that do not satisfy the one-way property

I am revising for a computer security course and I am stuck on one of the past questions. Here is it: Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S_{ab}$ to ...
14
votes
2answers
200 views

Function that spreads input

I'd like to know if there is a function $f$ from n-bit numbers to n-bit numbers that has the following characteristics: $f$ should be bijective Both $f$ and $f^{-1}$ should be calculable pretty fast $...
2
votes
2answers
748 views

Collision resistant hash function

A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$. ...
2
votes
1answer
443 views

Modulo hash function and multiples of three

This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$. The explanation given is: ...
6
votes
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 ...
6
votes
5answers
449 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, ...
2
votes
1answer
312 views

How do the following Hash Functions compare?

Consider the two hash functions used to map IP addresses. $x_i$ represents a octave (or "bit field") of the address. Hash Function 1: $$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} a_ix_i \bmod n$$ ...
1
vote
2answers
760 views

Collisions of prefixes of MD5 hashes in some fixed interval

I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer ...
3
votes
0answers
112 views

Algorithm that hashes a collection of sets following their disjointness relation

I wonder whether there is a simple algorithm to do this work: Say I have a collection of objects $C$, and a binary relation $R: C\times C$ that is auto-reflective ($\forall c\in C: c R c$) , and ...
5
votes
1answer
309 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 ...
1
vote
1answer
162 views

Is open adressing with prime steps bijective?

Who can help me with this topic: Probing with a step width that is a prime number. I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of ...
18
votes
2answers
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 ...

1 2 3 4 5
6