Java Map实现类面试题

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. 理解性能和内存消耗