Java Data Structure Summary

c82-java-prog-logo

Data Structure in Java
ArrayList — Resizable Array Implementation
1.5x resize if necessary

GC vs ARC
runtime vs compile time
https://stackoverflow.com/questions/7874342/what-is-the-difference-between-objective-c-automatic-reference-counting-and-garb

Right shift vs Division
1. faster
2. pure integer
3. no intermediate solution overflow issue (safer, avoid stack overflow)

append operation: Amortized o(1)

seamless

Resizable Array
Random Access: o(1)

ArrayDeque — Resizable Circular Queue
2x resize if necessary (bit operation)

LinkedList
Double Linked List in Java
8 bytes to store last or next pointer
Dynamic data structure

ArrayDeque is better for implementing Stack/Queue, for consecutive space, almost o(1) for head/tail operation

Queue queue = new ArrayDeque();
Queue queue = new ArrayDeque(1000); // avoid too much resize

List queue = new ArrayList(1000);
Deque stack = new ArrayDeque(1000);

Stack (Vector) is thread safe data structure, slower for cases which doesn’t need multi-thread

Hashing
build index (map object to number/hash code, many to one, ideal status is one to one)
Default: memory address
Hashcode design 3 principles:
1. same code for repeating calling in same application
2. Equal => same hash code
3. same hash code !=> Equal, but good to have

HashTable
Search an element in an array time complexity:
unsorted array with o(n)
sorted array with o(logn)

search in almost o(1), insert in almost o(1)

Use hashcode and array length to get index of array

Mapping: hashCode => arrayIndex
arrayIndex = hashCode % length

Collision:
Linear Probing (clustering in head or tail)
Separate Chain (Linked List)

Rehashing (Load Factor = number of entries / length, if over threshold like 75% and resize)

HashMap
Default value:
size: 16
load factor: 0.75
hash % length => hash & (length – 1)

X mod 2^n (X & (2^n – 1))

Map of List is slower than List of List

HashSet (HashMap wrapper class with dummy value)

LinkedHashMap
Linked List + Hashmap
LinkedList maintains the order for insertion

LRU (Least Recently Used) Cache

LinkedHashMap – maintain visit instead of insert order, handle size

TreeMap
Red-black Tree (self balanced binary searched tree) implementation
Mid-order Iteration (calculate )
o(logn): put, containsKey, remove
sorted keys

TreeSet (TreeMap wrapper class with dummy value)

Heap
Complete Tree (Each level must have max number of nodes, bottom level could be an exception, filled from left to right on each level)
Largest/smallest in the root
Children are always smaller/larger than parent

Add/Remove (sink up/down)
Keep complete tree structure
Keep parent-children value order

Remove the root only allowed

Store as array actually (childrenIdx – 1)/2 = parentIdx, leftChildIdx = 2 * parentIdx + 1, rightChildIdx = leftChildIdx + 1

PriorityQueue in Java (offer as add)

Practice: Top K Numbers

ArrayList: 1.5x resize(most operation on one side)
ArrayDeque: 2x resize (most operation on two sides)
HashMap: 2x resize (reduce the number of rehashing)

Donate $5 to me for a coffee with PayPal and read more professional and interesting technical blog articles. Feel free to visit my web app, WhizWallet, to apply for credit, store or gift cards, DealsPlus to browse daily deals and store coupons to save money.
Follow me @Yaoli0615 at Twitter to get latest tech updates.
Resources:

Core Java Volume I–Fundamentals (10th Edition) (Core Series)

Core Java, Volume II–Advanced Features (10th Edition) (Core Series)

Test-Driven Java Development

Java Concurrency in Practice

Java: An Introduction to Problem Solving and Programming (7th Edition)

Java 9 for Programmers (Deitel Developer Series)

Java SE8 for the Really Impatient: A Short Course on the Basics (Java Series)

Core Java for the Impatient

Java: The Beginners Guide for every non-programmer which will attend you trough your learning process

Java Deep Learning Essentials

Machine Learning in Java

Learning Reactive Programming With Java 8

Java 9 Programming By Example

Thinking in Java (4th Edition)

The Java EE Architect’s Handbook, Second Edition: How to be a successful application architect for Java EE applications

Java Artificial Intelligence: Made Easy, w/ Java Programming

Advertisements

About liyao13

Yao Li is a web and iOS developer, blogger and he has a passion for technology and business. In his blogs, he shares code snippets, tutorials, resources and notes to help people develop their skills. Donate $5 to him for a coffee with PayPal at About Me page and read more professional and interesting technical blog articles. Follow him @Yaoli0615 at Twitter to get latest tech updates.
This entry was posted in CS Research&Application, Uncategorized and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s