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

learn more… | top users | synonyms

0
votes
1answer
23 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
53 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
409 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
23 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
44 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 ...
4
votes
1answer
102 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 ...
3
votes
1answer
33 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
23 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
45 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
53 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
84 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
71 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
46 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
82 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 ...
6
votes
1answer
145 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
154 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
136 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
191 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
834 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
64 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
86 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
122 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
3k 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
395 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
140 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
313 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
143 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
135 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
160 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: ...
6
votes
1answer
278 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
254 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
181 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
760 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
118 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
879 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
1k 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
702 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 ...
13
votes
1answer
5k views

Hash tables versus binary trees

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
34
votes
4answers
8k views

(When) is hash table lookup O(1)?

It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item ...