A finite map data structure that addresses stored values using a function that maps many values to few addresses.

learn more… | top users | synonyms

-1
votes
1answer
39 views

Operation with same asymptotic cost on hash tables and lists

Let $x \in \{ \log n, n, \dots , n!\}$ some (cost) function. Are there interesting operations with runtime in $O(x)$ on lists which also have runtime in $O(x)$ on hash tables?
1
vote
0answers
15 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 ...
0
votes
1answer
26 views

How does these Probing time occurs for hash tables

I am having a hard time understanding the numbers of probing which might occur due to using different collision prevention method such as separate chaining, Linear Probing, double probing, which is ...
1
vote
0answers
37 views

Tradoff between space and false positive rate when using bloom filters

Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
1
vote
1answer
43 views

Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent

Consider the hash function mapping $w$-bit keys to hash values in $\{0,...,m-1\}$. Suppose $w=cr$. Interpret a $w$-bit key $x$ as a vector $(x_1,...,x_c)$ of $c$ $r$-bit keys. Consider the ...
2
votes
1answer
82 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 ...
3
votes
1answer
100 views

Probability of probing $t$ locations in a Cuckoo hash is $O(\frac{1}{2^{t/2}})$ locations in the worst case

I was told this question may be better received here. Prove that the probability that an insertion into a cuckoo hash table probes $t$ array locations is $O(\frac{1}{2^{t/2}})$. Keep in mind ...
3
votes
1answer
49 views

Where does the terminology of open addressing resp. closed hashing come from?

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books). Why the names "open" and "closed", and why these seemingly contradictory ...
0
votes
0answers
14 views

Expected number of collisions, 2 different solutions, what makes the difference?

The first solution: The probability that a slot is not mapped to on a single insert is $1-\frac{1}{m}$, and the probability it is not mapped to after $n$ inserts is $(1-\frac{1}{m})^n$. So the ...
2
votes
1answer
82 views

How can you iterate through a hash table in constant time?

I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that: "Hopefully, all the elements that are in your set happen to be placed into ...
2
votes
2answers
48 views

Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$

More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\{1..N\}$. I want to efficiently (as far as memory and time complexity goes) ...
1
vote
1answer
92 views

How to find expected number of slots of a certain size k in hash table?

If you can make no assumptions about the hash function, how can you find the expected number of slots of certain size k in a hash table? Looking more for a theoretical proof type of answer than a ...
5
votes
2answers
110 views

How to avoid cascading resizes when resizing hash tables?

With conventional collision resolution methods like separate chaining and linear/quadratic probing, the probe sequence for a key can be arbitrarily long - it is simply kept short with high probability ...
0
votes
1answer
30 views

Hashing and number of comparisons [duplicate]

Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all ...
5
votes
0answers
67 views

How are hash tables O(1) taking into account hashing speed?

Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity. However, this assumes the lengths of the elements are constant. Computing the hash of an ...
7
votes
3answers
540 views

What does “non-pathological data” mean?

I took an algorithms class on Coursera. The professor in the video about hash tables said that What's true is that for non-pathological data, you will get constant time operations in a properly ...
1
vote
1answer
39 views

Hash tables - probing for collisions run time

The question is a true or false question: Hash tables using probing for collisions run in constant time with respect to how many items are in the hash but are at least linearly dependent on how full ...
-1
votes
1answer
48 views

Does an associative array represent a mapping?

An associative array is a set of pairs (key, value). Does it represent a mapping, or a relation (i.e. does it allow the same key to be associated to different values)? Does it represent an ...
3
votes
1answer
109 views

Why does appending permutations of servers at the end of hash table avoid bottlenecks?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf The paper has a TLT (tract locator table) for identifying where to write in each ...
2
votes
1answer
36 views

Why does the following function distribute things in a binomial distribution?

I was reading the following FDS paper: https://www.usenix.org/system/files/conference/osdi12/osdi12-final-75.pdf and it says that the the following hash function does not distribute things uniformly ...
-1
votes
1answer
26 views

How to tell which value belongs to the key during hashing

To prevent collisions in Hash table , seperate chaining with linked list is used . Hash table works by hashing the key and storing the value in the bucket. Assuming 4 keys hash to the same bucket , ...
0
votes
1answer
51 views

Proving that collision is less likely if the table size is prime in case modulo arithmetic is used

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, ...
1
vote
1answer
63 views

The theoretical upper bounds for duplicate detection in a set of objects?

I recently had a lengthy exchange with someone about the most efficient way to remove duplicates from a collection. The debate was mostly centered around the specific behavior of C# collections, such ...
2
votes
2answers
88 views

What is this hash of array data structure called?

I've created a data structure that is a hash of arrays with a special property: the hash keeps track of the combined order in which items are appended to its arrays. For example (pseudocode): ...
1
vote
1answer
149 views

