Linked Questions
22 questions linked to/from (When) is hash table lookup O(1)?
0
votes
1
answer
3k
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 ...
- 109
26
votes
11
answers
8k
views
"For small values of n, O(n) can be treated as if it's O(1)"
I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1).
Example:
The motivation for doing so is based on the incorrect idea that O(1)
is ...
- 373
12
votes
3
answers
22k
views
How are hash table's values stored physically in memory?
Question:
How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often?
My current understanding (could be wrong):
Let's say I have 3 ...
- 221
20
votes
5
answers
3k
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 ...
6
votes
5
answers
3k
views
Hash table collisions: why use a linked list if we can use a hash set?
One way to deal with the problem of collisions for a hash table is to have a linked list for each bucket. But then the lookup time is no longer constant. Why not use a hash set instead of a linked ...
- 159
8
votes
2
answers
4k
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 ...
- 367
7
votes
2
answers
2k
views
More efficient algorithm for determining if one list is a sublist of another list
I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list.
What if the list is sorted?
An ...
- 275
1
vote
1
answer
931
views
Sorting when there are only O(log n) many different numbers
We have $n$ integers with lot's of repeated numbers. In this list, the number of distinct elements is $O(\log n)$. What's the best asymptotic number of comparisons for sorting this list?
Any idea or ...
- 507
4
votes
2
answers
4k
views
Are dictionaries and associative arrays the same thing?
With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?
- 177
2
votes
2
answers
4k
views
Time complexity of Hash table lookup
Suppose I have a hash table which stores the some strings. Let the index/key of this hash table be the length of the string. what is the time complexity of checking if the string of length K exists in ...
- 23
9
votes
4
answers
3k
views
Can element uniqueness be solved in deterministic linear time?
Consider the following problem:
Input: lists $X,Y$ of integers
Goal: determine whether there exists an integer $x$ that is in both lists.
Suppose both lists $X,Y$ are of size $n$. Is there a ...
D.W.♦
- 166k
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
5
votes
2
answers
919
views
Why isn't an edge-map graph implementation used in practice?
Wikipedia states that three different graph implementations are used in practice:
Adjacency Lists
Adjacency Matrix
Incidence Matrix
While I was learning about these structures, another option ...
- 151
3
votes
3
answers
2k
views
Simple Uniform Hashing Assumption and worst-case complexity for hash tables
Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)?
It says in the Wikipedia article that this assumption implies ...
- 229
6
votes
1
answer
818
views
Best data structure for a queue with random reads?
Well, it's not exactly a queue if it allows for random reads. This question is about a data structure which behaves like a queue for insertions and a sorted dictionary for reads.
Imagine an algorithm ...
- 249