Appearance
记录一下集合相关的概念，对于 Java 集合基础概念的一个补充
什么是 fail-fast机制，讲述一下他和 fail-safe 的异同。
错误检查机制
- 快速失败 fail-fast
- 当方法检测到对象的并发修改，但不允许这种修改时就抛出该异常
- fail-safe 机制
- fail-safe 任何对集合结构的修改都会在一个复制的集合上进行，因此不会抛出ConcurrentModificationException
fail-fast 解决方法
- 方案一：在遍历过程中所有涉及到改变modCount 值的地方全部加上synchronized 或者直接使用 Collection synchronizedList，这样就可以解决问题，但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。
- 方案二：使用CopyOnWriteArrayList 替换 ArrayLIst，推荐使用该方案（即fail-safe）。
fail-fast和 fail-safe 的区别
| Fail Fast Iterator | Fail Safe Iterator | |
|---|---|---|
| Throw ConcurrentModification Exception | Yes | No |
| Clone object | No | Yes |
| Memory Overhead | No | Yes |
| Examples | HashMap,Vector,ArrayList,HashSet | CopyOnWriteArrayList, ConcurrentHashMap |
通过实现 Comparable 或者 Comparator 接口来进行排序
一种情况是集合类本身自带排序功能，如前面说过的TreeSet、SortedSet、SortedMap等，
另一种就是本身不带排序功能，我们通过为需要排序的类实现 Comparable 或者 Comparator 接口来实现。
先来看两个例子，一个是实现Comparable的，一个是实现 Comparator 的
（1）实现Comparable的：
package com.xtfggef.list.test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
@SuppressWarnings("unchecked")
public class ComparableTest {
public static void main(String[] args) {
List<User> users = new ArrayList();
users.add(new User("egg", 23));
users.add(new User("niu", 22));
users.add(new User("qing", 28));
Collections.sort(users);
for (User user : users) {
System.out.println(user.getName() + " " + user.getAge());
}
}
}
@SuppressWarnings("unchecked")
class User implements Comparable {
private String name;
private int age;
public User(String name, int age) {
super();
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Object o) {
return this.age - ((User) o).getAge();
}
}（2）下面是实现Comparator接口的：
package com.xtfggef.comparator.test;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class ComparatorTest {
public static void main(String[] args) {
List<User> users = new ArrayList();
users.add(new User("egg", 21));
users.add(new User("niu", 22));
users.add(new User("gg", 29));
UserComparator comparator = new UserComparator();
Collections.sort(users, comparator);
for (User user : users) {
System.out.println(user.getUsername() + " " + user.getAge());
}
}
}
class User {
private String username;
private int age;
public User(String username, int age) {
super();
this.username = username;
this.age = age;
}
public String getUsername() {
return username;
}
public void setUsername(String username) {
this.username = username;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
class UserComparator implements Comparator<User> {
@Override
public int compare(User user1, User user2) {
int age1 = user1.getAge();
int age2 = user2.getAge();
if (age1 < age2) {
return 1;
}
return 0;
}
}👆 上面这种 Comparator 实现这个接口的时候， 👉 Comparator是一个泛型接口，所以在实现Comparator接口时，类的泛型类型需要指定具体类型，以避免类型擦除带来的问题。
通过上面的这两个小例子，我们可以看出，Comparator和Comparable用于不同的场景，实现对对象的比较从而进行排序。
总结为：
相同点： 二者都可以实现对象的排序，不论用 Arrays的方法还是用 Collections的sort()方法。
不同点：
（1）实现Comparable接口的类，似乎是预先知道该类将要进行排序，需要排序的类实现Comparable接口，是一种“静态绑定排序”。
（2）实现Comparator的类不需要，设计者无需事先为需要排序的类实现任何接口。
（3）Comparator接口里有两个抽象方法compare()和equals()，而Comparable接口里只有一个方法：compareTo()。
（4）Comparator接口无需改变排序类的内部，也就是说实现算法和数据分离，是一个良好的设计，是一种“动态绑定排序”。
（5）Comparator接口可以使用多种排序标准，比如升序、降序等。
Set集合是如何保证对象不重复的？
HashSet 的底层采用HashMap来存放数据, 他执行添加元素操作的时候是将元素作为 Map 的Key；
HashMap保证key的不重复性，对于重复的key，HashMap会根据参数onlyIfAbsent的设置和原value是否为空两个条件来判断是否替换新value，
但要注意的是，对于HashSet，这个value只是个空的Object类的对象，没有任何实际作用，HashSet中的元素实际上是存储在key上的。针对重复的key，HashMap只有对于value的处理，并不会替换key，因此在HashSet中加入相同元素不会覆盖。
源码相关内容：
HashSet 的添加方法
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}hashmap 的 put 方法
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());//----------1----------
int i = indexFor(hash, table.length);//-----------2---------
for (Entry e = table[i]; e != null; e = e.next) {//-----------3---------
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}//------------------4--------------------
modCount++;
addEntry(hash, key, value, i);
return null;
}当向HashMap中添加元素的时候，
- 首先计算元素的hashcode值，然后根据1处的代码计算出Hashcode的值，
- 再根据2处的代码计算出这个元素的存储位置，
- 如果这个位置为空，就将元素添加进去；
- 如果不为空，则看3-4的代码，遍历索引为i的链上的元素，如果key重复，则替换并返回oldValue值。
总结：结果向HashSet中加入相同元素不会进行覆盖。因为HashSet底层使用HashMap实现，元素存在HashMap的key中。在HashMap中，多次put相同的key，只会覆盖value，而不存在key的情况。
使用for循环删除元素陷阱
先来看看下面这个程序：
public class Test {
public static void main(String[] args) {
List<String> list = new LinkedList<String>();
list.add("A");
list.add("B");
list.add("C");
for(int i=0; i<list.size(); i++){
list.remove(i);
}
for(String item:list){
System.out.println(item);
}
}
}可以先猜猜这个程序输出什么？
按我们的思路，应该是输不出什么，但是执行它，输出的却是：B。
分析下这个程序，当第一步remove完后，集合内还剩2个元素，此时i为1，而list.size()的值为2，从0开始的话，i为1时，正好指向第二个元素，也就是说当remove完A后，直接就跳到C，将B漏了。
解决办法：
public class Test {
public static void main(String[] args) {
List<String> list = new LinkedList<String>();
list.add("A");
list.add("B");
list.add("C");
for(int i=0; i<list.size(); i++){
list.remove(i);
i -= 1;//每次删除完后，i减少1
}
for(String item:list){
System.out.println(item);
}
}
}讲述一下 length、length()、size() 的区别。
- java 中的
length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了 length 这个属性. - java 中的
length()方法是针对字符串说的,如果想看这个字符串的长度则用到length()这个方法. - java 中的
size()方法是针对泛型集合说的,如果想看这个泛型有多少个元素,就调用此方法来查看!
在 HashMap 中，为什么不一下子把整个链表变为红黑树呢
为什么非要等到链表的长度大于等于8的时候，才转变成红黑树？
（1）构造红黑树要比构造链表复杂，在链表的节点不多的时候，从整体的性能看来， 数组+链表+红黑树的结构可能不一定比数组+链表的结构性能高。就好比杀鸡焉用牛刀的意思。
（2）HashMap频繁的扩容，会造成底部红黑树不断的进行拆分和重组，这是非常耗时的。因此，也就是链表长度比较长的时候转变成红黑树才会显著提高效率。