Why should one not use a 2^p size hash table when using the division method as a hash function?

I don't understand what is meant by: "m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k." (pg. 231 of CLRS) Terms defined: ...
1
vote
2answers
51 views

Hashing a Specific Range Of a Character Array [closed]

I need to process queries to Hash various ranges of a character array. I am currently using the Arrays.hashCode from the standard java library. But the problem is that this method is too slow. Also my ...
-1
votes
2answers
86 views

Recurrence for total number of extraneous key insertions in a hash table

I have a practice exam question that I don't know how to set up a recurrence for. It is dealing with a hash table. The question is as follows: Suppose that a hashing strategy is designed so that ...
9
votes
1answer
191 views

Universal Hashing in Practice

A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if $$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$ You can find more about ...
4
votes
1answer
187 views

Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most

There are $n$ elements in a hash table of size $m \geq 2n$ which uses open addressing to avoid collisions. The hash function was chosen randomly among a set of uniform functions. A set $H$ of ...
1
vote
1answer
158 views

Double hashing - probe count probabilities

From TAoCP, Vol. 3 by Knuth we know that expected (mean) probe counts for hash tables with open adressing and double hashing collision-resolution are: $1 \over 1 - \alpha$ - for unsuccessful search ...
1
vote
1answer
245 views

Find similar vector by Locality Sensitive Hashing

I have many vectors in my database. They are in high dimensions such as: $v_1$ : $\langle 23, 23, 1, 33, 103, 219, \dots \rangle$ $v_2$ : $\langle 92, 83, 1, 33, 239, 192, \dots \rangle$ ... I ...
0
votes
1answer
936 views

Retrieving data from hash table ordered by insertion time

By default, a hash table is unordered. I have a simple question on the retrieval of elements in a hash table Can we retrieve elements from a hash table in the same order as they are put inside?
-2
votes
1answer
67 views

Complexity of a hash tables with balanced trees in the buckets

If I use a balanced tree instead of lists in a hash table implementation, and also after initializing my table I don't enlarge nor reduce the size of the table, what would be the worst case ...
2
votes
2answers
96 views

Are those definitions of universal hash family equivalent?

I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is. Definition 1: $H$ is a universal ...
1
vote
1answer
145 views

Sequential hash tree traversal

A lot of articles say that hash tree traversal cost to any randomly chosen leaf is $\mathcal{O}(\log_2 N)$ ($N$ is a number of leafs) and that is right. If we have a tree of 8 leafs it will take us at ...
10
votes
3answers
4k views

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...
1
vote
1answer
584 views

How to get expected running time of hash table?

If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in ...
2
votes
1answer
150 views

Hash function - uniformity / strong universality

I am currently learning how randomised Hashing works. So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$. That class is called ...
3
votes
0answers
372 views

Hash table collision probability

For an open-addressing hash table, what is the average time complexity to find an item with a given key: if the hash table uses linear probing for collision resolution? if the hash table uses double ...
2
votes
2answers
157 views

Why can't we use a hash tables for collision resolving in hash tables?

To prevent collisions, hash tables with open addressing use a methodology to chain the contents. Why can't we use another hash table allocated to each slot of the primary hash table?
2
votes
1answer
171 views

How do the following Hash Functions compare?

Consider the two hash functions used to map IP addresses. $x_i$ represents a octave (or "bit field") of the address. Hash Function 1: $$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} a_ix_i \bmod n$$ ...
2
votes
1answer
163 views

Modulo hash function and multiples of three

This is a textbook based question. In The Art of Computer Programming Volume 3, Knuth says that for a hash function $h(k) = k \bmod M$, $M$ should not be a multiple of $3$. The explanation given is: ...
7
votes
1answer
300 views

Origins of the term “distributed hash table”

I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came ...
4
votes
1answer
286 views

Using hash tables instead of lists for buckets in hash tables

Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem? I looked up ...
0
votes
2answers
207 views

What is the average search complexity of perfect hashing?

The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
15
votes
1answer
888 views

How Does Populating Pastry's Routing Table Work?

I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify. Disclaimer: I'm not a computer science student. I've ...
1
vote
1answer
126 views

Is open adressing with prime steps bijective?

Who can help me with this topic: Probing with a step width that is a prime number. I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of ...
5
votes
3answers
1k views

Counting different words in text using hashing

I am still fighting with hashing and I am ask myself: what is the most efficient way to count the number of different words in a text using a hash table? My intuition says that applying the hashcode ...
9
votes
2answers
2k views

Hashing using search trees instead of lists

I am struggling with hashing and binary search tree material. And I read that instead of using lists for storing entries with the same hash values, it is also possible to use binary search trees. And ...
11
votes
4answers
761 views

For what kind of data are hash table operations O(1)?

From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there ...