Java Map實現類面試題

HashMap

Q1: HashMap的實現原理是什么？

HashMap基于哈希表實現，使用數組+鏈表+紅黑樹（Java 8）的數據結構。

public class HashMapPrincipleExample {// 模擬HashMap的基本結構public class SimpleHashMap<K, V> {private static final int DEFAULT_CAPACITY = 16;private static final float LOAD_FACTOR = 0.75f;private Entry<K, V>[] table;private int size;private static class Entry<K, V> {K key;V value;Entry<K, V> next;Entry(K key, V value, Entry<K, V> next) {this.key = key;this.value = value;this.next = next;}}@SuppressWarnings("unchecked")public SimpleHashMap() {table = new Entry[DEFAULT_CAPACITY];}public V put(K key, V value) {int hash = hash(key);int index = indexFor(hash, table.length);// 遍歷鏈表for (Entry<K, V> e = table[index]; e != null; e = e.next) {if (e.key.equals(key)) {V oldValue = e.value;e.value = value;return oldValue;}}// 添加新節點addEntry(hash, key, value, index);return null;}private void addEntry(int hash, K key, V value, int index) {Entry<K, V> e = table[index];table[index] = new Entry<>(key, value, e);if (++size > table.length * LOAD_FACTOR) {resize(2 * table.length);}}private int hash(K key) {return key == null ? 0 : key.hashCode();}private int indexFor(int hash, int length) {return hash & (length - 1);}}
}

Q2: HashMap的擴容機制是怎樣的？

public class HashMapResizeExample {public void demonstrateResize() {HashMap<String, Integer> map = new HashMap<>();// 1. 默認初始容量16，負載因子0.75System.out.println("初始容量：" + 16);System.out.println("擴容閾值：" + (16 * 0.75));// 2. 指定初始容量HashMap<String, Integer> customMap = new HashMap<>(32);// 3. 模擬擴容過程for (int i = 0; i < 13; i++) {map.put("key" + i, i);System.out.println("當前大小：" + map.size());}}// 擴容時的數據遷移public void demonstrateRehash() {HashMap<String, Integer> map = new HashMap<>(4);map.put("A", 1); // index = hash("A") & (4-1)map.put("B", 2);map.put("C", 3);// 擴容后 index = hash("A") & (8-1)}
}

TreeMap

Q3: TreeMap的實現原理是什么？

TreeMap基于紅黑樹實現，可以保證鍵的有序性。

public class TreeMapPrincipleExample {// 1. 自然排序public void naturalOrdering() {TreeMap<String, Integer> map = new TreeMap<>();map.put("C", 3);map.put("A", 1);map.put("B", 2);// 按鍵的自然順序排序for (Map.Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + ": " + entry.getValue());}}// 2. 自定義排序public void customOrdering() {TreeMap<Person, String> map = new TreeMap<>((p1, p2) -> {int ageCompare = Integer.compare(p1.getAge(), p2.getAge());if (ageCompare != 0) return ageCompare;return p1.getName().compareTo(p2.getName());});map.put(new Person("Tom", 20), "Student");map.put(new Person("Jerry", 18), "Student");map.put(new Person("Bob", 20), "Teacher");}// 3. 范圍操作public void rangeOperations() {TreeMap<Integer, String> map = new TreeMap<>();for (int i = 1; i <= 10; i++) {map.put(i, "Value" + i);}// 獲取子MapMap<Integer, String> subMap = map.subMap(3, 7);// 獲取小于等于key的EntryMap.Entry<Integer, String> floorEntry = map.floorEntry(5);// 獲取大于等于key的EntryMap.Entry<Integer, String> ceilingEntry = map.ceilingEntry(5);}
}

LinkedHashMap

Q4: LinkedHashMap的特點是什么？

LinkedHashMap在HashMap的基礎上維護了一個雙向鏈表，可以保持插入順序或訪問順序。

public class LinkedHashMapExample {// 1. 插入順序public void insertionOrder() {LinkedHashMap<String, Integer> map = new LinkedHashMap<>();map.put("A", 1);map.put("B", 2);map.put("C", 3);// 遍歷時保持插入順序}// 2. 訪問順序public void accessOrder() {LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);  // accessOrder = truemap.put("A", 1);map.put("B", 2);map.put("C", 3);map.get("A");  // 訪問A，A會移到鏈表末尾// 遍歷時A會在最后}// 3. LRU緩存實現public class LRUCache<K, V> extends LinkedHashMap<K, V> {private final int capacity;public LRUCache(int capacity) {super(capacity, 0.75f, true);this.capacity = capacity;}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}}
}

ConcurrentHashMap

Q5: ConcurrentHashMap的實現原理是什么？

ConcurrentHashMap在Java 8中使用CAS和synchronized來保證并發安全。

public class ConcurrentHashMapExample {// 1. 基本使用public void basicUsage() {ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();map.put("A", 1);map.putIfAbsent("B", 2);map.computeIfAbsent("C", key -> 3);}// 2. 原子操作public void atomicOperations() {ConcurrentHashMap<String, AtomicInteger> map = new ConcurrentHashMap<>();map.putIfAbsent("counter", new AtomicInteger(0));// 線程安全的計數器map.get("counter").incrementAndGet();}// 3. 并發迭代public void concurrentIteration() {ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();// 填充數據for (int i = 0; i < 100; i++) {map.put("key" + i, i);}// 并發遍歷map.forEach(8, (key, value) -> System.out.println(key + ": " + value));}
}

Q6: 如何選擇合適的Map實現類？

public class MapSelectionExample {public void demonstrateUsage() {// 1. 一般用途，非線程安全Map<String, Object> hashMap = new HashMap<>();// 2. 需要有序Map<String, Object> treeMap = new TreeMap<>();// 3. 需要記住插入順序Map<String, Object> linkedHashMap = new LinkedHashMap<>();// 4. 需要線程安全Map<String, Object> concurrentMap = new ConcurrentHashMap<>();// 5. 需要同步Map<String, Object> synchronizedMap = Collections.synchronizedMap(new HashMap<>());// 6. 實現LRU緩存Map<String, Object> lruCache = new LinkedHashMap<>(16, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size() > 100; // 限制大小為100}};}// 使用場景示例public void usageScenarios() {// 1. 頻繁插入刪除HashMap<String, Object> hashMap = new HashMap<>();// 2. 需要排序TreeMap<String, Object> treeMap = new TreeMap<>();// 3. 需要保持插入順序LinkedHashMap<String, Object> linkedHashMap = new LinkedHashMap<>();// 4. 高并發場景ConcurrentHashMap<String, Object> concurrentMap = new ConcurrentHashMap<>();}
}

面試關鍵點

1. 理解HashMap的底層實現
2. 掌握HashMap的擴容機制
3. 了解TreeMap的排序原理
4. 熟悉LinkedHashMap的特點
5. 理解ConcurrentHashMap的并發機制
6. 掌握Map的選擇原則
7. 注意線程安全問題
8. 理解性能和內存消耗