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

learn more… | top users | synonyms

9
votes
3answers
1k 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 ...
5
votes
6answers
835 views

Hash table collisions: why use a linked list if we can use a hash set?

One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked ...
3
votes
2answers
42 views

Hash Table: Relation between position of a value and Hash table size

I need to know whether hash table size, $S$ has any impact on distribution of a value in hash table. At the moment I'm using SHA512 and I can tolerate up to 50 elements in any bucket, and I have ...
2
votes
1answer
42 views

How to resize a large, distributed hash table?

Many hash table implementations found in programming languages (such as Java's HashMap or Python's dict) dynamically increase the size of the hash table once the number of items reaches a certain ...
0
votes
0answers
41 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: http://math.stackexchange.com/questions/1512644/balls-and-bins-hash-table-a-concrete-example but I could not get an answer that I ...
4
votes
1answer
39 views

Balanced allocation-Hash table- overflow probability

My question is related to this: Hash-Table in Practice In [1] page 7, it is said that if we throw $n$ balls into $k$ bins, then each bin contains at most $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log ...
1
vote
0answers
38 views

Find unique vectors by linear algorithm

I was thinking about the homework problem: Given $n$ vectors in 3D: $(\mathbf{v_1},\mathbf{v_2},\dots, \mathbf{v_n})$. Their coordinates are positive integers and less than $10^9$. We should ...
3
votes
1answer
151 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 ...
1
vote
0answers
31 views

Storing variable length Keys in hash table itself

I wrote a custom hash table for a project I'm working on. The core functionality was pretty simple rolling table: In each table there is a memory section for HashItemReference(integer SecondHash, ...
2
votes
3answers
189 views

Memory usage of a BST or hash table?

I would like to use a data structure allowing fast access, either a balanced binary search tree (BST) for $O(\log n)$ access time or an open hash table for constant access time. 1) What is the exact ...
1
vote
1answer
51 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 ?
1
vote
1answer
68 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 ...
1
vote
0answers
22 views

Problem occurring when changing hash table size

I'm practicing an exam for a data structures course. There's a question about a hash table with hash function: $$h'(k,i)=h_1(k)+i*h_2(k) \mod{11}$$ where $$h_1(k)=k \mod{13}$$ and $$h_2(k) = 1 + k ...
1
vote
2answers
139 views

Why can't hash tables provide O(n) sorting?

Since a sufficiently large hash table takes constant time to both insert and retrieve data, should it not be possible to sort an array by simply inserting each element into the hash table, and then ...
0
votes
1answer
671 views

What is the advantage of seperate chaining over open addressing?

Hash tables resolve collisions through two mechanisms, separate chaining or open hashing and open addressing or closed hashing. Though the first method uses lists (or other fancier data structure) ...
3
votes
1answer
146 views

What exactly is a hash function?

I have no idea how I managed to get this far in life without ever really grasping this but as it happens I'm still very confused on the concept of a hash function. I did some googling/wikipedia-ing, ...
0
votes
1answer
69 views

std::hash and separate chaining

I'm attempting to implement my own generic hash table using separate chaining. I'm using the std::hash() method to create my hash function. I noticed in the description of std::hash() that: For two ...
4
votes
3answers
2k views

How are hash table's values stored physically in memory?

Question: How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often? My current understanding (could be wrong): Let's say I have 3 ...
1
vote
0answers
145 views

Improve the runtime of hashtable operations by keeping lists in sorted order

The following is a question from the textbook Introduction to Algorithms, however a solution to the problem is not given... Professor Marley hypothesizes that he can obtain substantial performance ...
3
votes
3answers
444 views

How should I design a hash table where all the keys are permutations?

I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys. Given that I know how all the keys look ...
4
votes
0answers
165 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 ...
10
votes
4answers
203 views

What are the advantages of cuckoo hashing over dynamic perfect hashing?

Dynamic perfect hash tables and cuckoo hash tables are two different data structures that support worst-case O(1) lookups and expected O(1)-time insertions and deletions. Both require O(n) auxiliary ...
0
votes
1answer
48 views

conversion to base-R numbers

I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for ...
-1
votes
1answer
46 views

Operation with same asymptotic cost on hash tables and lists [closed]

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
33 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
37 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
47 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
61 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
96 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
125 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
106 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 ...
2
votes
1answer
219 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
71 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) ...
2
votes
1answer
438 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 ...
6
votes
2answers
207 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
42 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
80 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 ...
8
votes
3answers
1k 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
84 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
54 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
129 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
49 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
35 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
81 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
83 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
100 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
644 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
62 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
91 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
243 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 ...