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

3
votes
1answer
24 views

Choosing a non-cryptographic hash function for language with no unsigned integers

I'm implementing a hash table in pure UnrealScript, which only has support for signed 32-bit integers. This means no 64-bit integers and no unsigned integers. I was in the middle of implementing an ...
0
votes
0answers
27 views

Linear hashing vs extendable hashing - memory

could you give me an example when linear hashing costs more memory than extendable hashing? And the other side, when extendable hashing takes more memory than linear hashing?
2
votes
0answers
14 views

Constraint on Universal set of hash functions

I was reading hashing from CLRS. In it author says: Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a ...
0
votes
0answers
24 views

How to ensure that no manipulation to data records has been made

Let's say I have a transaction history, like this: Transaction #1: Add 5 Transaction #2: Add 8 Transaction #3: Remove 2 Transaction #4: Cancel Transaction #2 Is ...
0
votes
2answers
49 views

What Exactly Does the Term “Key” Mean with Regards to a Hash Table?

I know it is supposed to be some arbitrary term that is a stand-in for a large class of possible objects. But I still don't understand what part of the array the term "key" is meant to represent or ...
0
votes
0answers
15 views

Locality sensitive hashing (LSH) for media files

I'm trying to implement a general memoizator for media files (audio, images and video), where given an expensive function f, we compute it for some input only if f was not already been computed for ...
4
votes
0answers
38 views

Mean and variance of number of buckets of length $i$ in hashing with chaining

Consider a hash table with $m$ buckets, with chaining as collision resolution policy. Given the set $S$ that will be stored in the hash table, let $X_i$ be the number of buckets whose chain length is $...
2
votes
1answer
52 views

Hash function which is invariant under small changes

I am looking for a hash function which is invariant under small changes. E.g., if I have two strings MyString and MySttring ...
1
vote
1answer
37 views

Is this some kind of hashing?

Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d \}...
2
votes
2answers
47 views

Simple pseudorandom split of data

I want to split my data into $n$ approximately equal parts. Which simple hash functions will ensure that the number of $x$ with $h(x)\equiv i\pmod{n}$ is approximately equal for each $i$?
6
votes
1answer
79 views

Two definitions of universal hash functions

I have seen two definitions of universal hash functions in the literature. For any $i \geqslant 2$ let $[i]=\{1,\ldots,i\}$. Definition 1: A family $\mathcal H$ of hash functions from $[n]$ ...
2
votes
1answer
53 views

Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?

One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 ...
1
vote
1answer
49 views

Different probabilistic statement for Simple Uniform Hashing

Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them ...
2
votes
3answers
70 views

What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n_j = T[j]$ be the size of the ...
5
votes
3answers
233 views

Building static hash table with particular collisions

Is there efficient algorithm to encode keys in hash function with provided collisions? By efficient I mean with low-ish runtime of lookup operation (taking constants into account) and realistic time ...
3
votes
1answer
31 views

Understanding Murmur3

The Bloom filter data structure requires a set of hashing functions. The Murmur3 family is a great fit, as it contains the seed parameter to easily create a variety ...
10
votes
3answers
1k views

Why is a (collision-less) hashtable lookup really O(1)?

Disclaimer: I know there are similar sounding questions already here and on Stackoverflow. But they are all about collisions, which is not what I am asking for. My question is: why is collision-less ...
7
votes
3answers
295 views

1-to-1 cryptographically secure bit shuffling

Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes). The function should have the following qualities: It should be 1-to-1 so that all inputs ...
6
votes
2answers
29 views

Is the following intuition valid for understanding $k$-wise independent hash functions?

I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on $k$-wise independent families of hash functions. I'm perfectly comfortable ...
0
votes
0answers
43 views

What is the difference between O(n^2) and O(N)[N*O(1)]?

I was reading this article on gperf. In it they claim that the use of nested if statements for parsing command line input of $N$ options ends up making $O(N^2)$ ...
0
votes
0answers
72 views

Hash Table: How to Calculate Max Load of a Bucket in Practice

My question is related to this question I posted in math forum: http://math.stackexchange.com/questions/1512644/balls-and-bins-hash-table-a-concrete-example but I could not get an answer that I need....
1
vote
4answers
109 views

General theory on Hash Functions?

I'm a computer engineer and I've met hash functions theoretically speaking in "algorithms and data structure" and then in several applications (like databases, operating systems, computer architecture ...
3
votes
1answer
169 views

Hash-Table in Practice

I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n }{d}$, where $k$ is the number ...
0
votes
0answers
44 views

How to design Hash Functions for the problem of Set Intersection?

This is a specific question about [1]. Before the question, I must explain and organize some topics: 1) In section 3.2, during the "Pre-processing Stage", a hash function maps an element to a bit-...
2
votes
2answers
167 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 ...
2
votes
1answer
86 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
95 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
21 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
85 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 ...
6
votes
1answer
140 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
66 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 ...
2
votes
0answers
89 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 ...
7
votes
1answer
175 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 $...
4
votes
1answer
242 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
38 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
83 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
48 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
87 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 ...
4
votes
3answers
544 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 ...
3
votes
1answer
61 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 ...
5
votes
0answers
233 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 ...
1
vote
2answers
525 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
1answer
73 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
46 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 ...
2
votes
1answer
77 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 ...
3
votes
1answer
159 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
130 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 ...
2
votes
1answer
46 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, ...
1
vote
1answer
2k 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?