Data structure: insert, remove, contains, get random element, all at O(1)

by

Consider a data structure composed of a hashtable H and an array A. The hashtable keys are the elements in the data structure, and the values are their positions in the array.

  1. insert(value): append the value to array and let i be its index in A. Set H[value]=i.
  2. remove(value): We are going to replace the cell that contains value in A with the last element in A. let d be the last element in the array A at index m. let i be H[value], the index in the array of the value to be removed. Set A[i]=d, H[d]=i, decrease the size of the array by one, and remove value from H.
  3. contains(value): return H.contains(value)
  4. getRandomElement(): let r=random(current size of A). return A[r].

since the array needs to auto-increase in size, it’s going to be amortize O(1) to add an element, but I guess that’s OK.

More Related Contents:

  1. How do I prove or disprove that this function is Ω(n^1.5)?
  2. How does a hash table work?
  3. How do I express mutually recursive data structures in safe Rust?
  4. Firebase data structure and url
  5. Implement graph-like data structure in Rust
  6. lenses, fclabels, data-accessor – which library for structure access and mutation is better
  7. Quadtree for 2D collision detection
  8. Advantages of Binary Search Trees over Hash Tables
  9. Difference between binary tree and binary search tree
  10. Are duplicate keys allowed in the definition of binary search trees?
  11. Searching a number in a rotated sorted Array
  12. Efficient implementation of immutable (double) LinkedList
  13. Efficient (and well explained) implementation of a Quadtree for 2D collision detection [closed]
  14. Why hashmap lookup is O(1) i.e. constant time?
  15. What is the left-child, right-sibling representation of a tree? Why would you use it?
  16. Test whether a list contains a specific value in Clojure
  17. Difference between “Complete binary tree”, “strict binary tree”,”full binary Tree”?
  18. Chained Hash Tables vs. Open-Addressed Hash Tables
  19. Linked List vs Vector
  20. Data structure for quick time interval look up
  21. Reverse the ordering of words in a string
  22. Calculate size of Object in Java [duplicate]
  23. Linked List in SQL
  24. How to implement a binary search tree in Python?
  25. Are there strongly-typed collections in Objective-C?
  26. What is the difference between a map and a dictionary?
  27. Why are hash table expansions usually done by doubling the size?
  28. Table like java data structure
  29. What should the ‘pop()’ method return when the stack is empty? [duplicate]
  30. Why do hash keys have different order when printing?

Leave a Comment