1

I need to map accented letters (é, ü, á, ï, ö, ..., etc.) to their corresponding letters in English (e, u, a, i, o, ..., etc.).

I know I can do this in several approaches:

  1. Looping through an array - complexity O(n):
const mappingArray = [
   ['é', 'e'],
   ['ü', 'u'],
   ['á', 'a'],
   ['ï', 'i'],
   ['ö', 'o']
];

accentedToEnglish(accented) {
    for (let i = 0; i < mappingArray.length; i++ ) {
      if (mappingArray[i][0] === accented)
            return mappingArray[i][1];
     }
}
  1. Accessing object keys - complexity O(1):
const mappingObject = {
   'é': 'e',
   'ü': 'u',
   'á': 'a',
   'ï': 'i',
   'ö': 'o'
};

accentedToEnglish(accented) {
    return mappingObject[accented];
}

Why is the complexity of the mapping above using object keys = O(1) in javascript? Does't the javascript engine iterate through all the keys behind the scenes in order to find the exact value?

Lorraine R.
  • 1,545
  • 1
  • 14
  • 39
  • 4
    No, objects are implemented as hash tables so that lookup is amortized O(1). – Barmar Apr 24 '23 at 17:45
  • 1
    in a way its like accessing array elements if you know the index. so an array is also like an object `{0:['é', 'e'], 1:['ü', 'u']...}` . `mappingArray['0'][1]` is like `mappingObject['é']` – cmgchess Apr 24 '23 at 18:01
  • Strictly speaking, objects are not usually implemented as hash maps, but JS engines do use hash maps and/or binary search to speed up various operations (such as: caching the result of performing a property lookup on an object that's in "struct mode", not in "hash map mode"). **Pro tip: for patterns like this example, `Map`s will be even faster than regular objects with properties.** – jmrk Apr 29 '23 at 14:09

1 Answers1

0

In JavaScript, objects are implemented as hashes. Which means the keys are fed to a hash function which computes an address in O(1) average and amortized time. To understand more about the complexity of hash tables you could look at:
Hash table runtime complexity (insert, search and delete)

For a quick explanation also take a look at the answer of: What exactly is a hash in regards to JSON?
and Complexity of accessing data in an object.

Naitzirch
  • 45
  • 1
  • 2
  • 6