JavaGuide知识点整理——集合常见知识点（下）

程序员 · 2024-9-18 12:32:03

Map接口

HashMap和Hashtable的区别

线程是否安全：HashMap是非线程安全的，Hashtable是线程安全的，由于Hashtable内部的方法根本都颠末synchronized修饰(这是很老的一个实现，假如现在必要包管线程安全的话推荐利用ConcurrentHashMap)
服从：由于线程安全的题目，HashMap要比Hashtable的服从高一些，别的Hashtable根本被镌汰，不发起在代码中利用。
对Null key和Null value的支持：HashMap可以存储null的key和value。但是null作为键只能有一个。null作为值可以有多个。Hashtable不答应有null键和null值，否则会抛出空指针非常。
初始容量巨细和每次扩充容量巨细差别：
- 创建时假如不指定容量初始值，Hashtable默认的初始巨细为11，之后每次扩容容量变为原来的2n+1.HashMap默认初始化巨细16.之后每次扩容，容量都变为包涵的2倍。
- 创建时假如给定了容量初始值，Hashtable会直接利用你给定的巨细。而HashMap会将其扩容为2的幂次方发小。也就是说HashMap永世利用2的幂次方作为哈希表的巨细。
底层数据结构：JDK1.8以后HashMap在办理哈希辩论时有了较大的厘革，当链表长度大于阈值(默认8)(将链表转化成红黑树前会判断，假如当前数组长度小于64，那么会先辈性数组扩容，而不是转化成红黑树)时，会将链表转化成红黑树，以淘汰搜刮时间，Hashtable没有这样的机制。

HashMap和HashSet的区别

HashSet的源码中很清楚的写的：HashSet的底层是基于HashMap实现的。HashSet的源码非常少，由于除了Clone(),writeObject(),readObject()等是HashSet本身不得不实现的以外，其他的方法都是直接调用HashMap中的方法.

HashMap和TreeMap的区别

TreeMap和HashMap都继续自AbstractMap，但是必要留意的是TreeMap它还实现了NavigableMap接口和SortedMap接口。
实现了NavigableMap接口让TreeMap有了对集合内元素的搜刮的本事。
实现SortedMap接口让TreeMap有了对集合中的元素根据键排序的本事。默认是按照key的升序排序，不外我们也可以指定排序的比力器。
/** * @author shuang.kou * @createTime 2020年06月15日 17:02:00 */public class Person { private Integer age; public Person(Integer age) { this.age = age; } public Integer getAge() { return age; } public static void main(String[] args) { TreeMap<

erson, String> treeMap = new TreeMap<>(new Comparator<

erson>() { @Override public int compare(Person person1, Person person2) { int num = person1.getAge() - person2.getAge(); return Integer.compare(num, 0); } }); treeMap.put(new Person(3), "person1"); treeMap.put(new Person(18), "person2"); treeMap.put(new Person(35), "person3"); treeMap.put(new Person(16), "person4"); treeMap.entrySet().stream().forEach(personStringEntry -> { System.out.println(personStringEntry.getValue()); }); }}这个代码的实行可以看出TreeMap已经按年事升序来分列了。固然也可以用lambda来实现排序：
TreeMap<

erson, String> treeMap = new TreeMap<>((person1, person2) -> { int num = person1.getAge() - person2.getAge(); return Integer.compare(num, 0);});综上，相比于HashMap，TreeMap重要是多了对集合中的元素根据键值排序的本事以及对集合内元素的搜刮的本事。
HashSet怎样查抄重复

据说java8之前的版本：把对象参加HashSet的时候，会先盘算对象的hashcode值来判断对象参加的位置，同事也会与其他参加的对象的hashCode值比力，假如没有相同的，HashSet会假设对象没有重复出现，假如发现有hashCode值相同的对象，会调用equals()方法来查抄hashCode相当的对象是否真的相同。假如两者相同说明有重复，不会参加乐成。
而在JDK1.8中，HashSet的add方法只是简朴的调用了一下HashMap的put方法，而且判断了一下返回值以确保是否有重复元素。下面是源码截图：

也就是说在1.8中，无论HashSet中是否已经存在了某元素，HashSet都会直接插入。只是会在add方法的返回值处告诉我们插入前是否已经存在相同的元素。
HashCode与equals的相干规定：

假如两个对象相当，则hashCode肯定也是相同的
假如两个对象相当，equals判断肯定是true
两个对象有相同的hashCode值，他们也不肯定是相当的
综上，equals方法被覆盖过，则hashCode方法也必须被覆盖。
hashCode默认行为是对堆上的对象产生独特值，假如没有重写hashCode，则该class的两个对象无论怎样都不会相当。

