Array/map like data structure with unique ID support for items, O(1) get() method and no duplication

user_864101 0
Viewed 342

I have a lot of data that I store in arrays. All array items have a string unique ID (like 123e4567-e89b-12d3-a456-426614174000). Before pushing an item, I call findIndex to make sure no duplicates are inserted with the same ID. I frequently access array items by index and by ID (find(i => i.id === UUID))

Is there a more efficient data structure for this? Supporting these features:

  1. ordered items (should support push, unshift)
  2. get item by ID in O(1) time (faster find)
  3. get item index by ID in O(1) time (faster findIndex)
  4. get items by index (arr[index])
  5. no duplication by ID (#2 will make this easy to support)
  6. easy iteration (for..of / forEach)
  7. sorting items

I looked into a regular object and a Map but they don't support accessing items by index or sorting.

typescript data-structures arrays javascript
2 Answers

Using an object or Map indexed by ID will work fine. Accessing an object key will be O(1), as is Map.has.

In order to get the item index in O(1) as well without iterating over the object or Map again, create another data structure mapping IDs to their index.

const itemsById = new Map();
const itemsByIndex = new Map();
const addItem = (item) => {
  if (itemsById.has(item.id)) return; // duplicate already exists
  itemsById.set(item.id, item);
  itemsByIndex.set(itemsByIndex.size, item);
};

Maps can be iterated over with for..of. Objects can be iterated over with .entries().

To "sort", put the values into an array, sort the array, then change itemsByIndex as needed.

user_95152070

Edit: you noted in a comment you don't want to sort by UUID. Well be default everything will be sorted by insertion order, and if you wanted to sort by another value you would push that value to the sort array instead of "data.id".

I am upvoting the above answer, because you will have to use a couple different data structures to accomplish what you want. Here is a way to implement this in one Javascript object:

const myDictionary = function() {
  let sort = [];
  const indexes = new Map();
  const dictionary = new Map();
  
  this.addItem = function(data) {
    indexes.set(data.id, sort.push(data.id) - 1);
    dictionary.set(data.id, data);
  }
  
  this.getItemByID = function(key) {
    return dictionary.get(key);
  }
  
  this.getItemByIndex = function(i) {
    return dictionary.get(sort[i]);
  }
  
  this.getItemIndex = function(id) {
    return indexes.get(id);
  }
  
  this.sortItems = function(sortingAlgorithm) {
    if (sortingAlgorithm) {
      sort = sortingAlgorithm(sort);
    } else {
    
      function quickSortBasic(array) {
        if(array.length < 2) {
          return array;
        }

        var pivot = array[0];
        var lesserArray = [];
        var greaterArray = [];

        for (var i = 1; i < array.length; i++) {
          if ( array[i] > pivot ) {
            greaterArray.push(array[i]);
          } else {
            lesserArray.push(array[i]);
          }
        }

        return quickSortBasic(lesserArray).concat(pivot, quickSortBasic(greaterArray));
      }

      sort = quickSortBasic(sort);
    }
    
    sort.forEach(function (el, i) {
      indexes.set(el, i);
    });
  }
}

const dictionary1 = new myDictionary();

dictionary1.addItem({id: "1", data:"data 1"});
dictionary1.addItem({id: "4", data:"data 4"});
dictionary1.addItem({id: "2", data:"data 2"});

console.log(dictionary1.getItemIndex("4"));

dictionary1.sortItems();

console.log(dictionary1.getItemIndex("4"));
console.log(dictionary1.getItemByID("2"));
console.log(dictionary1.getItemByIndex(0));

Note that sorting uses a quick sort algorithm by default but still has to iterate over the "indexes" map and update all the data, so a bit inefficient. If you can find a way to sort AND update the indexes at the same time, that would be better, but I cannot think of a way right at the moment.

user_60006800
Related