1.比较器
1.1 作用
java中定义的运算符，大多数只适用于基本数据类型。因为引用数据类型的对象不能直接使用运算符进行比较，所以java提供了比较器(内部还是对基本数据类型进行的比较)。
1.2 两种实现对象排序的方式
java.lang.Comparable：自然排序
java.lang.Comparator：定制排序
1.2.1 两者区别
Comparable接口的比较规则是在实现类中重写的，此类中所有的对象都可以使用；
Comparator接口的比较规则是在排序时临时定义的；
1.3 Comparable接口
1.3.1 概述
- Comparable接口中有一个抽象方法
public int compareTo(T o);，像String，包装类都重写了compareTo方法，用于对象之间的比较。 - 如果想要对自定义类的对象进行默认排序，必须实现Comparable接口，然后重写compareTo方法,在compareTo方法中进行属性的比较；
- 实现Comparable接口的对象列表（和数组）可以通过
Collections.sort或Arrays.sort进行自动排序； - 重写规则得到的结果是升序，如果想要降序，取相反数。
1.3.2 重写compareTo(T o)方法的规则
如果当前对象大于形参对象o，返回正整数；
如果当前对象小于形参对象o，返回负整数；
如果两者相等，返回0；
1.3.3 缺点
只能在类中重写compareTo方法，类中所有的对象使用相同比较方式，不能在具体对象中重写，有局限性。
1.3.4 实例
方式1：直接进行属性的比较
方式2：可以调用相应的包装类中的compare方法
@Override
public int compareTo(Object o) {
if (o instanceof Person) {
Person o1 = (Person) o;
return this.age > o1.age ? 1 : (this.age == o1.age) ? 0 : -1;
return Integer.compare(this.age, o1.age);
}
throw new RuntimeException("传入类型不正确");
}
1.4 Comparator接口
1.4.1 概述
- 如果类中没有实现Comparable接口，或者类中实现了Comparable接口但不适合当前操作且不想修改类中代码，可以考虑使用 Comparator 的对象来排序。
- 一般使用(匿名)内部类，需要重写Comparator 接口中的compare(Object o1,Object o2)方法，重写规则与compareTo()一致。
- 创建匿名内部类当作排序方法的形参传入，排序规则只可以使用一次。
1.4.2 实例
p是一个Person类型的数组
// 简化前：满足重写规则，默认为升序，如果想要降序，取相反数
Collections.sort(characters, new Comparator<Character>() {
@Override
public int compare(Character o1, Character o2) {
if (o1 - o2 > 0) {
return 1;
} else if (o1 - o2 < 0) {
return -1;
} else {
return 0;
}
}
});
// 简化后：因为重写规则中o1小于o2时，需要返回负数，而此时o1-o2也是负数；同理o1大于或是等于o2时，返回值也和o1-o2的结果一致，所以就使用o1-o2的结果来充当返回值。
Arrays.sort(p, new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
});
2.System类、Math类、BigInteger与BigDecimal
3.枚举类
3.1 概述
- 如果一个类只有有限个确定的对象，那么可以使用枚举类。
- 如果需要定义一组常量时，强烈建议使用枚举类。
- 若枚举只有一个对象, 则可以作为一种线程安全的单例模式的实现方式。
3.1.1 一些例子
星期：Monday(星期一)、…、Sunday(星期天)
性别：Man(男)、Woman(女)
季节：Spring(春节)…Winter(冬天)
3.2 jdk1.5之前的定义方式
class Season{
// 1. 声明枚举类的属性：private final
private final String name;
private final int age;
// 2. 私有化构造器，并在构造器中初始化对象的属性
private Season(String name,int age){
this.name = name;
this.age = age;
}
// 3. 创建本类的对象：static final
public static final Season SPRING = new Season("春天",1);
public static final Season SUMMER = new Season("夏天",2);
public static final Season AUTUMN = new Season("秋天",3);
public static final Season WINTER = new Season("冬天",4);
// 4. 其余诉求：提供属性的getter方法
public String getName() {
return name;
}
public int getAge() {
return age;
}
// 5. 其余诉求： 重写同toString方法
@Override
public String toString() {
return "Season{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
3.3 jdk1.5新增的定义方式–enum关键字
3.3.1 细节
- 枚举类中创建的常量对象放到类的最上边，仅由常量名和参数列表构成，其余相同修饰信息都可以省略（public static final ）；
- 枚举类的常量对象之间用",“隔开，末尾对象”;"结束；
- 属性、私有化构造器、getter方法和上面的定义方式一致；
- enum类继承于java.lang.Enum类，所以不能再继承于其他类；
- Enum类中重写了toString()方法，返回当前枚举对象的常量名；
- JDK 1.5 中可以在 switch 表达式中使用Enum定义的枚举类的对象作为表达式, case 子句可以直接使用枚举值的名字, 无需添加枚举类作为限定。
3.3.2 代码
enum Season1{
// 1. 枚举类对象：放在类的最前边，仅由对象名和参数列表构成
SPRING("春天",1),
SUMMER("夏天",2),
AUTUMN("秋天",3),
WINTER("冬天",4);
// 2. 声明枚举类的属性：private final
private final String name;
private final int age;
// 3. 私有化构造器，并在构造器中初始化对象的属性
private Season1(String name,int age){
this.name = name;
this.age = age;
}
// 4. 其余诉求：提供属性的getter方法
public String getName() {
return name;
}
public int getAge() {
return age;
}
}
如果没有属性，那么空参构造器可以省略，直接写对象名即可。
enum Season1{
SPRING,
SUMMER,
AUTUMN,
WINTER;
}
3.4 Enum类的主要方法
- values()方法：返回枚举类型的对象数组。该方法可以很方便地遍历所有的枚举值。
- valueOf(String str)：可以把一个字符串转为对应的枚举类对象。要求字符串必须是枚举类对象的“名字”。如不是，会有运行时异常：IllegalArgumentException。可以用来查找枚举类中的对象。
- toString()：返回当前枚举类对象常量的名称
enum Season1{
SPRING,
SUMMER,
AUTUMN,
WINTER;
}
Season1[] values = Season1.values();
for (int i = 0; i < values.length; i++) {
System.out.println(values[i]);
}
System.out.println("--------------------------------------");
Season1 season1 = Season1.valueOf("SPRING");
System.out.println(season1);
SPRING
SUMMER
AUTUMN
WINTER
-----------------------------
SPRING
3.5 枚举类实现接口
3.5.1 细节
- 和普通 Java 类一样，枚举类可以实现一个或多个接口；
- 若每个枚举值在调用实现的接口方法呈现相同的行为方式，则只要统一实现该方法即可；
- 若需要每个枚举值在调用实现的接口方法呈现出不同的行为方式, 则可以让每个枚举值分别来实现该方法；
3.5.2 统一实现方法
interface test{
void show();
}
enum Season1 implements test{
SPRING,
SUMMER,
AUTUMN,
WINTER;
@Override
public void show() {
System.out.println("季节");
}
}
3.5.3 每个枚举值分别来实现方法
interface test{
void show();
}
enum Season1 implements test{
SPRING{
@Override
public void show() {
System.out.println("春");
}
},
SUMMER {
@Override
public void show() {
System.out.println("夏");
}
},
AUTUMN {
@Override
public void show() {
System.out.println("秋");
}
},
WINTER {
@Override
public void show() {
System.out.println("冬");
}
};
}
4.集合
4.1 概述
4.1.1 定义
集合是对多个数据进行存储和操作的结构，是java提供的一种容器。
Map双列集合与Collection单列集合并列存在。
4.1.2 数组与集合的区别
- 数组初始化之后，长度就不可更改；
- 数组的方法和属性较少，不便于进行数据的删除，插入等操作，且效率低；
- 无法直接获取数组中的元素个数；
- 数组是有序、可重复的；
- 数组只能存放单一数据类型的数据；
4.1.3 线程安全和线程不安全的集合
只有Vector和Stack、Hashtable和Properties这两对父子类是线程不安全的。
5.Collection集合
5.1 细节
- 一般往集合中添加元素时，需要重写类的equal()方法，因为contains()和remove()这些方法都需要调用equal()方法比较对象是否相等。
- Collection集合中存放的都是引用数据类型，基本数据类型会自动装箱。
- Collection集合元素可以是 null。
5.2 常用方法
- 添加(尾部添加)
add(Objec tobj)
addAll(Collection coll) - 获取有效元素的个数
int size() - 清空集合
void clear() - 是否是空集合
boolean isEmpty() - 是否包含某个元素
boolean contains(Object obj)：是通过元素的equals方法来判断是否是同一个对象
boolean containsAll(Collection c)：也是调用元素的equals方法来比较的。与次序无关，只要内容相同即可。 - 删除
boolean remove(Object obj) ：通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素
boolean removeAll(Collection coll)：取当前集合的差集 - 取两个集合的交集
boolean retainAll(Collection c)：把交集的结果存在当前集合中，不影响c - 集合是否相等，对于List集合，因为有序，所以必须挨个比较集合中的元素是否相等；对于set集合，无序，只要两个集合中元素相同即可。
boolean equals(Object obj) - 转成对象数组
Object[] toArray() - 获取集合对象的哈希值
hashCode() - 遍历
iterator()：返回迭代器对象，用于集合遍历
5.3 数组转集合
使用Arrays中的静态方法asList(T… a)，参数是可变参数序列，也可以是数组
返回的List集合不能进行更改集合长度的操作，例如add和remove，不然直接抛异常
- 如果是基本数据类型的匿名数组，那么会被当作是一个元素
List ints = Arrays.asList(new int[]{1, 2, 3});
System.out.println(ints.size()); // 1
- 引用数据类型的匿名数组或者可变参数序列，传入几个就算几个
List ints = Arrays.asList(new String[]{"1", "2", "3"});
System.out.println(ints.size()); // 3
List int1 = Arrays.asList(1,2,3,4);
System.out.println(int1.size()); // 4
5.4 迭代器iterator
5.4.1 作用
用于遍历 Collection 集合中的元素。
5.4.2 方法
- hasNext() 判断当前集合是否还有下一个元素
- next() 指针后移，并将指针指向的元素返回
- remove() 移除指针指向的集合元素，如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，再调用remove都会报IllegalStateException。
5.4.3 细节
- iterator迭代器只用于遍历Collection集合，Iterator本身并不提供承装对象的能力。如果需要创建Iterator 对象，则必须有一个被迭代的集合。
- 集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。
- 不经判断，直接调用it.next()可能会抛出NoSuchElementException异常。
5.4.4 实例
List ints = new ArrayList();
ints.add(1);
ints.add(2);
ints.add(3);
ints.add(4);
Iterator it = ints.iterator();
while (it.hasNext()){
Object next = it.next();
if(next.equals(3)){
it.remove();
}
}
System.out.println(ints); // [1, 2, 4]
5.5 foreach
5.5.1 作用
- 用来遍历数组或者Collection集合，底层是通过iterator迭代器实现的。
- 只能遍历元素，在遍历过程中不能修改数组或集合中的元素
5.5.2 实例
int[] arr = new int[]{1, 2, 3};
for (int n : arr) {
System.out.println(n);
}
5.6 List接口(动态数组)
List是ArrayList、LinkedList、Vector的父接口，所以它们实现了这些方法。
List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来操作集合元素的方法。
- void add(int index, Object ele):在index位置插入ele元素
- boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
- Object get(int index):获取指定index位置的元素
- int indexOf(Object obj):返回obj在集合中首次出现的位置，不存在返回-1
- int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
- Object remove(int index):移除指定index位置的元素，并返回此元素
- Object set(int index, Object ele):设置指定index位置的元素为ele
- List subList(int fromIndex, int toIndex):返回从
[fromIndex,toIndex)位置的子集合
5.6.1 常用方法
- 增(尾部)：add(Object obj)
- 删：remove(int index) / remove(Object obj)
- 改：set(int index, Object ele)
- 查：get(int index)
- 插：add(int index, Object ele)
- 长度：size()
- 遍历：① Iterator迭代器方式 ② 增强for循环 ③ 普通的循环
ArrayList a = new ArrayList();
a.add(1);
a.add(2);
a.add(3);
a.add(4);
a.add(5);
for (int i = 0; i < a.size(); i++) {
System.out.println(a.get(i));
}
for (Object i : a) {
System.out.println(i);
}
5.6.2 细节
List中添加的对象所在类需要重写equals()方法，虽然List可以插入相同的元素，插入时不需要使用equals()方法比较，但是remove()和contains()方法需要使用equals()方法比较。
5.7 ArrayList
5.7.1 特点
- 底层是通过
Object[] elementData数组来存储数据，查找修改快，插入和删除慢； - 线程不安全，效率高；
- 如果确定集合元素个数，开发中一般使用
public ArrayList(int initialCapacity)带参构造器来创建集合对象，避免了扩容造成的系统开销； - 可以使用构造器
public ArrayList(Collection<? extends E> c)将其余Collection实现类转为ArrayList集合；
5.7.2 jdk1.8 源码解析
- 使用空参构造器创建ArrayList后，此时集合的容量为0，只有第一次调用add()/addAll()方法时，才会分配空间。如果第一次添加的元素个数小于等于10，那么集合容量定为10；如果大于10，则集合容量定为所添加的元素个数。之后的扩容，都是将容量扩为当前的1.5倍。
- 如果使用带参构造器
public ArrayList(int initialCapacity)，会直接创建一个指定容量的数组this.elementData = new Object[initialCapacity];，首次创建并不会扩容。
5.8 LinkedList
5.8.1 特点
- 底层数据结构是双向链表，插入删除快，查找修改慢；
- 线程不安全，效率高；
5.8.2 新增方法
- void addFirst(Object obj) 在链表头部插入一个新节点，相当于add(0,obj);
- void addLast(Object obj) 在链表尾部插入一个新节点，相当于add(obj);
- Object getFirst() 得到表头元素，相当于get(0)
- Object getLast() 得到表尾元素，相当于get(list.size()-1)
- Object removeFirst() 删除表头元素，相当于remove()或者remove(0)
- Object removeLast() 删除表尾元素，相当于remove(list.size()-1)
5.8.3 源码分析
- 通过空参构造器创建
public LinkedList() { } - 添加元素
public boolean add(E e) {
linkLast(e);
return true;
}
将元素添加到链表末尾
void linkLast(E e) {
final Node<E> l = last; // 获取当前末尾元素
final Node<E> newNode = new Node<>(l, e, null);// 新建节点
last = newNode; // 将新建节点作为链表最后一个元素
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// 链表结构
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
5.9 Vector
5.9.1 特点
- 底层是通过数组来存储数据；
- 线程安全，效率低；
- 大多数操作与ArrayList相同，区别之处在于Vector是线程安全的。现在一般不使用Vector；
5.9.2 源码分析
- 空参构造创建对象，容量设为10;
public Vector() { this(10); } - 默认扩容为原来容量的2倍；
5.10 面试题–remove(int index)和remove(Object obj)的选择
因为List中有两个构成重载的方法remove(int index)和remove(Object obj)，如果直接传入一个整数，那么选择的是remove(int index)；如果传入一个Integer类型的对象，那么选择的是remove(Object obj)。
@Test
public void testListRemove() {
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
updateList(list);
System.out.println(list);//[1, 2]
}
private static void updateList(List list) {
list.remove(2);
}
5.11 ArrayList/LinkedList/Vector的异同
相同点：都是List接口的实现类，存放的元素是有序可重复的。
不同点：
如果在尾部添加元素，ArrayList效率要高于LinkedList，因为数组具有随机访问性，ArrayList可以直接定位到尾部元素的位置，且不需要移动其它元素，时间复杂度为O(1)；而链表不具备随机访问性，LinkedList需要从头部往后依次查找，时间复杂度为O(n);
5.12 Vector和ArrayList的最大区别
Vector和ArrayList的最大区别是Vector是线程安全的，ArrayList不是。
5.12 Set接口
5.12.1 概述
- Set集合无序，不可重复。
无序：不等于随机性，添加元素时不会按照数组索引递增的顺序存放，而是根据hash值来确定存放位置。而且不能说遍历顺序与存放顺序不一致，因为LinkedHashSet遍历顺序与存放顺序一致。
不可重复：相同的元素只能添加一个，具体比较方式看实现类。
- Set接口是Collection的子接口，set接口没有提供额外的方法。
- 去重：HashSet和LinkedHashSet中存放的对象所在类需要重写hashCode()和equals()方法；TreeSet可以不用重写hashCode()和equals()方法，但是一定要实现比较器接口。
5.13 HashSet
5.13.1 jdk1.8 源码
- 对象创建：创建一个HashMap对象
public HashSet() {
map = new HashMap<>();
}
- 添加元素过程
向HashSet中添加元素a时，首先要计算元素a的哈希值，通过哈希值得到在数组中的索引，如果索引位置没有元素，添加成功；
如果索引位置有元素，比较元素a与索引位置其他元素的哈希值(同一链表上的元素)：
如果哈希值不同，添加成功；
如果哈希值相同，则使用元素a的equals()方法进行比较，如果不相等，添加成功；
5.13.2 细节
- HashSet底层是数组+链表+红黑树实现的(JDK1.8之后)。
- 对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：“相等的对象必须具有相等的散列码”。
- HashSet 线程不安全。
5.13.3 重写hashCode()和equals()
- 因为Object中的hashCode()返回的是对象的内存地址，而集合添加元素时关注的是对象的内容是否相等(内容相同的对象内存地址不一定一样)，所以根据对象的属性重写hashCode()，保证相等的对象必须具有相等的哈希值(哈希值用来获取数组索引)。
- 在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。（唯一性）
- 当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode() 方法的返回值也应相等。（对等性）
- 对象中用作 equals() 方法比较的属性，都应该用来计算 hashCode 值。（保证对等性的实现）
- 一般使用编辑器自动生成的代码即可。
5.13.4 为什么用Eclipse/IDEA重写hashCode方法中，使用31这个数字？
public static int hashCode(Object a[]) {
if (a == null)
return 0;
int result = 1;
for (Object element : a)
result = 31 * result + (element == null ? 0 : element.hashCode());
return result;
}
- 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。（减少冲突）
- 31只占用5bits,相乘造成数据溢出的概率较小。
- 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。（提高算法效率）
- 31是一个素数，素数作用就是如果我用一个数字来乘以这个素数，那么最终出来的结果只能被素数本身和被乘数还有1来整除！(减少冲突)
5.14 LinkedHashSet
5.14.1 细节
- LinkedHashSet是HashSet的子类。
- LinkedHashSet根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，保证遍历顺序与存放的顺序一致。
- LinkedHashSet 不允许集合元素重复。
5.14.2 底层结构
5.15 TreeSet
5.15.1 细节
- TreeSet 可以确保集合元素处于排序状态，有两种排序方法：自然排序和定制排序。
- 同一个TreeSet集合只能添加相同数据类型的对象。
- 对于 TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 或者compare(Object o1, Object o2)方法比较的返回值是否为0。如果两个对象比较返回值是0，那么后者不会被添加到集合中(Set不可重复)
5.15.2 自然排序
添加对象的所在类必须实现Comparable接口，重写comparTo()方法
根据年龄排序
TreeSet t = new TreeSet();
t.add(new Person("jack",22));
t.add(new Person("merry",17));
t.add(new Person("json",5));
t.add(new Person("luse",35));
t.add(new Person("facker",35)); // 不会添加到集合中
for (Object o: t) {
System.out.println(o);
}
Person{name='json', age=5}
Person{name='merry', age=17}
Person{name='jack', age=22}
Person{name='luse', age=35}
5.15.3 定制排序
- TreeSet的自然排序要求元素所属的类实现Comparable接口，如果元素所属的类没有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
- 要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
根据名字排序
TreeSet t = new TreeSet(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((Person)o1).getName().compareTo(((Person)o2).getName());
}
});
t.add(new Person("jack",22));
t.add(new Person("merry",17));
t.add(new Person("hson",5));
t.add(new Person("luse",35));
t.add(new Person("facker",35));
for (Object o: t) {
System.out.println(o);
}
Person{name='facker', age=35}
Person{name='hson', age=5}
Person{name='jack', age=22}
Person{name='luse', age=35}
Person{name='merry', age=17}
5.16 练习
5.16.1 去除List中的重复数据
思路：通过set集合来实现
- 将list集合中的所有元素添加到Set集合中；
- 将Set集合作为List集合构造器的形参创建List集合实例。
List list = new ArrayList();
list.add(1);
list.add(1);
list.add(2);
list.add(2);
list.add(3);
list.add(3);
list.add(4);
Set hs = new HashSet();
1. 将list集合中的所有元素添加到Set集合中
hs.addAll(list);
2. 将Set集合作为List集合构造器的形参创建List集合实例
System.out.println(new ArrayList(hs));
5.16.2 Set集合增删
remove过程：首先计算传入对象的哈希值，得到数组索引，当传入对象和索引位置的元素的哈希值相同并且调用equals()方法返回值为true时，移除相同元素。（跟add()比较流程相同）
当集合中一有元素的内容更改时，其哈希值不会更改。
set.remove(p1);：因为p1的属性name更改，所以其哈希值也随之更改，但是其在set集合中的位置没有改变。故调用remove(p1)方法时，查找的位置可能不是p1的当前位置，所以p1不会被移除。
set.add(new Person(1001,"CC"));：此对象的哈希值与集合中Person{1001,“CC”}的哈希值不同，所以两者不会出现哈希冲突，添加成功。
set.add(new Person(1001,"AA"));：此对象的哈希值与集合中Person{1001,“CC”}的哈希值相同，但是通过equals()比较内容不相同，所以添加成功。
HashSet set = new HashSet();
Person p1 = new Person(1001,"AA");
Person p2 = new Person(1002,"BB");
set.add(p1);
set.add(p2);
System.out.println(set);
p1.name = "CC";
set.remove(p1);
System.out.println(set);
set.add(new Person(1001,"CC"));
System.out.println(set);
set.add(new Person(1001,"AA"));
System.out.println(set);
[Person{name='BB', age=1002}, Person{name='AA', age=1001}]
[Person{name='BB', age=1002}, Person{name='CC', age=1001}]
[Person{name='BB', age=1002}, Person{name='CC', age=1001}, Person{name='CC', age=1001}]
[Person{name='BB', age=1002}, Person{name='CC', age=1001}, Person{name='CC', age=1001}, Person{name='AA', age=1001}]
6.Map集合
6.1 概述
6.1.1 Map的实现类的结构
|----Map:双列数据，存储key-value对的数据 —类似于高中的函数：y = f(x)
|--------HashMap:作为Map的主要实现类；线程不安全的，效率高；可以存储null的key和value
|------------LinkedHashMap:保证在遍历map元素时，可以按照添加的顺序实现遍历。
|------------原因：在原有的HashMap底层结构基础上，使用了一对双向链表来记录添加元素的顺序，迭代顺序与 Key-Value 对的插入顺序一致
|------------对于频繁的遍历操作，此类执行效率高于HashMap。
|--------TreeMap:保证按照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序，底层使用红黑树
|--------Hashtable:作为古老的实现类；线程安全的，效率低；不能存储null的key和value
|------------Properties:常用来处理配置文件。key和value都是String类型
HashMap的底层：数组+链表 （jdk7及之前）；数组+链表+红黑树 （jdk 8）
6.1.2 细节
- Map 中的 key 和 value 都可以是任何引用类型的数据。
- key是唯一的，value可以重复，通过一个key只能确定唯一一个value值。
6.1.3 Map结构的理解
- key：不可重复且无序，所以使用Set存放。即同一个HashMap的key所对应的类，须重写hashCode()和equals()方法。
- value：可以重复且无序，使用Collection存放，value所对应的类应该重写equals()方法。
- Entry：key-value构成了一个Entry对象，无序且不可重复，使用Set存放。
6.2 HashMap
6.2.1 jdk1.7 底层源码分析
创建+添加：
- 通过空参构造器创建对象后，底层创建了长度是16的一维数组Entry[] table。
- 通过put(key,value)向集合中添加元素，==首先计算key的哈希值，==通过哈希值确定数组索引，如果数组索引处为空，添加成功；
- 如果数组索引处存在一个或多个entry对象(以链表形式存在)，依次比较添加元素key与它们key的哈希值，如果都不同，添加成功(添加到链表尾部)；
- 如果存在key的哈希值相同的entry对象，通过equals()依次与它们key的实体内容比较，如果所有的equals()都返回false，添加成功(添加到链表尾部)；
- 如果任意一个equals()返回true，就用添加元素的value替换掉现有元素的value，并返回现有元素的value；
6.2.2 jdk1.8 底层源码分析
- 创建对象：通过空参构造器创建对象，此时并没有初始化数组
Node<K,V>[] table长度，只是将填充因子loadFactor 设为DEFAULT_LOAD_FACTOR=0.75；
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
- 首次添加元素：首先会创建一个长度为16，临界值(数组总长度*loadFactor)为12的Node数组，通过
(n - 1) & hash(n:数组长度，hash：k的哈希值)计算出元素所在的数组位置，然后将元素放入数组中。
之后添加元素：与jdk1.7大致相同。
public V put(K key, V value) {
hash(key)：计算key的哈希值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
首次添加才能进入此if语句
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
如果添加元素所在的数组位置为null，则可以直接添加
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
如果 table 的索引位置的 key 的 hash 相同和新的 key 的 hash 值相同，
并 满足(table 现有的结点的 key 和准备添加的 key 是同一个对象 || equals 返回真)
就认为不能加入新的 k-v
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
如果当前的 table 的已有的 Node 是红黑树，就按照红黑树的方式处理
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
加入后，判断当前链表的个数，是否已经到 8 个，到 8 个，后
就调用 treeifyBin 方法进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
6.2.3 源码中的重要常量
DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
threshold：扩容的临界值，数组总长度*加载因子：16 * 0.75 => 12
TREEIFY_THRESHOLD：Bucket中链表长度大于等于该默认值，转化为红黑树:8
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量:64
6.2.4 扩容
添加元素时，当HashMap中元素的个数(1.7不包括要添加的元素，1.8包括)超过临界值(数组总长度*loadFactor)且要存放的位置非空，就会进行数组扩容。loadFactor(填充因子)的默认值时0.75，默认情况下，数组大小(DEFAULT_INITIAL_CAPACITY)为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为2*16=32，临界值扩大为24(32*0.75)，即扩大为原来的2倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数， 那么使用指定容量的构造器进行实例化能够有效地提高HashMap的性能。
6.2.5 为什么要提前扩容(为什么要有临界值)
因为HashMap中元素的索引是根据哈希值计算出来的，就可能会导致有的位置一直没有元素存放，而有的位置的元素会有很多个，降低查询效率，所以定义了临界值来提前扩容。
6.2.6 jdk1.8 链表 <==> 红黑树
添加元素成功之后，如果此索引位置上的链表长度大于等于TREEIFY_THRESHOLD=8但是数组长度小于MIN_TREEIFY_CAPACITY=64，那么HashMap会先扩容解决；如果数组长度大于等于64，那么此索引位置上的链表就会转为红黑树。后续如果由于删除或者其他原因调整了大小，当红黑树的节点小于或等于 6 个以后，又会恢复为链表形态。
为什么链表要变为红黑树：为了防止用户自己实现了不好的哈希算法时导致链表过长，从而导致查询效率低。
为什么数组有长度限制： 因为链表的长度不大的时候，红黑树不会带来明显的查询时间上的优势，反而会增加空间复杂度。所以通常情况下，并没有必要转为红黑树。
为什么TREEIFY_THRESHOLD是8：因为链表的长度不大的时候，红黑树不会带来明显的查询时间上的优势，反而会增加空间复杂度。所以通常情况下，并没有必要转为红黑树。如果 hashCode 分布良好,很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，长度为 8 概率小于千万分之一(仅为 0.00000006)，所以通常情况下，并不会发生从链表向红黑树的转换。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果 table 为 null ,或者大小还没有到 64，暂时不树化，而是进行扩容. //否则才会真正的树化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
6.2.7 jdk1.8之前 HashMap 的缺点
- JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。
- 当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。
- 针对这种情况，JDK 1.8 中引入了红黑树（查找时间复杂度为 O(logn)）来优化查找时间。
6.2.8 jdk1.8 底层代码的改进
- 底层数组由
Entry<K,V>[] table转为Node<K,V>[] table，两者没有较大的区别； HashMap map = new HashMap();默认情况下，先不创建长度为16的数组，当首次调用map.put()时，再创建长度为16的数组；- 七上八下：jdk1.7时新增的元素作为链表头，jdk1.8时新增的元素作为链表尾；
- JDK 1.8 以前 HashMap 的实现是 数组+链表，jdk1.8之后是数组+链表+红黑树；
6.2.9 负载因子值的大小，对HashMap有什么影响
负载因子和当前Node数组长度的乘积称为临界值，根据临界值来进行数组的扩充。
- 负载因子的大小决定了HashMap的数据密度。
- 负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时的比较次数增多，性能会下降。
- 负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。
- 按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数。
6.3 LinkedHashMap
6.3.1 细节
- 继承于HashMap,添加元素时使用双向链表来记录元素的顺序，所以遍历顺序与添加顺序一致。
6.3.2 实例
Map m = new LinkedHashMap();
m.put("指定",2);
m.put("dsf",2);
m.put("123",2);
m.put(456,2);
System.out.println(m);//{指定=2, dsf=2, 123=2, 456=2}
6.4 Map中的常用方法
6.4.1 添加/修改
Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中，返回值时被替换键值对的value，如果没有替换，则为null。void putAll(Map m):将集合m中的键值对添加到当前map集合中。
6.4.2 删除
Object remove(Object key)：移除指定key的key-value对，并返回value。void clear()：清空当前map中的所有数据。
6.4.3 查找
Object get(Object key)：获取指定值对应的valueboolean containsKey(Object key)：是否包含指定的keyboolean containsValue(Object value)：是否包含指定的valueint size()：返回map中key-value对的个数boolean isEmpty()：判断当前map是否为空boolean equals(Object obj)：判断当前map和参数对象obj是否相等
6.4.4 元视图查询
- Set keySet()：返回所有key构成的Set集合
- Collection values()：返回所有value构成的Collection集合
- Set entrySet()：返回所有key-value对构成的Set集合
6.4.5 Entry中的方法
k getKey()：获取entry中的键；k getValue()：获取entry中的值；
6.5 遍历Map集合
6.5.1 方式1
获取entry集合，通过Entry中的getKey()和getValue()方法来遍历
Set set1 = m.entrySet();
for (Object o1 : set1) {
System.out.print(((Map.Entry)o1).getKey());
System.out.print(((Map.Entry)o1).getValue());
System.out.println();
}
6.5.2 方式2
获取keySet集合，通过get()方法来获取对应的value；
Set set = m.keySet();
for (Object o1 : set) {
Object o2 = m.get(o1);
System.out.println(o1 + "--->" + o2);
}
6.6 TreeMap
6.6.1 细节
- TreeMap存放键值对时会对key进行排序，可以保证所有的 Key-Value 对处于有序状态。
- TreeMap底层使用红黑树结构存储数据。
- TreeMap中的所有Key必须是相同数据类型，且一定要实现比较器接口并重写其中的比较方法。
- TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0。
6.6.2 自然排序
key对象所在的类实现Comparable接口，重写compareTo()方法。
6.6.3 定制排序
实现Comparator接口，重写compare()方法，作为TreeMap的构造器参数传入；
TreeMap t = new TreeMap(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return -o1.compareTo(o2);
}
});
t.put("gsd",1);
t.put("hsd",1);
t.put("asd",1);
t.put("csd",1);
System.out.println(t);
6.7 Hashtable
- Hashtable实现原理和HashMap相同，功能相同。但是不同于HashMap，Hashtable是线程安全的；
- 与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value；
6.8 Properties
- Properties 类是 Hashtable 的子类，该对象用于处理属性文件
- 由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型
- 存取数据时，建议使用
setProperty(String key,String value)方法和getProperty(String key)方法 - 加载本地properties文件：
pros.load(new FileInputStream("jdbc.properties"));
Properties p = new Properties();
FileInputStream fls = null;
try {
fls = new FileInputStream("test.properties");
p.load(fls);
Object name = p.getProperty("name");
Object age = p.getProperty("age");
System.out.println(name + "---" + age);
} catch (IOException e) {
e.printStackTrace();
}finally {
try {
fls.close();
} catch (IOException e) {
e.printStackTrace();
}
}
7 开发中如何选择集合实现类
8 Collections
8.1 概述
Collections是操作List、Set、Map的工具类，其中都是静态方法，可以实现对集合的排序、查找、替换和线程安全化。
8.2 排序操作
8.2.1 静态方法
* reverse(List)：反转 List 中元素的顺序
* shuffle(List)：对 List 集合元素进行随机排序
* sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
* sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行定制排序
* swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
* Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
* Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
* Object min(Collection)
* Object min(Collection，Comparator)
* int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
* void copy(List dest,List src)：将src中的内容复制到dest中
* boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换 List 对象的所有旧值
8.2.2 细节
shuffle(List)：对List集合随机排序，每次调用结果都不同。void copy(List dest,List src)：将src中的内容复制到dest中。
list1中元素个数必须与list中相同，不然会抛异常Source does not fit in dest
List list1 = Arrays.asList(new Object[list.size()]);
Collections.copy(list1, list);
System.out.println(list1);
8.3 转为线程安全的集合
使用Collections.synchronizedXxx()方法可以将集合转为线程安全的集合。所以在实际开发中如果需要线程安全的集合，我们一般也不会选择Vector、Hashtable这种本来就线程安全的集合，而是使用Collections.synchronizedXxx()方法将ArrayList、HashMap转为线程安全的。