HashMap的底层实现

JDK1.8之前HashMap底层是数组和链表联合在一起利用，也就是链表散列。HashMap通过key的hashCode颠末扰动函数处理后得到hash值，然后通过(n-1)&hash判断当前元素存放的位置(这里n是数组的长度)。假如当前位置存在元素的话，就判断该元素与要存入的元素的hash值以及key是否相同，假如相同的话直接覆盖，不相同就通过拉链法办理辩论。
所谓扰动函数指的就是HashMap的hash方法，利用哈希方法也就是扰动函数是为了防止一些实现比力差的hashCode方法，从而淘汰哈希碰撞。
所谓“拉链法”就是：将链表和数组相联合，也就是说创建一个链表数组，数组中每一个格就是一个链表，若碰到哈希辩论，将辩论的值加到链表中即可。

相比于之前的版本，jdk1.8之后在办理哈希辩论的时候有了较大的厘革：当链表长度大于阈值(默认是8.但是将链表转化红黑树前会判断当前数组长度，数组小于64的话会先数组扩容，而不是转化红黑树)时，将链表转化为红黑树，以淘汰搜刮时间。

TreeMap,TreeSet,以及1.8以后的HashMap底层都用到了红黑树，红黑树就是为了办理二叉查找树的缺陷，由于二叉查找树某些环境下会退化成一个线性结构。
下图可以看做是一个简朴的HashMap添加元素的步调：

HashMap的长度为什么是2的幂次方

为了能让HashMap存取高效，只管淘汰碰撞，也就是只管把数据分配匀称，我们上面也讲到了Hash值的范围-2147483648 到 2147483647，前后加起来40亿的映射空间，只要哈希函数映射的比力匀称疏松，一样寻常应该是很难出现碰撞的，但是题目是一个40亿长度的数组内存是放不下的。所以这个散列值不能直接拿来用。用之前还要对数组的长度取模运算，得到的余数才华用来要存放的位置也就是对应的数组下标。这个数组下标的盘算公式是(n-1)&hash。这也就表明了为什么HashMap的长度为什么是2的幂次方。
这里有一个公式：在length是2的n次方的时候：hash%length==hash&(length-1)
这个公式创建。
我们上面说的对数组长度取模，之所以能演酿成(n-1)&hash也是为了让这个公式创建。由于这样二进制位操纵比用%服从要高的多。
HashMap多线程操纵死锁题目

重要缘故原由在于并发下的Rehash会造成元素之间形成一个循环链表。不外JDK1.8后办理了这个题目，但是照旧不发起多线程的环境下利用HashMap，由于多线程下利用还会有其他题目，比如数据丢失等，并发环境发起利用ConcurrentHashMap.
HashMap有哪几种常见的遍历方式、

从大方向来说有四种：

迭代器方式遍历(Iterator)
For Each方式遍历
Lambda表达式遍历
streams API遍历

但是美中范例又有差别的实现，所以一共有七中遍历方式：

利用迭代器（Iterator）EntrySet 的方式举行遍历；
利用迭代器（Iterator）KeySet 的方式举行遍历；
利用 For Each EntrySet 的方式举行遍历；
利用 For Each KeySet 的方式举行遍历；
利用 Lambda 表达式的方式举行遍历；
利用 Streams API 单线程的方式举行遍历；
利用 Streams API 多线程的方式举行遍历。

