All Questions
4 questions
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
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
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
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