The Magic of Maps. QuickMap.java

Discussion in 'Resources' started by AronTheGamer, Aug 21, 2014.

Thread Status:
Not open for further replies.
  1. Offline

    AronTheGamer

    Nevermind.
     
  2. Offline

    zombiekiller753

    AronTheGamer
    No.
    Just about everyone who uses a Map, uses a HashMap, and that's not how a HashMap works.

    Imagine if you had 1 million entries. Your code would take, at the worst case scenario, o(n) time.

    However, a HashMap, like the name suggests, uses the hashcode of keys to sort them. They're put in to 'buckets', and therefore when you request a value by key, it'll look up the hashcode, and get the correct bucket. From there, it'll be able to look up your value much faster.

    Think of it like an actual dictionary, where the buckets are A-Z. When you look for the word 'Zoo', you don't start from 'A' and go all the way through. You start at 'Z' and go from there.
     
    Garris0n, Phasesaber and Skyost like this.
  3. Offline

    xTrollxDudex

  4. Offline

    zombiekiller753

  5. Offline

    RawCode

    Quick?

    please return april first.
     
    Garris0n likes this.
  6. Offline

    IDragonfire

    That is not a Map, it is a Set, or a Array structure ...
    Your runtime to, get, remove check keys is linear, O(n)
    In a Map you get, removs ans check keys in constant time, O(1) [best and average case, worst case also O(n)]

    Try to insert 1.000.00 items in your "QuickMap" and then grab all reverse
    Do the same with a Map, e.g. a HashMap.

    If you messaure the time you see the different ;)

    You can try google,
    I advice this book for the full details: http://mitpress.mit.edu/books/introduction-algorithms

    ###
    If you want to learn: http://en.wikipedia.org/wiki/Data_structure
    For Big O notation: http://en.wikipedia.org/wiki/Big_O_notation
    Map: http://en.wikipedia.org/wiki/Hash_table
    Array: http://en.wikipedia.org/wiki/Array_data_structure
    Set: http://en.wikipedia.org/wiki/Set_(abstract_data_type)
     
  7. Offline

    marwzoor

    Just make a binary search tree :3

    http://en.m.wikipedia.org/wiki/Binary_search_tree

    Can handle millions of data and it's greatly faster than a HashMap.

    The class is called TreeMap in the java library and is the same thing as a binary search tree.
     
  8. Offline

    PandazNWafflez

    marwzoor That only helps if your data has a defined natural order.
     
  9. Offline

    Comphenix

    Not really, just compare the average time complexity of a binary search tree and a hash table. Basically, the average time it takes to look up or insert entries in a BST "grows like" (see the defintion of Big O) the natural logarithm of the total number of entries. In contrast, adding more entries to a hash table will not slow down these operations.

    TreeMap does not generally perform better than HashMap as a Map, but it allows for quick lookup of the minimum and maximum entry, or the first entry just below or above a certain key. In those specific cases, a HashMap is inefficient.
     
    PandazNWafflez likes this.
  10. Offline

    IDragonfire

    Now the thread become a ressource thread xD

    I think @Compenix and marwzoor both said the truth.

    Generally a HashMap/table has a average/best case lookup time from O(1), also in big data.
    A Tree has a lookup time from O(log(n)).
    O(1) is faster then O(log n).
    (I ignored the constant factors for each implementation).

    The problem are the hashfunction and the collisions.
    In big data the probability of collisions are higher and the lookup time increase.
    On the other side, you must rebalance trees and you have a huge insert time ...

    Hashtable is only the threadsafe (synchronized) variant of a Hashmap (and some other little changes, e.g. null keys not allowed),
    You can access a HashMap from difference threads, what can increase the performance or cause problems xD

    You can not generalize "Map is better then Tree, or reverse", it depend on the data and your usage.

    I refer back to my post about data structure:
    http://forums.bukkit.org/threads/the-magic-of-maps-quickmap-java.305240/#post-2759090

    Trees: http://www.wikiwand.com/en/Tree_(data_structure)
    overview over runtimes: http://bigocheatsheet.com/
     
Thread Status:
Not open for further replies.

Share This Page