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

learn more… | top users | synonyms

2
votes
2answers
43 views

Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) ...
-1
votes
0answers
12 views

What is GeForce GT755m SLI good for? Bitcoin minnig? rendering? [closed]

I bought the Y510P gt755m SLI notebook PC. Now I see that working with a single graphics card or both, I don't see much difference in a games' frame rate, witch means that having to GPU for gaming is ...
-2
votes
1answer
22 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 ...
0
votes
1answer
35 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 ...
5
votes
2answers
93 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 ...
1
vote
1answer
102 views

Term for binary search tree using hashes?

I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, ...
1
vote
1answer
50 views

Finding Hash of 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 index j. Inclusive) in O(1) using some form of precomputation ? Maybe a ...
2
votes
1answer
96 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 ...
3
votes
5answers
156 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 ...
2
votes
1answer
36 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, ...
17
votes
4answers
932 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 ...
2
votes
0answers
54 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 ...
4
votes
1answer
104 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
34 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 ...
0
votes
1answer
46 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
106 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
53 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 ...
2
votes
1answer
90 views

Sequential numbers to unique-looking numbers

I'm not sure how to word this because I'm not familiar with this, but I'm sure a process like this is rather common. Basically, I've got members signing up for our website, and each one is assigned a ...
0
votes
1answer
63 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 ...
6
votes
2answers
442 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 ...
1
vote
2answers
48 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 ...
4
votes
2answers
132 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 ...
0
votes
1answer
65 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 ...
6
votes
1answer
154 views

Universal Hashing in Practice

A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if $$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$ You can find more about ...
1
vote
0answers
29 views

Min/max of hash function (Whirlpool)

The Whirlpool hash function generates a 128-digit hexadecimal number. Could that number ever be ...
3
votes
2answers
244 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 ...
1
vote
1answer
143 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 ...
1
vote
1answer
218 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 ...
0
votes
1answer
872 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?
-2
votes
1answer
64 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 ...
5
votes
1answer
227 views

Bloom filter and perfect hashing

Bloom filter use a hash function to test membership for S by checking if an item is present of not at the specified position. To mitigate the effect of hash collision, multiple functions are used, ...
2
votes
2answers
89 views

Are those definitions of universal hash family equivalent?

I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is. Definition 1: $H$ is a universal ...
2
votes
0answers
68 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
128 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 ...
10
votes
3answers
3k 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 ...
3
votes
1answer
135 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. ...
1
vote
1answer
454 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
144 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 ...
2
votes
2answers
224 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 ...
2
votes
2answers
445 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$. ...
5
votes
1answer
513 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
155 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, ...
12
votes
2answers
154 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
1answer
148 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$$ ...
2
votes
1answer
162 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: ...
1
vote
2answers
187 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
102 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
183 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 ...
10
votes
1answer
345 views

Weak hashing function for memorable IPv6 addresses

IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4. There have been ...
1
vote
1answer
121 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 ...