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

Filter by
Sorted by
Tagged with
1
vote
2answers
345 views

Double Hashing with Strings as key

How would you choose the second hash function with for double hashing with string as key? My first hash function is the scalar product of a random int array with the 16 bit number of each char. Is ...
0
votes
4answers
196 views

What is the best hash functions for millions of String keys?

I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value. The problem that the retrieval process is too slow and I want to ...
0
votes
1answer
13 views

Detecting and correcting collisions in (Zorbist) hashing to avoid errors in transposition table

Context Say I have a transposition table that uses keys produced by (e.g. Zorbist) hashing game positions. The table has a finite recycled memory (key % p is the <...
4
votes
3answers
107 views

Merkle tree sorting leaves and pairs

I am implementing a Merkle tree and am considering using either of the two options. The first one is sorting only by leaves. This one makes sense to me since you would like to have the same input ...
6
votes
1answer
239 views

Hashing using Horner’s Rule

When hashing a (key, value) pair where the key is a string, I have seen the following hash function in use: E.g. $c_n + 256c_{n-1}+ 256^2c_{n-2}+...256^{n-1}c_1$, where this represents the string $...
0
votes
1answer
65 views

Shuffling Bits For Uniform Distribution

I am writing a hashing algorithm to be used in the key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to ...
2
votes
0answers
18 views

Does there exist a locality sensitive hashing for $\ell_p$-norm distance where $p>2$?

It is well known that the $p$-stable distribution can be used to generate locality sensitive hash code for $\ell_p$-norm distance measure where $p \le 2$. However, it seems that the situation for $p&...
3
votes
1answer
84 views

How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?

Imagine my server is generating "tokens" of some sort for a client on a regular basis. When a client asks for a token, the server responds with a new value (and any other supplemental ...
0
votes
1answer
82 views

Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)

I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function. The versions are as follows: ...
1
vote
1answer
30 views

Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
4
votes
1answer
147 views

Count Sketch probability bound

I have been reading up on the Count Sketch algorithm, and I stumpled upon the Count Sketh algorithm explained in section 5 of https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf. Then, I ...
1
vote
1answer
14 views

Universal hash function for strings of unbounded length

Is there a (weakly) universal hash function for strings without any assumption of the string length? I did not find one on Google / Wikipedia.
2
votes
1answer
1k 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
2answers
79 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 ...
2
votes
0answers
29 views

Finding the longest power subsequence

A power sequence is a sequence containing consecutive powers of a number starting from power one. for example $3^1, 3^2, 3^3$ is a power sequence. The question is to find the length of the longest ...
0
votes
0answers
16 views

Propose a family of hash functions with $mod p^2$ for some prime number $p$

I need to define a family H of universal functions $\{0,1, ..., p^k−1\} →\{0,1, ..., p^2−1\}$. Now based on a similar example I was thinking of something like: Given some $a= (a1, a2, ..., ak)∈\{0, ......
0
votes
0answers
18 views

Hash tables for storing data in an application that supports partial search

Is a hash table a good data structure for storing data in an application that support partial search such as "select * from MyTable where name like 'John%'. If not, what is? I would have thought ...
4
votes
1answer
543 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
108 views

Constructing 2-Universal Families

Let H be a class of all functions, mapping M possible keys to N integers. Is it true that H is a 2-universal family? Is it a good idea to use H in applications? I don't even know where and how to ...
0
votes
0answers
21 views

What is the order of magnitude of bitwise operations involved in a SHA-256 hash?

Specifically, how many bitwise operations (approximately, could be just order of magnitude) occur each time a Bitcoin ASIC miner performs a SHA-256 hash in typical mining computation, i.e. as it ...
0
votes
0answers
21 views

If the load factor is a decimal (say 3.6), what is the length of each chain in a hash table that utilizes separate chaining?

I understand that if the load factor were 2, then the length of the chain would be 2 for each index in the array, but what happens if the load factor is a decimal? Do we round up or down?
0
votes
2answers
413 views

My professor claims that inserting the same key into a hash table again will lead to a collision … – Is he really right?

My whole life I thought a collision is a situation that occurs when two distinct pieces of data have the same hash value. Everything looks a little bit different now: A few days ago we had to ...
3
votes
2answers
77 views

Information on Tavori and Dreizin ranged hash function?

While doing some digging around in the GNU implementation of the C++ standard library I came across a section in bits/hashtabe.h that refers to a hash function "in ...
1
vote
1answer
48 views

How 'Avalanche Effect' got its name?

I wonder how or why Avalanche Effect got its name. Avalanche Effect is a desirable property of cryptographic algorithms, wherein if an input is changed slightly (...
1
vote
1answer
45 views

Why mod operation can be used as hash function

I'm new here, and I'm currently trying to understand why mod operation can be used as a hash function. For example, consider the function $h(x)=x\mod 2^{256}$, where $x$ can be a string of any length. ...
1
vote
1answer
38 views

How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

Most definitions of a $k$-wise independent family of hash functions I have encountered state that a family $H$ of hash functions from $D$ to $R$ is k-wise independent if for all distinct $x_1, x_2,\...
4
votes
3answers
89 views

Integer set disjointness query on sketches with something like homomorphic hashing

Suppose I have two sets of integers $A$ and $B$ and I have a sketch data structure described by a function $\mathsf{sketch}_n : \mathcal{P}(\mathbb{Z}) \to 2^n$ that returns a bitstring of size $n$. ...
1
vote
2answers
144 views

Hash functions producing uniform outputs

I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why. Which one of the following hash functions on integers will distribute keys most ...
1
vote
2answers
205 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 ...
1
vote
1answer
57 views

How can I prove or disprove that the following function is bijection?

For a research project, I tried to prove or disprove that a function called xxhash128_low is a bijection from 64 bit unsigned integer to 64 bit unsigned integer. I have shown that it is sufficient to ...
1
vote
2answers
53 views

Question regarding the proof that quadratic probing always finds an empty slot if the table is less than half full

to prove this statement I assume the probing function as: $$h(i,x)=h'(x)+i^2 \text{ mod t} $$ And for $0\leq i,j < \frac{t}{2}$; $i\neq j; t \text{ prime}$: $$h(i,x) = h(j,x)$$ This results into $$(...
1
vote
1answer
105 views

Universal hash functions - Proof

Problem statement Let $K$ be a set of keys with $|K| = n$ and define the index set $I = \{0, \ldots, m-1\}$. Now let $H = \{h \mid h : K \to I\}$, i.e. $H$ contains all hash functions which map the ...
0
votes
0answers
19 views

Bad data for hash function

Is it possible to choose such a nontrivial set of queries so that the amortized running time for a hash table with a public key and a function like $(a_{N − 1}k^{N − 1} +... + A_{1}k + a_0) (mod \: p)$...
0
votes
1answer
30 views

Why is this implementation of the hash function bad?

I have a task of hashing DNA sequences. Let the DNA be long sequences of four amino acids, which we will denote by the letters $A, T, G$ and $C$. My hash function $h$ take DNA as an input and return ...
1
vote
2answers
136 views

Store a n-bit string using only O(log n) space

Is it possible to somehow store a $n$ bit string using only $\mathcal{O}(\log{n})$ space? I am thinking if the string could be stored using a hash function, but I am not sure if it is even possible.
1
vote
0answers
30 views

Is there a standard name for this property of hash functions?

A hash function $H$ operating on strings can have the following property: Let $x$ be a string and $c$ a character. Given $H(x \cdot c)$ and $c$, $H(x)$ can be determined uniquely (where $\cdot$ stands ...
0
votes
1answer
19 views

Choosing the right function

I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining). What is a good hasing function that guarantees a good ...
0
votes
1answer
45 views

oone exmple in hash topics?

Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is ...
0
votes
0answers
34 views

Minimal perfect hash function for set of integers

This might be a trivial question, but I have the following problem: I want to (perfectly) hash a number of lists of integers of length $n$, with all entries between $k_{min}$ and $k_{max}$. How can I ...
1
vote
0answers
66 views

Pairwise independent hash function family?

I am looking for a family of pairwise independent hash functions $\mathcal{H} = \{h \mid h:[n]\rightarrow [m]\}$ that is easily computable. As an example that doesn't seem to work, choose a prime $p &...
1
vote
1answer
18 views

Clarification on evenly dispersing modular hashing [duplicate]

I'm going over "Algorithms fourth edition" by Robert Sedgewick and Kevin Wayne. In the chapter on hash tables I have encountered an easy hashing method called "modular hashing" <...
0
votes
0answers
24 views

Expected runtime for hashing with a binary search tree as collision handling

I thought about implementing a data structure with expected runtime of O(1) for insertion, deletion and look-up and a worst case runtime for these operations of O(log(n)). This is under the assumption ...
0
votes
0answers
42 views

Simple incremental hash funcion

I have permutations: 4 1 2 5 3 4 3 2 5 1 numbers can be order magnitude of 1000 (fits in two bytes) I want compute 32 bit (or better 64 bit) hashes, it should be ...
-1
votes
1answer
81 views

What is Simple Uniform Hashing, and why searching a hashtable has complexity Θ(n) in the worst case

Can anyone explain nicely what Simple Uniform Hashing is, and why searching a hashtable has complexity Θ(n) in the worst case if we don’t have uniform hashing (where n is the number of elements in the ...
0
votes
0answers
25 views

Double Hash Family Universality

Here I am given 2 hash families and I need to prove the universality of the double hash, but I am stuck as to how to prove this. I know the properties of an epsilon-universal family is that the ...
1
vote
1answer
108 views

When and Why do I Rehash?

I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash? One reason to ...
1
vote
2answers
110 views

Looking for memory-efficient way to detect hash collisions

Given a hash function H, it's possible that H(a) = H(b) = c Let's assume we have a big data set [N1 ... Nk], with K items and we hash each item in this set After operation is done, we'd get a set of ...
2
votes
3answers
123 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 ...
2
votes
0answers
39 views

In Universal Hashing- probability of poor performance is small and is the same for any set of keys of the same size

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following claim: Universal Hashing uses randomization.For the example of a compiler's symbol table, ...
0
votes
1answer
66 views

Difficulty in understanding few steps in the proof: “The class $\mathscr{H}_{p,m}$ of hash functions is universal”

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\...

1
2 3 4 5 6