1

I was watching a youtube tutorial in DS&A (using JS) and he mentioned that the time complexity of accessing or removing property in an object is constant?

how is that possible shouldn't we search for this property first and then delete it or access it. so, it should be linear!

abdallah nagy
  • 33
  • 6
  • 1
    It depends on how you break down the complexity, but property lookup into a hash-key table is generally considered to be constant time. – Pointy Dec 19 '22 at 21:04
  • If property names are thousands of characters long, things get weird, but usually they're not. – Pointy Dec 19 '22 at 21:04
  • but they are not indexed? so, how we get the property in constant could you explain more or give me a reference for that? – abdallah nagy Dec 19 '22 at 21:06
  • 4
    https://en.m.wikipedia.org/wiki/Hash_table – Robin Zigmond Dec 19 '22 at 21:10
  • 1
    The concept of hashing and hash-based data structures is really important, you're going to enjoy learning about it! – Pointy Dec 19 '22 at 21:20
  • also https://stackoverflow.com/questions/34292087/is-there-anything-that-guarantees-constant-time-for-accessing-a-property-of-an-o, https://stackoverflow.com/questions/50250231/is-the-time-complexity-o1-when-i-get-a-value-from-an-object-by-a-key-in-javasc etc. etc – pilchard Dec 19 '22 at 21:30
  • thank you very much @Pointy this wikipedia article answered all my questions and as you said, it's really interesting and i'm exited to learn more in hash table :) – abdallah nagy Dec 19 '22 at 22:00

1 Answers1

1

JavaScript objects are actually hash tables under the hood. (See https://en.wikipedia.org/wiki/Hash_table for more info on how hash tables work.)

In simple terms, in a hash table, the key itself directly correlates to a number when put through the hash table's hashing function, which number is (or correlates to) an address. Thus, JavaScript can (typically) directly use the key name to access that number and/or address. This has runtime complexity O(1) because the key's string (if it's a string) can be decoded into an address without any iteration over the other keys in the object.

JCollier
  • 1,102
  • 2
  • 19
  • 31