Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

Is accessing hashmaps fast (relative to list or array)?

Discussion in 'Entity Component System' started by Mr-Mechanical, Jan 20, 2019.

  1. Mr-Mechanical

    Mr-Mechanical

    Joined:
    May 31, 2015
    Posts:
    507
    Hi,

    I'm thinking of switching a list for a hashmap. Is accessing values from keys similarly performant to accessing a value from a list by index? I'm looking at NativeHashMap source to try to understand how it works, do hashmaps require iteration to access a key by value or is the access time always constant time?

    Thank you for the help.
     
  2. Abbrew

    Abbrew

    Joined:
    Jan 1, 2018
    Posts:
    417
    Not a direct answer, but please be wary of how you implement your GetHashCode() function. Computing the hash of a float for example is EXTREMELY expensive - 7x as expensive as hashing an int/int2/int3. Therefore accessing a hashmap will be quick if your hash function simply returns a unique identifier (like Entity's GetHashCode). Better yet, have a constructor that computes the hashed value and store it in a short and return that (short reduces the size of the struct which brings me to my next point). Also consider the size of the struct when using it as a key. Since structs are copied, larger structs will take longer to copy and manipulate. Smaller structs will make iterating the hashmap fast. Sorry if this didn't directly answer your question, I was just worried you might run into this issue
     
    Mr-Mechanical likes this.
  3. tertle

    tertle

    Joined:
    Jan 25, 2011
    Posts:
    3,752
    As Abbrew, if your hash is extremely fast the lookup is fast.

    Stuff like int or Entity (which only hashes the index not the version) are extremely quick in a hashmap. Once you start using stuff like hash = 237 ^ x; hash = 317 ^ y; etc it becomes notable slow when your count increases and not something you probably want to use for over 1k entities.
     
    Mr-Mechanical likes this.
  4. nat42

    nat42

    Joined:
    Jun 10, 2017
    Posts:
    353
    Hashmaps are a way to accellerate accessing a value by a key (not a key by a value)

    I believe it's mostly constant time, except when there are hash collisions (your hashing function maps multiple keys to the same hash bucket)
     
    Mr-Mechanical likes this.
  5. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    8,194
    If you were able to access the list via index then the faster option would be to use an array.
     
    Mr-Mechanical likes this.