# 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

200 questions
110 views

### Hash for verifying both compressed and uncompressed data?

Is it possible to have a single hash function output simultaneously verify a compressed block of data as well as its uncompressed counterpart? Trivially one could just use a hash function twice (once ...
112 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 ...
85 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 ...
25 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 ...
176 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 ...
203 views

65 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$?
166 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]$ to ...
456 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 ...
85 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 ...
302 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 ...
744 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 ...
575 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 ...
2k 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 ...
323 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 ...
137 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 ...
51 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)$ ...
654 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: https://math.stackexchange.com/questions/1512644/balls-and-bins-hash-table-a-concrete-example but I could not get an answer that I ...
795 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 ...
308 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 ...
77 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-...
1k 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 ...
145 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 ?
691 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$. ...
22 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 ...
458 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 ...
250 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 ...
192 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 ...
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 ...