下面是简朴是利用代码：
public static void main(String[] args) { Map<Integer,String> map = new HashMap<>(); map.put(1,"f"); map.put(2,"s"); map.put(3,"t"); // 第一种遍历方式entrySet Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Integer, String> entry = iterator.next(); System.out.println(entry.getKey()+":"+entry.getValue()); } //第二种遍历方式keySet Iterator<Integer> iterator1 = map.keySet().iterator(); while (iterator1.hasNext()) { Integer key = iterator1.next(); System.out.println(key+":"+map.get(key)); } // 第三种遍历方式For Each EntrySet for (Map.Entry<Integer, String> entry : map.entrySet()) { System.out.println(entry.getKey()+":"+entry.getValue()); } //第四种遍历方式For Each keySet for (Integer key : map.keySet()) { System.out.println(key+":"+map.get(key)); } // 第五种遍历方式lambda map.forEach((key, value) -> { System.out.println(key+":"+value); }); // 第六种遍历方式Streams API 单线程 map.entrySet().stream().forEach((entry) -> { System.out.println(entry.getKey()+":"+entry.getValue()); }); // 第七种遍历方式Streams API 多线程 map.entrySet().parallelStream().forEach((entry) -> { System.out.println(entry.getKey()+":"+entry.getValue()); }); }ConcurrentHashMap和Hashtable的区别

二者的重要区别表现在实现线程安全的方式差别

底层数据结构:jdk1.7的ConcurrentHashMap底层接纳分段的数组+链表实现，JDK1.8接纳的数据结构和HashMap一样，数组+链表/红黑树.Hashtable1.8之前和HashMap的底层数据结构类似都是数组+链表。
实现线程安全的方式：在JDK1.7的时候，ConcurrentHashMap(分段锁)对整个桶数组举行了分割分段，每一把锁只锁容器中一部门数据，多线程访问容器中差别数据段的数据就不会存在竞争。提高并发访问率。到了JDK1.8已经摒弃了分割分段的概念。直接用Node数组+链表+红黑树的数据结构来实现，并发控制利用synchronized和CAS来操纵。整个看起来就像是优化过且线程安全的HashMap。
Hashtable(同一把锁)利用synchronized来包管线程安全，服从非常低，当一个线程访问同步方法时，其他线程也访问同步方法可能进入壅闭大概轮询状态。如利用put添加元素，另一个线程不能利用put，而且也不能利用get，竞争越激烈服从越低。

ConcurrentHashMap线程安全的详细实现方式/底层详细实现

JDK1.7

JDK1.7的时候将数据分为一段一段存储，然后给每一段数据配一把锁。当一个线程占用锁访问此中一个段数据时，其他段的数据也能被其他线程访问

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构构成。
Segment继续了ReentrantLock，所以Segment是一种可重入锁，扮演锁的角色，HashMap用于存储键值对数据。
一个ConcurrentHashMap里包罗一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构。一个Segment包罗一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment保卫一个HashEntry数组里的元素，当对HashEntry数组的数据举行修改时，必须先获取对应的Segment的锁。
JDK1.8

ConcurrentHashMap取消了Segment分段锁，接纳CAS和synchronized来包管并发安全。数据结构和HashMap1.8的结构类似。数组+链表/红黑树。java8在链表长度超过一个阈值(8)时将链表转化成红黑树。
synchronized只锁定当前链表大概红黑树的首节点。这样只要hash不辩论，就不会产生并发，服从大大的提拔了。
Collections工具类

Collections工具类常用方法：

排序
查找更换操纵
同步控制

排序操纵

void reverse(List list)//反转void shuffle(List list)//随机排序void sort(List list)//按自然排序的升序排序void sort(List list, Comparator c)//定制排序，由Comparator控制排序逻辑void swap(List list, int i , int j)//交换两个索引位置的元素void rotate(List list, int distance)//旋转。当distance为正数时，将list后distance个元素团体移到前面。当distance为负数时，将 list的前distance个元素团体移到反面查找，更换操纵

int binarySearch(List list, Object key)//对List举行二分查找，返回索引，留意List必须是有序的int max(Collection coll)//根据元素的自然顺序，返回最大的元素。类比int min(Collection coll)int max(Collection coll, Comparator c)//根据定制排序，返回最大元素，排序规则由Comparatator类控制。类比int min(Collection coll, Comparator c)void fill(List list, Object obj)//用指定的元素代替指定list中的全部元素int frequency(Collection c, Object o)//统计元素出现次数int indexOfSubList(List list, List target)//统计target在list中第一次出现的索引，找不到则返回-1，类比int lastIndexOfSubList(List source, list target)boolean replaceAll(List list, Object oldVal, Object newVal)//用新元素更换旧元素同步控制

Collections提供了多个synchronizedXxx()方法，该方法可以将指定集合包装成线程同步的集合，从而办理多线程并发访问集适时的线程安全题目。
我们知道HsahSet,TreeSet，ArrayList,LinkedList,HashMap,TreeMap都是线程不安全的。Collections提供了多个静态方法可以把他们包装秤线程安全的集合。
synchronizedCollection(Collection<T> c) //返回指定 collection 支持的同步（线程安全的）collection。synchronizedList(List<T> list)//返回指定列表支持的同步（线程安全的）List。synchronizedMap(Map<K,V> m) //返回由指定映射支持的同步（线程安全的）Map。synchronizedSet(Set<T> s) //返回指定 set 支持的同步（线程安全的）set。不外最好不消下面这些方法，由于服从非常低，必要线程安全的集合范例时最好用JUC包下的并发集合。
本篇条记就整理到这里，假如稍微帮到你了记得点个喜好点个关注，也祝各人工作顺顺遂利！

JavaGuide知识点整理——集合常见知识点（下）

所属分类: 问答交流

新帖推荐: 30日

推荐作品