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和HashSet
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<Person, String> treeMap = new TreeMap<>(new Comparator<Person>() {
@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<Person, 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方法，并且判断了一下返回值以确保是否有重复元素。下面是源码截图：
HashSet的add方法
也就是说在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的话会先数组扩容，而不是转化红黑树)时，将链表转化为红黑树，以减少搜索时间。
jdk1.8的数据结构
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的时候将数据分为一段一段存储，然后给每一段数据配一把锁。当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问
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包下的并发集合。
本篇笔记就整理到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！
网友评论