A finite map data structure that addresses stored values using a function that maps many values to few addresses.
2
votes
2answers
54 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 ...
0
votes
1answer
22 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 ...
8
votes
3answers
200 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
54 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
62 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 ...
2
votes
0answers
77 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
104 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
61 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
140 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
174 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
136 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
107 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)$?
14
votes
1answer
301 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
101 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
390 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 ...
7
votes
2answers
421 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 ...
9
votes
4answers
492 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 ...
8
votes
1answer
2k 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 ...
25
votes
4answers
3k 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 ...
