Coding Techniques
Data Structures in Java · Study material
Hash table with separate chaining
A hash table turns a key into a bucket index with hashCode(), keeps colliding keys in a short chain, and doubles its bucket array when the load factor passes 0.75 – the same plan HashMap follows (plus tree bins for very long chains).
public class Main {
// A tiny String → int hash table with separate chaining (the idea behind HashMap)
static class ChainedHashTable {
private static class Entry {
final String key;
int value;
Entry next;
Entry(String key, int value, Entry next) { this.key = key; this.value = value; this.next = next; }
}
private Entry[] buckets = new Entry[4];
private int size;
private static int index(String key, int length) { return (key.hashCode() & 0x7fffffff) % length; }
void put(String key, int value) {
int i = index(key, buckets.length);
for (Entry e = buckets[i]; e != null; e = e.next)
if (e.key.equals(key)) { e.value = value; return; } // existing key: replace
buckets[i] = new Entry(key, value, buckets[i]); // new key: front of the chain
if (++size > buckets.length * 3 / 4) resize(); // load factor 0.75
}
Integer get(String key) {
for (Entry e = buckets[index(key, buckets.length)]; e != null; e = e.next)
if (e.key.equals(key)) return e.value;
return null;
}
private void resize() { // rehash every entry
Entry[] old = buckets;
buckets = new Entry[old.length * 2];
for (Entry head : old)
for (Entry e = head; e != null; e = e.next) {
int i = index(e.key, buckets.length);
buckets[i] = new Entry(e.key, e.value, buckets[i]);
}
System.out.println(" resized to " + buckets.length + " buckets");
}
}
public static void main(String[] args) {
ChainedHashTable t = new ChainedHashTable();
String[] fruits = {"apple", "banana", "cherry", "date", "elder", "fig", "grape"};
for (int i = 0; i < fruits.length; i++) t.put(fruits[i], i * 2 + 3);
t.put("apple", 4);
System.out.println(t.get("apple") + " " + t.get("fig") + " " + t.get("kiwi") + " size=" + t.size);
}
}
resized to 8 buckets resized to 16 buckets 4 13 null size=7
Trie for prefix search and autocomplete
A trie stores words character by character, so words with a common prefix share nodes. Lookup and prefix search take O(length of the word), independent of how many words are stored.
import java.util.ArrayList;
import java.util.List;
public class Main {
// A trie (prefix tree) for lowercase words
static class Trie {
private static class Node {
final Node[] next = new Node[26];
boolean word; // does a word end here?
}
private final Node root = new Node();
void insert(String w) {
Node n = root;
for (char c : w.toCharArray()) {
int i = c - 'a';
if (n.next[i] == null) n.next[i] = new Node();
n = n.next[i];
}
n.word = true;
}
private Node find(String prefix) {
Node n = root;
for (char c : prefix.toCharArray()) {
n = n.next[c - 'a'];
if (n == null) return null;
}
return n;
}
boolean contains(String w) { Node n = find(w); return n != null && n.word; }
List<String> startsWith(String prefix) { // every word under the prefix, in a-z order
List<String> out = new ArrayList<>();
Node n = find(prefix);
if (n != null) collect(n, new StringBuilder(prefix), out);
return out;
}
private void collect(Node n, StringBuilder sb, List<String> out) {
if (n.word) out.add(sb.toString());
for (int i = 0; i < 26; i++)
if (n.next[i] != null) {
sb.append((char) ('a' + i));
collect(n.next[i], sb, out);
sb.deleteCharAt(sb.length() - 1); // backtrack
}
}
}
public static void main(String[] args) {
Trie t = new Trie();
for (String w : new String[]{"java", "javac", "javadoc", "jar", "jvm", "lambda", "list"}) t.insert(w);
System.out.println(t.contains("java") + " " + t.contains("jav") + " " + t.contains("jvm"));
System.out.println(t.startsWith("jav") + " " + t.startsWith("l") + " " + t.startsWith("x"));
}
}
true false true [java, javac, javadoc] [lambda, list] []
Linked-list pointer patterns
// Middle node: fast moves 2, slow moves 1
Node slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
// Cycle detection (Floyd): the two pointers meet only if there is a loop
boolean hasCycle(Node head) {
for (Node s = head, f = head; f != null && f.next != null; ) {
s = s.next; f = f.next.next;
if (s == f) return true;
}
return false;
}
// Dummy head: no special case for removing/inserting at the front
Node dummy = new Node(0, head), cur = dummy;
while (cur.next != null) { if (cur.next.val == target) cur.next = cur.next.next; else cur = cur.next; }
head = dummy.next; Monotonic stack and deque patterns
// Next greater element: keep a stack of indexes whose answer is still unknown
int[] next = new int[a.length];
Arrays.fill(next, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
while (!st.isEmpty() && a[st.peek()] < a[i]) next[st.pop()] = a[i];
st.push(i);
}
// Sliding-window maximum: the deque holds indexes in decreasing value order
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < a.length; i++) {
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst(); // left the window
while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast(); // smaller values are useless
dq.offerLast(i);
if (i >= k - 1) result.add(a[dq.peekFirst()]);
} Data structure checklist
- List the operations you need and how often; pick the structure that makes the frequent ones cheap.
- Prefer ArrayList, ArrayDeque, HashMap and PriorityQueue from the JDK in production code.
- Make node classes
private staticnested classes. - Keep a size field instead of counting nodes every time.
- Use a dummy head node to simplify linked-list edge cases.
- Always keep a visited set when traversing graphs.
- Test empty, single-element and duplicate-key cases.