Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

5
votes
1answer
126 views

Most space-efficient lossy dictionary?

Short version: What is the most space-efficient lossy dictionary (with given false positive and false negative rates)? Long version: A lossy dictionary is a data structure $D$ that encodes a set $S$ ...
4
votes
1answer
352 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 ...
3
votes
1answer
40 views

Bounds on probe lengths and number of rehashes with universal hashing

Say I have a family of hash functions that are weakly universal, i.e. the probability of two non-identical keys $x\neq y$ are mapped to the same hash-value is bounded by $k/m$ when I have $m$ bins and ...
2
votes
1answer
22 views

The expectation of the total number of pairs of keys in a hash table that collide using universal hashing

I am reading CLRS relating to perfect hashing. When computing the $$ \mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}] $$ where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
0
votes
1answer
39 views

Hash function orders ships from closest to furthest from the origin

Suppose we have a circular radar that scans for ships in an area enclosed by $x^2+y^2 \leq z^2$ (a circle). We wish to design a hash function $h$ such that, we can order the $n$ ships from closest to ...
0
votes
1answer
146 views

How to get all in constant time?

We are planning to design a system where following operations are supported. ...
6
votes
0answers
632 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 ...
5
votes
0answers
203 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 $...
4
votes
0answers
70 views

Is it possible to compute an equality hash for nodes in a *cyclic* directed graph in less than quadratic time?

Calculating hashes for nodes in an acyclic graph is well known using a Merkle tree. With some simplifying assumptions, a simple algorithm will also calculate hashes for nodes in a cyclic graph... but ...
3
votes
0answers
34 views

Altering the size of a Hash

Does removing the leading(or trailing) n bits of any given hash have any negative effects other then increasing the likeliness of collisions? Does appending 2 hashes of the same object with different ...
3
votes
0answers
425 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 ...
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 ...
2
votes
0answers
64 views

Approximate dot product between neural network output layer's parameter vector and input activations with winner-take-all hashing

In the paper Deep Networks with Large Output Spaces, Vijayanarasimhan et al. describe their approach to approximating the dot product between a neural network's output layer's parameter vector and ...
2
votes
0answers
554 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 ...
2
votes
0answers
93 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 $...
1
vote
0answers
21 views

What's the problem with deletion in FKS perfect hashing?

In FKS perfect hashing we construct two levels of tables. To lookup an element we first check in the first table which points us to the correct second level table that will contain the element if it ...
1
vote
0answers
39 views

Double Hashing Collision

Less Hashing Same Performance: Building A Better Bloom Filter (Kirsch and Mitzenmacher) mentioned that we can use $ g_i(x) = (h_1 (x)+ih_2 (x))\pmod{p}$, where $h_1(x)$ and $h_2(x)$ are two ...
1
vote
0answers
40 views

why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

I am self-studying the book Intro to Algorithms 3ed by CLRS. One of the problems seems to give a piece of information that is not necessary, Problem 11-4 in the book states Let H be class of hash ...
1
vote
0answers
88 views

Bloom filters vs storing hashes as numbers

In competitive programming there is a trick for storing a set of strings(or objects really) to reduce memory - you only keep the hashes of the strings in a hash-table (usually as 32 or 64 bit integers)...
1
vote
0answers
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)$ ...
1
vote
0answers
111 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
0answers
66 views

Min/max of hash function (Whirlpool)

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

Search operation in hash table

Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining. Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and ...
0
votes
0answers
24 views

What is a minimal, pseudo-random hash function?

I want to generate pseudo-random hashes of inputs in a way that is optimally time and space efficient. I'm not at all concerned about security. The output should be evenly distributed and appear ...
0
votes
0answers
17 views

Adaptive radix tree for storing Hash vs HAMT

Is there any disadvantage to using Adaptive radix tree to store hash of key like it is done in HAMT and Ctrie Would it be slower? Would it use more memory?
0
votes
0answers
57 views

Is this PJW hash function incorrect?

I came across this implementation of PJW and it seems incorrect: ...
0
votes
0answers
18 views

Can I uses with same hashing-function for two hash-tables?

Given 2 hash tables , can I use only one hashing function for the two hash tables? I don't sure if the size of the hash-tables is necessarily affect about the hashing-function that this hash-table ...
0
votes
0answers
141 views

Proving a hash function family is weakly universal

$H$ is a family of weakly universal hash functions if for two elements $x,y$: $$ P(h(x) = h(y)) \le \frac1m, $$ where $m$ is the size of the domain, and $h$ is chosen at random from $H$. ...
0
votes
0answers
189 views

Average number of comparisons for hash/rehash operations

I have the below problem, which I've already been given the answer to, I'm just trying to understand why the answer is the way it is. I've modified the language of the problem significantly so it ...
0
votes
0answers
682 views

Rolling Hash calculation with Horner's method

I understood how Horner's method reduces the complexity(number of operations) while evaluating a polynomial. I have a character array derived from a string ...
0
votes
0answers
256 views

Why is the module of the second function in double hashing a prime number?

When using double hashing, the second hash function is defined as $$h_2(x)=A-x\mod A,$$ where $A$ is a prime number less than the capacity of the hash table. But why must $A$ be a prime number? (This ...
0
votes
0answers
26 views

Is it possible to retrive the Hash from an encrypted folder?

So first of all I've a software which basically locks/encrypts a folder with a given password. Afterwards it's almost impossible to open the folder without entering the password through the software. ...
0
votes
0answers
78 views

Existence of perfect hash function

In their original paper, Storing a sparse table with O(1) worst case access time (Fredman, Kolmos and Szemeredi, Proc. FOCS '82, IEEE, 1982), the authors show that a perfect hash function must exist, ...
0
votes
0answers
27 views

Hash function for searching, is that feasible?

I have a set of sorted values $\left\{a_j \right\}_{1 \leq j \leq n}$, suppose now a number $x$ is given and we would like to find out the index $j$ such that $a_j \leq x < a_{j+1}$ (you can assume ...
0
votes
0answers
20 views

are these functions for open address hashing, proper?

I want to use these two functions in two hash-tables with open-addressing. Is there any problems with these functions? If yes, why they are not appropriate? ...
0
votes
0answers
84 views

Perfect hashing function algorithm

Is there a good (perfect) hashing algorithm for the following problem? We have $n \ll m$ (say $n=150$ and $m=5\times 10^{12}$) and we want a hash table to store integers up to $m$ whose prime ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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-...
0
votes
0answers
193 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 ...
-1
votes
0answers
17 views

Is there a collision free Hash Function for dynamic data that preserves already created hashes?

I am familiar with the concept of hash functions and fingerprints but I am new to the implementation of functions and the specific characteristics of all those hash functions out there. What I need ...