集合

介绍

数组的不足

集合的好处

集合的体系

单列集合

双列集合（键值对）

Collection接口和常用方法

2）remove可以是一个对象也可以是一个下标
7）addAll可以加入一个新的list
8）containsAll可以查找是否包含一个list

迭代器遍历

迭代器执行原理

快捷键itit

while (iterator.hasNext()) {
            Object next =  iterator.next();
            
        }
1
2
3
4

注意：当退出while循环后，此时迭代器指向最后的元素，如果再取iterator.nxet()会报错，如果仍要使用可以重新让Inerator iterator = list.iterator()

增强for循环

注意：也可以用在数组上

List接口和常用方法

基本介绍

常用方法

1）add方法第一个参数可以是索引，用来指定插入的位置
2）addAll方法同上
7）set方法相当于指定一个下标，把元素给替换掉
8）subList方法返回的集合是前闭后开的集合

ArrayList底层结构和源码分析

注意事项

• 可以加入多个null
• 效率高，但是不安全，多线程时推荐Vector
  

底层结构和源码分析（重点，难点）

tip：扩容时因为无参，所以临时（0,10）1.5倍；如果有参直接1.5倍

Vector底层结构和源码分析

Vector和ArrayList的比较

LinkedList底层结构

linkedList.add()其实就是l存放当前链表中的尾结点，然后加入新节点（构造器中prev指向了l），l的next指向新节点，节点的添加过程就完成了

linkedList.remove(index)，删除指定下标的结点，不加index默认删除下标0的结点

ArrayList和LinkedList的比较

注意：这两个集合都是不安全的，所以推荐在单线程中使用

Set接口和常用方法

基本介绍

特点：

• 无序，但每次取出的顺序是固定的，根据哈希值
• 不重复
  

常用方法

注意：不能用传统for遍历

HashSet全面说明（无序，“不重复”）

不能存放相同元素？

1. 先获取元素的哈希值（hashcode方法）
2. 对哈希值进行运算，得出一个索引值即为要存放在哈希表中的位置号，位置号不同肯定可以存放
3. 如果位置号相同且该位置上没有其他元素，则直接存放，如果该位置上己经有其他元素则需要进行equals判断（程序员自己定义），如果相等，则不再添加。如果不相等，可以添加

HashSet底层机制说明（底层是HashMap）

• 先算hash值，然后转成索引值，当索引值相同的时候调用euals比较，不同的时候放链表中
• 一条链表的元素个数达到8，并且table的大小到达64个就会把这个链表转成红黑树

扩容机制(不区分结点是加在table中还是table的链表中)

注意：链表长度大于 8，总长度大于 64时树化，如果总长度小于 64 而链长度大于 8 了，会进行扩容（table长度*2）

HashSet中equals和hashCode的重写

   @Override
   //值相同返回true
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        //基本数据类型直接使用==比较值，引用数据类型就用Object的equals方法比较地址
        return age == employee.age && Objects.equals(name, employee.name);
    }

    @Override
    //当前对象的name和age值相同就返回相同的hashcode
    public int hashCode() {
        return Objects.hash(name, age);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LinkedHashSet介绍

底层机制示意图

特点：插入顺序和读取顺序一致

Map接口和常用方法

Set的底层是Map，不过只用了Map的key值，value用了常量填充

特点

1. 加入元素使用put(key,value)方法
2. key不能重复，value可以（key不同时，都不在同一个链表上）。如果key重复了等价于替换。
3. key可以为空，只能有一个，value可以为空，可以有多个
4. key大多数情况放字符串，其实可以放个Object对象
5. 通过key一定可以找到value，map.get(key)得到value

理解key-value

键值对是匿名内部类HashMap$Node类型的，为了遍历方便map提供的entrySet()方法会返回EntrySet集合，里面存放的元素是Entry类型的，而Entry的key和value分别指向Node的key和value

Map接口常用方法

entrySet()方法

返回set集合，方便遍历

Set set = hashMap.entrySet();
        for (Object o : set) {
            System.out.println(((Map.Entry) o).getValue());
        }
1
2
3
4

keySet()方法

返回一个Set，里面存放key

values()方法

返回一个Collection，里面存放value

Map的几种遍历方法

        //法一
        Set set1 = map.keySet();
        for (Object key : set1) {
            System.out.println(key + " " + map.get(key));
        }
        //法二
        Set set2 = map.entrySet();
        for (Object entry : set2) {
            Map.Entry e = (Map.Entry) entry;
            System.out.println(e.getKey() + " " + e.getValue());
        }
1
2
3
4
5
6
7
8
9
10
11

HashMap底层

注意：链表长度大于 8，总长度大于 64时会树化，如果总长度小于 64 而链长度大于 8 了，会进行扩容（）table长度*2）

HashMap小结

HashTable基本介绍（安全，不可null）

HashTable的底层机制

HashTable和HashMap对比

• 注意：HashTable不会树化

Map接口的实现类Properties

常用方法

TreeSet

最大的特点是有序的(通过比较器)，默认按比如数值、字符(ASCII码值)
补充：LinkedHashSet也是有序的（通过链表维系次序）

源码解读

1. 构造器把传入的比较器对象，赋给了 TreeSet的底层的 TreeMap的属性this.comparator

public TreeMap(Comparator<? super K> comparator){
		this.comparator = comparator
}
1
2
3

2. 再调用 treeset.add("tom”)，在底层会执行到

if (cpr != null) {//cpr就是我们自己写的匿名内部类（对象）
	do {
		parent = t;
		cmp = cpr.compare(key, t.key);//动态绑定到我们的匿名内部类（对象）
		if (cmp < 0)
			t = t.left:
		else if (cmp > 0)
			t = t.right;
		else//如果相等，即返回0，这个key就没加入
			return t.setValue(value):
	} while(t != null);
1
2
3
4
5
6
7
8
9
10
11

TreeMap

源码解读

集合总结，如何选择实现类

Collections工具类

常用方法

6)注意是右到左，且长度是List里的size()方法值，我们都知道new ArrayList()初始化的时候size()等于0，即便是你使用new ArrayList(10)来初始化，也只是预设了一个initialCapacity＝＝10的存储空间，size()还是等于0。因此在使用Collections.copy之前，需要把目的List加一些空的元素，直到目的List的size()值与源List的size()值等长（或更长）

习题

4. treeSet会优先使用我们传进去的的Comparator匿名对象，如果没传，会以添加进去的对象实现Comparable接口的compareTo去重，如过传进去的对象没有实现Comparable接口，会报错具体见第五题
5.

// 如果没有传入comparator，会尝试把添加的对象转换成Comparable类型，如果添加的对象没有实现Comparable接口，会报类型转换错误
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)

1
2
3

---

• 重写了hashCode和equals方法后，如果id和name相同就会认为是同一对象
• remove方法也会根据key去计算hash值，从而确定索引，这边set.remove(p1)时，根据1001和CC算出的索引位置不再是原来p1的位置，索引remove了null，第一次输出{1001,CC}
• set.add(new Person(1001,“CC”)时，计算出的索引位置是上面remove的位置，所以添加成功，第二次输出{1001,CC}，{1001,CC}
• set.add(new Person(1001,“AA”)时，计算出的索引在第一个位置，但是equals方法比较CC和AA值得时候不相等，所以{1001,AA}挂在{1001,CC}后面