All Questions
Tagged with hash-tables complexity-theory
6 questions
10
votes
3
answers
2k
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 ...
- 203
7
votes
2
answers
2k
views
Confusion with analysis of hashing with chaining
I was attending a class on analysis of hash tables implemented using chaining, and the professor said that:
In a hash table in which collisions are resolved by
chaining, an search (successful or ...
- 275
1
vote
3
answers
274
views
Is the capacity of a hash table a constant value?
In this paper, page 4, it is said:
"...there is always a constant expected number of elements that map to the same slot"
Assume we have a set $S$ of $n$ values, and we want to insert them into a ...
- 111
1
vote
1
answer
302
views
Counting letter frequency in array in O(1) with hash function
I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p']
There are several ways to do this:
A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
- 167
1
vote
1
answer
88
views
Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?
The Problem:
I am currently analyzing a simple program that takes a file of length $n$, splits it into its individual words (seperated by white space) and adds those words to a set:
...
- 11
0
votes
3
answers
2k
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)$?
- 41