Linked Questions
22 questions linked to/from (When) is hash table lookup O(1)?
2
votes
1
answer
3k
views
Average number of collisions before successful insertion into hash table
I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$.
I was thinking that since it is a linear probing and ...
- 21
3
votes
1
answer
469
views
Does my simple, static hash table have O(1) worst case lookup?
Will the following simple hash table construction algorithm be able to construct a
static hash table in $O(n)$ expected time, and will the worst case access time be $O(1)$? If not, what are the ...
- 203
10
votes
2
answers
249
views
Determining the particular number in $O(n)$ time and space (worst case)
$\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]...
- 621
0
votes
2
answers
346
views
How does a hash table not require all the keys to be looked through to find a value, i.e. O(N)?
Before starting, I want to say that I understand time complexity, and I understand how a hash table is considered O(1) vs an array having a time comp. of O(N) in terms of what you learn. What I don't ...
- 156
3
votes
0
answers
496
views
Data Structure for storing the Sweep Line Status in Sweep Line Algorithms
I have been looking into the sweep line algorithms of finding intersection of line segments and polygon partitioning using monotone polygons. The algorithms require a dynamically balanced binary tree ...
- 31
10
votes
0
answers
254
views
Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]
Background:
In this question we care only about worst-case running-time.
Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
- 22.5k
0
votes
0
answers
150
views
is hash table a magic?
I have no cs background (algorithm and data structure), but need to find a data analysis related job since my major is math / statistics. However, (I am trying to avoid software engineering related ...
- 273