Skip to content

Instantly share code, notes, and snippets.

@tan-i-ham

tan-i-ham/gist:8677624dde8266142a7ba9b9c709523b

Forked from psayre23/gist:c30a821239f4818b0709
Last active September 22, 2022 11:46
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tan-i-ham/8677624dde8266142a7ba9b9c709523b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tan-i-ham/8677624dde8266142a7ba9b9c709523b to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tan-i-ham revised this gist Sep 20, 2022. 1 changed file with 10 additions and 10 deletions.
    20 changes: 10 additions & 10 deletions gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -34,13 +34,13 @@



    Map | Get | ContainsKey | Next | Data Structure
    ----------------------|----------|-------------|----------|-------------------------
    HashMap | O(1) | O(1) | O(h / n) | Hash Table
    LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List
    IdentityHashMap | O(1) | O(1) | O(h / n) | Array
    WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table
    EnumMap | O(1) | O(1) | O(1) | Array
    TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree
    ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables
    ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List
    Map | Get | Put | Remove | ContainsKey | Next | Data Structure
    ----------------------|----------|-------|----------|--------------|----------|-------------------------
    HashMap | O(1) | | O(1) | O(1) | O(h / n) | Hash Table
    LinkedHashMap | O(1) | | | O(1) | O(1) | Hash Table + Linked List
    IdentityHashMap | O(1) | | | O(1) | O(h / n) | Array
    WeakHashMap | O(1) | | | O(1) | O(h / n) | Hash Table
    EnumMap | O(1) | | | O(1) | O(1) | Array
    TreeMap | O(log n) | | | O(log n) | O(log n) | Red-black tree
    ConcurrentHashMap | O(1) | | | O(1) | O(h / n) | Hash Tables
    ConcurrentSkipListMap | O(log n) | | | O(log n) | O(1) | Skip List
  2. tan-i-ham revised this gist Sep 20, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,7 @@
    List | Add | Remove | Get | Contains | Next | Data Structure
    ---------------------|------|--------|------|----------|------|---------------
    ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array
    LinkedList | O(1) | O() | O(n) | O(n) | O(1) | Linked List
    LinkedList | O(1) | O(n) | O(n) | O(n) | O(1) | Linked List
    CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array


  3. tan-i-ham revised this gist Sep 20, 2022. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -4,7 +4,7 @@
    List | Add | Remove | Get | Contains | Next | Data Structure
    ---------------------|------|--------|------|----------|------|---------------
    ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array
    LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List
    LinkedList | O(1) | O() | O(n) | O(n) | O(1) | Linked List
    CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array


  4. @psayre23 psayre23 revised this gist Jan 3, 2015. 1 changed file with 30 additions and 30 deletions.
    60 changes: 30 additions & 30 deletions gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -1,36 +1,36 @@
    Below are the Big O performance of common functions of different Java Collections.


    List | Add | Remove | Get | Contains | Data Structure
    ---------------------|------|--------|------|----------|---------------
    ArrayList | O(1) | O(n) | O(1) | O(n) | Array
    LinkedList | O(1) | O(n) | O(n) | O(n) | Linked List
    CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | Array



    Set | Add | Contains | Next | Data Structure
    --------------------|----------|----------|----------|-------------------------
    HashSet | O(1) | O(1) | O(h/n) | Hash Table
    LinkedHashSet | O(1) | O(1) | O(1) | Hash Table + Linked List
    EnumSet | O(1) | O(1) | O(1) | Bit Vector
    TreeSet | O(log n) | O(log n) | O(log n) | Red-black tree
    CopyOnWriteArraySet | O(n) | O(n) | O(1) | Array
    ConcurrentSkipList | O(log n) | O(log n) | O(1) | Skip List



    Queue | Offer | Peak | Poll | Size | Data Structure
    ------------------------|----------|------|----------|------|---------------
    PriorityQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap
    LinkedList | O(1) | O(1) | O(1) | O(1) | Array
    ArrayDequeue | O(1) | O(1) | O(1) | O(1) | Linked List
    ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | Linked List
    ArrayBlockingQueue | O(1) | O(1) | O(1) | O(1) | Array
    PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap
    SynchronousQueue | O(1) | O(1) | O(1) | O(1) | None!
    DelayQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap
    LinkedBlockingQueue | O(1) | O(1) | O(1) | O(1) | Linked List
    List | Add | Remove | Get | Contains | Next | Data Structure
    ---------------------|------|--------|------|----------|------|---------------
    ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array
    LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List
    CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array



    Set | Add | Remove | Contains | Next | Size | Data Structure
    ----------------------|----------|----------|----------|----------|------|-------------------------
    HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table
    LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List
    EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector
    TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree
    CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array
    ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List



    Queue | Offer | Peak | Poll | Remove | Size | Data Structure
    ------------------------|----------|------|----------|--------|------|---------------
    PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap
    LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array
    ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List
    ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List
    ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array
    PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap
    SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None!
    DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap
    LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List



  5. @psayre23 psayre23 created this gist Jan 3, 2015.
    46 changes: 46 additions & 0 deletions gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    Below are the Big O performance of common functions of different Java Collections.


    List | Add | Remove | Get | Contains | Data Structure
    ---------------------|------|--------|------|----------|---------------
    ArrayList | O(1) | O(n) | O(1) | O(n) | Array
    LinkedList | O(1) | O(n) | O(n) | O(n) | Linked List
    CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | Array



    Set | Add | Contains | Next | Data Structure
    --------------------|----------|----------|----------|-------------------------
    HashSet | O(1) | O(1) | O(h/n) | Hash Table
    LinkedHashSet | O(1) | O(1) | O(1) | Hash Table + Linked List
    EnumSet | O(1) | O(1) | O(1) | Bit Vector
    TreeSet | O(log n) | O(log n) | O(log n) | Red-black tree
    CopyOnWriteArraySet | O(n) | O(n) | O(1) | Array
    ConcurrentSkipList | O(log n) | O(log n) | O(1) | Skip List



    Queue | Offer | Peak | Poll | Size | Data Structure
    ------------------------|----------|------|----------|------|---------------
    PriorityQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap
    LinkedList | O(1) | O(1) | O(1) | O(1) | Array
    ArrayDequeue | O(1) | O(1) | O(1) | O(1) | Linked List
    ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | Linked List
    ArrayBlockingQueue | O(1) | O(1) | O(1) | O(1) | Array
    PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap
    SynchronousQueue | O(1) | O(1) | O(1) | O(1) | None!
    DelayQueue | O(log n) | O(1) | O(log n) | O(1) | Priority Heap
    LinkedBlockingQueue | O(1) | O(1) | O(1) | O(1) | Linked List



    Map | Get | ContainsKey | Next | Data Structure
    ----------------------|----------|-------------|----------|-------------------------
    HashMap | O(1) | O(1) | O(h / n) | Hash Table
    LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List
    IdentityHashMap | O(1) | O(1) | O(h / n) | Array
    WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table
    EnumMap | O(1) | O(1) | O(1) | Array
    TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree
    ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables
    ConcurrentSkipListMap | O(log n) | O(log n) | O(1) | Skip List