Java集合知识进阶讲解第二部分

未分类 2周前程序员胖胖胖虎阿

21 0 0

文章标题：

Java集合知识进阶讲解第二部分

文章内容：

Map集合

1.1. 快速遍历Map的多种方式

可以通过不同方法来遍历Map集合。例如，方式一是利用entrySet()结合forEach循环：

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

方式二是使用keySet()配合forEach循环，通过键获取对应值进行遍历：

for (String key : map.keySet()) {
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

方式三是运用forEach方法搭配Lambda表达式来遍历：

map.forEach((key, value) -> 
    System.out.println("Key: " + key + ", Value: " + value)
);

方式四可借助迭代器，无论是通过entrySet()还是keySet()获取迭代器进行遍历。比如通过entrySet()获取迭代器的示例：

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

通过keySet()获取迭代器的示例：

Iterator<String> keyIterator = map.keySet().iterator();
while (keyIterator.hasNext()) {
    String key = keyIterator.next();
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

方式五是使用Stream流API来遍历，有普通流和并行流两种情况。普通流示例：

map.entrySet().stream()
    .forEach(entry -> 
        System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue())
    );

并行流示例（大数据量时可能提升性能）：

map.entrySet().parallelStream()
    .forEach(entry -> 
        System.out.println("[Parallel] Key: " + entry.getKey() + ", Value: " + entry.getValue())
    );

1.2. HashMap的实现原理

在JDK1.7及之前，HashMap底层数据结构是数组与链表的组合。当要添加键值对时，先计算key的哈希值，再通过hash & (数组长度-1)（等同于hash%数组长度，位运算更高效）确定数组索引位置。若该索引位置为空，就创建Entry对象存入键值对等信息，并增加HashMap修改次数；若不为空，则通过链表将其链接到同一哈希桶中（需注意链表过长会使查询效率降为O(n)）。

JDK1.8之后，HashMap底层变为数组加链表或红黑树的结构。添加元素时，先算哈希值找索引位置。若索引为空，创建Node对象存入相关信息并增加修改次数；若不为空，查看数据结构。若是链表（采用尾插法），添加后判断链表长度是否≥8，若此时数组长度≥64，链表会转成红黑树以提升查询和添加效率（从O(n)到O(log n)）；若数组长度不满足，就进行扩容操作。

1.3. HashMap的扩容机制

HashMap默认数组长度为16（2的4次方），可指定。扩容时机有两种：一是链表长度≥8但数组长度<64时，将数组长度扩为原来两倍；二是实际键值对长度≥数组长度×负载因子（默认0.75）时，将数组长度扩为原来两倍。

扩容时，先计算新数组长度（旧数组长度的两倍），若不满足扩容要求则继续以两倍扩容直到满足。创建新数组后，遍历旧数组对象，取出哈希值。JDK1.7用重新再哈希，分布均匀但性能低；JDK1.8用hash & (新数组长度-1)运算，结果≥旧数组长度时，新数组索引为旧数组长度+原索引长度，否则用原索引长度，最后让HashMap的数组指向新数组。因数组长度是2的幂次，将数组长度减一可形成特定二进制形式，与哈希值&运算能判断索引是否需改变。

1.4. HashMap在多线程下的问题

JDK1.7多线程下会出现Entry链死循环和数据丢失问题。JDK1.8解决了Entry死循环和数据丢失，但出现put方法数据覆盖问题。

JDK1.7出现问题原因：链表添加用头插法，多线程并发扩容易导致死循环和数据丢失。JDK1.8解决方式是将头插法改为尾插法保证顺序。JDK1.8出现put覆盖问题是因HashMap线程不安全，并发put会覆盖数据。解决方法是加锁或用线程安全集合。

1.5. 解决哈希冲突的方法

方法一：链接法，用链表等存储冲突键值对，链接到同一哈希桶。

方法二：开放寻址法，在哈希表中找其他位置存键值对，常见线性探测、二次探测、双重散列等。

方法三：再哈希法，用另一哈希算法直到找到存储位置。

方法四：哈希桶扩容，冲突过多时动态增加哈希桶数据并重新分配键值对，减少冲突概率。

1.6. HashMap的put过程

首先计算key哈希值找数组索引位置，判断索引是否为空。为空则添加键值对（创建entry或node对象）；不为空则通过链表或红黑树链接到同一哈希桶。若用链表，判断链表长度是否≥8。不满足则跳转后续步骤；满足则判断数组长度是否≥64。满足则链表转红黑树提效；不满足则扩容数组。接着看实际键值对长度是否≥数组长度×负载因子（0.75），满足则扩容数组，不满足则结束put过程。

1.7. HashMap的key使用类型

通常用String类型，因其不可变，修改时创建新对象，保证key唯一性和安全性。

1.8. HashMapkey可为null的原因

底层哈希运算时先判断key是否为null，若是则hash赋值为0，不进行哈希运算。因key唯一，只能有一个key为null，value无此限制。需注意，若HashMap未初始化，给key赋null会出现空指针异常。

1.9. HashMap不采用平衡二叉树的原因

平衡二叉树追求过度平衡，插入删除易破坏平衡，需左旋右旋维护，成本高。红黑树不追求过度平衡，最长路径不超最短路径两倍，牺牲部分查询效率降低维护成本，插入删除不易破坏规则。

1.10. HashMap的负载因子

负载因子=实际键值对长度/数组长度，默认0.75。值高时数组内存使用率高，哈希冲突概率大；值低时数组空间利用率低，需频繁扩容，影响性能。

1.11. HashTable介绍

HashTable底层是数组加链表，数组初始容量11，每次扩容2n+1。用synchronized锁方法保证线程安全，但锁整个方法性能低。

1.12. ConcurrentHashMap的原理

JDK1.7用分段锁，将数据分段加锁，实现并发安全且高效。JDK1.8用CAS与volatile或synchronized加锁。