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)

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

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

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)

Learning Reactive Programming With Java 8

Thinking in Java (4th Edition)

Java Artificial Intelligence: Made Easy, w/ Java Programming