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
105 views

Why does this particular hashCode function help decrease collisions?

I just read in Effective Java about the hashCode method: Store some constant nonzero value, say, 17, in an int variable called result. For each significant ...
1
vote
1answer
37 views

Collisions in independent hashing

Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?
3
votes
1answer
46 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$. ...
1
vote
0answers
18 views

Prior papers on hash walks [closed]

Random walks are well known from probability theory. I have the idea for hash walks. If h(x) is a hash function and a,b,c,d,e,f is a boolean sequence then the sort of hash walk I am talking about is ...
1
vote
1answer
32 views

How would you implement truly random hash functions in practice?

Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$. A hash function $h:[U]\rightarrow[m]$ is truly random if For any set of ...
4
votes
1answer
53 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 ...
0
votes
0answers
43 views

How does hashing achieve sketching?

Given a sequence $x \in \{ 1,2,3...,\vert \Sigma \vert \}^*$ one wants to create a sketch of it say $s(x)$ of size $\frac{2c}{3}k (ln^2 k)$ bits. And that seems to be achieved as follows, pick at ...
2
votes
2answers
66 views

About a particular use of hashing [closed]

Look at the last problem on page 2 here, http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf All one wants to do is to convert a $x \in \{ 0,1\}^n$ into a $y \in \{0,1\}^k$ . Then just a ...
1
vote
0answers
51 views

Why is exact nearest neighbor search hard in high dimensional spaces?

I started research on nearest neighbor search in IR a couple of weeks ago. I am still very new to this field, but what I discovered so far from literature is: 1) For the exact nearest neighbor ...
6
votes
1answer
95 views

Is there a continuous hash?

Questions: Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$? Can we add an efficiently computable closeness predicate which given $h_k(x)$ and ...
3
votes
1answer
61 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, ...
2
votes
1answer
21 views

Stateless pseudorandom/hash algorithm for ℤⁿ → [0,1)

There's a problem which I had on a number of unrelated occasions which I usually work around in some way or another. Deep inside, though, it bothers me that I haven't ever found a “proper” solution to ...
0
votes
1answer
46 views

std::hash and separate chaining

I'm attempting to implement my own generic hash table using separate chaining. I'm using the std::hash() method to create my hash function. I noticed in the description of std::hash() that: For two ...
3
votes
1answer
28 views

What are the examples of the easily computable “wild” permutations?

I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the ...
2
votes
3answers
50 views

Which fingerprinting/hashing algorithms support compounding?

The definition of fingerprinting algorithms in Wikipedia describe a property called compounding as you can see here as: Some fingerprinting algorithms allow the fingerprint of a composite file to ...
3
votes
3answers
339 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 ...
2
votes
1answer
50 views

Linear and almost-linear perfect hashing

I am trying to understand the sentence from a paper by Patrascu: Unfortunately, we do not have linear perfect hashing. Instead, we use a family of hash functions.... with almost-linearity The ...
4
votes
0answers
102 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 ...
0
votes
0answers
16 views

What would be the expected number of clashes if I had a random hash function h to hash n distinct keys in an array T of size m. [duplicate]

I'm learning about hash functions and the way they work. Im not sure how I find the number of crashes. Collisions are solved with chaining and I think the results should be written in Big Oh and ...
1
vote
2answers
148 views

Hash function floating point inputs for genetic algorithm

I am implementing a genetic algorithm to use as an optimisation algorithm to evolve robots. The robots have certain parameters (represented as floats) which can lie anywhere within a certain range ...
0
votes
0answers
22 views

Amplifying a Locality Sensitive Hash

I'm trying to build a cosine locality sensitive hash so I can find candidate similar pairs of items without having to compare every possible pair. I have it basically working, but most of the pairs in ...
0
votes
1answer
24 views

conversion to base-R numbers

I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for ...
1
vote
0answers
26 views

What needs to be done after deleting an item in a hash table built under opening addressing with linear probing

In some textbook problems, the problem asks me to insert a bunch of elements and remove a bunch of elements. Insertion is done using linear probing, i.e. h = XmodR + I, when there is a collision, I ...
1
vote
1answer
40 views

Hash values that are impossible to reach

I was just curious as to if there are (or could by) any hash values that are impossible to compute due to the implementation of the algorithm. For example, SHA-256 produces a value that is 256-bits ...
2
votes
1answer
65 views

How to find a 2-wise independent hash family that is not 3-wise independent?

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 ...
2
votes
1answer
85 views

Show that the following family of hash functions is $2$-wise independent but not $3$-wise independent

I've really been thinking about and working on this problem for a while, and I would appreciate if someone could offer any help towards the solution. Consider the following family of hash ...
0
votes
0answers
21 views

bloom filter in high load/concurrency environment?

"I was asked this question in an interview, How to design a bloom filter to reduce cache access in a high load and concurrency environment. I know how bloom filter works but try to understand how high ...
2
votes
1answer
38 views

Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values?

Modern non-cryptographic 32- and 64-bit valued hash functions, for example, lookup3, MurmurHash3 and CityHash, have quite sophisticated loops, each iteration of which include many multiplications, ...
0
votes
1answer
603 views

Why can the alphabet be represented in numbers in base 256

This is in context of hashing of strings. I'm not sure why a string like, CS, could be represented as CS = 'c'*256 + 's' Does anyone know about this?
1
vote
2answers
91 views

Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad?

I am doing an exercise from a Big Data course I'm taking on Coursera (this exercise is for experimenting with a big-data problem and is not for any credit or homework) , the assignment was described ...
2
votes
2answers
54 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) ...
-2
votes
1answer
48 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
203 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 ...
6
votes
2answers
167 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 ...
3
votes
2answers
165 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
213 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 ...
4
votes
1answer
407 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
190 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
46 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, ...
18
votes
5answers
1k 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
173 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
124 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 ...
2
votes
1answer
46 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
70 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
317 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
63 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
182 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
97 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
1k 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
59 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 ...