# 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

48 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
684 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 ...
172 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$ ...
259 views

14 views

### Efficiently extendable hash function?

I'm wondering whether there exists some good known hash functions with the following property: Assume that $x$ is some string over some alphabet $A$, then given $H(x)$ we can compute in $O(1)$ time ...
36 views

### How can I choose good hash function for PCY algorithm

As far as I understand from PCY (Park, Chen, and Yu) algo is that the algo uses hashing during the first pass to reduce the number of CANDIDATE pairs that are considered in the second pass. I have 2 ...
66 views

### A tree-like data structure with rights delegation for distributed computing

Every actor can create a root node and delegate a right to add a child node. Every node contains name of its’ creator or who added it, and value S. Sum of all values S at the same level of the tree ...
21 views

### Is there a good way to hash abstract binding trees?

The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the ...
44 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 ...
51 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 ...
98 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)...
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)$ ...
158 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 ...
66 views

### Min/max of hash function (Whirlpool)

The Whirlpool hash function generates a 128-digit hexadecimal number. Could that number ever be ...
30 views

### Choosing an independent hash function, given hash function value

Supposed we have a function $h:U\to [m_1]$. Given this hash function, can we generate without using randomization or a universal hash collection another hash $h':U \to [m_2]$, which depends on $h$ ...
8 views

### Creating a specific hash setup

While solving a practice exam, this is the question I could not answer. Any help is appreciated. I am new to hashing and have no idea how to solve this question. Let $H$ be a $(0.15, 0.85, 0.9, 0.1)$-...
63 views

### How can I create 10-character, unique codes with no collisions, but without being predictable?

If we are using numbers and letters, there are $36^{10}$ unique combinations. Collision is already unlikely, but I need it to be impossible, so using hashing is out of the picture(?). The use-case is ...
17 views

### Why did Wegman-Carter call their class of hash functions as universal on their seminal paper

Wegman-Carter on their seminal Universal classes of hash functions uses the term universal for their definition. They gave this definition as: Let $H$ be a class of functions from $A$ to $B$. We ...
35 views

### How can I hash an attributed graph?

I am interested in solving the following problem using a learning to hash algorithm: I've got several attibuted graphs (a graph with node and edge labels - you can think about that as a description ...
14 views

### When to apply a probe sequence when inserting an element to a hash table

So, if we start out with an empty table with M elements. Do we always need to have a specified hash function say $h(x) = x \% 8$ as well as a specific probing sequence to use when inserting a ...
33 views

### Construction of hash function with a given distribution

Two questions about the construction of a hash function: Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
18 views

### Time complexity of website access analysis using Hash Tables

I would like to calculate the time complexity of an algorithm which returns the number of accesses of a website and the number of different users who entered. Each user is represented by a unique ...
57 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 ...
30 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 ...
36 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 ...
41 views

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?
125 views

### Is this PJW hash function incorrect?

I came across this implementation of PJW and it seems incorrect: ...
220 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$. ...
1k 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 ...
392 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 ...
28 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. ...
83 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, ...
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 ...
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? ...
95 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 ...
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 ...
720 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 ...
81 views

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

This is a specific question about . 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-...
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 ...