Java Map实现类面试题

HashMap

Q1: HashMap的实现原理是什么？

HashMap基于哈希表实现，使用数组+链表+红黑树（Java 8）的数据结构。

java">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的扩容机制是怎样的？

java">public class HashMapResizeExample {
    public void demonstrateResize() {
        HashMap<String, Integer> map = new HashMap<>();
        
        // 1. 默认初始容量16，负载因子0.75
        System.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基于红黑树实现，可以保证键的有序性。

java">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);
        }
        
        // 获取子Map
        Map<Integer, String> subMap = map.subMap(3, 7);
        // 获取小于等于key的Entry
        Map.Entry<Integer, String> floorEntry = map.floorEntry(5);
        // 获取大于等于key的Entry
        Map.Entry<Integer, String> ceilingEntry = map.ceilingEntry(5);
    }
}

LinkedHashMap

Q4: LinkedHashMap的特点是什么？

LinkedHashMap在HashMap的基础上维护了一个双向链表，可以保持插入顺序或访问顺序。

java">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 = true
        map.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;
        }
        
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;
        }
    }
}

ConcurrentHashMap

Q5: ConcurrentHashMap的实现原理是什么？

ConcurrentHashMap在Java 8中使用CAS和synchronized来保证并发安全。

java">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实现类？

java">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) {
                @Override
                protected 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<>();
    }
}