I was looking for a data structure with delete o(1) and random access o(1) for my project. Could anybody help ?
Asked
Active
Viewed 422 times
0
-
When you say "random access", do you mean access by key, or access by index? – Jim Mischel Jun 05 '18 at 00:15
-
possible duplicate of https://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1 – Shanu Gupta Jun 05 '18 at 01:33
-
You really need to add more context. Are you accessing by key or by index? Are your keys integers within a relatively small range, or variable-length strings, or something else entirely? How many items do you expect this data structure to contain? We need more information before we can provide anything like a reasonable answer. – Jim Mischel Jun 05 '18 at 15:37
-
By random access, I mean access by index of course. – iman12 Jun 06 '18 at 03:25
2 Answers
1
If you insist on those complexities and you don't have to release memory in the table as soon as keys are deleted, then you can use dynamic perfect hashing.
It's a little complicated: https://en.wikipedia.org/wiki/Dynamic_perfect_hashing
To get O(1) deletes you'll have to defer any rehashes caused by delete until the next insert.
Matt Timmermans
- 53,709
- 3
- 46
- 87
0
You can use hash tables with an average O(1) but worst case O(n)
kkica
- 4,034
- 1
- 20
- 40
-
-
1https://www.geeksforgeeks.org/design-a-data-structure-that-supports-insert-delete-search-and-getrandom-in-constant-time/ – kkica Jun 04 '18 at 15:56
-
1
-
1
-
You can make worst case O(logn) if you make balanced BST instead of linear chaining in hash table. – Shanu Gupta Jun 05 '18 at 01:28