14.集合|Java学习笔记

Java 的集合类很多， 主要分为两大类
单列集合Collection，双列集合Map

1. Collection实现子类可以存放多个元素，每个元素可以是Object
2. 有些Collection的实现类，可以存放重复的元素，有些不可以
3. 有些Collection的实现类，有些是有序的(List)，有些不是有序(Set)
4. Collection接口没有直接的实现子类，是通过它的子接口Set和List来
   实现的

1. Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。
2. 所有实现了Collection接口的集合类都有一个iterator(方法， 用以返回
   一个实现 了Iterator接口的对象，即可以返回一个迭代器。
3. Iterator的结构.[看一 张图]
4. Iterator仅用于遍历集合，Iterator本身并不存放对象。

List接口是Collection接口的子接口List java

1. List集合类中元素有序(即添加顺序和取出顺序一致)、 且可重复。
2. List集合中的每个元素都有其对应的顺序索引，即支持索引。
3. List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
4. JDK API中List接口的实现类有:
   

1. permits all elements, including null , ArrayList可以加入null,并且多个
2. ArrayList是由数组来实现数据存储的
3. ArrayList基本等同于Vector，除了ArrayList是线程不安全(执行效率高)
   在多线程情况下，不建议使用ArrayList

1. ArrayList中维护了一个0bject类型的数组elementData. [debug看源码]
   transient Object[] elementData; //transient表示瞬间,短暂的，表示该属性不会被序列化
2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0,第1次添加，则扩容elementData为10,如需要再次扩容，则扩容elementData为1.5倍。
3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData为1.5倍。

1. Vector底层也是一个对象数组，protected Object[] elementData;
2. Vector 是线程同步的，即线程安全，Vector类的操作方法带有synchronized

public synchronized E get(int index) {
	if (index > = elementCount)
		throw new ArrayIndexOutOfBoundsException(index); 
	return elementData(index); 
}

3. 在开发中，需要线程同步安全时，考虑使用Vector

Vector 和 ArrayList 的比较

1. linkedList底层实现了双向链表和双端队列特点
2. 可以添加任意元素(元素可以重复)，包括null
3. 线程不安全，没有实现同步

1. linkedList底层维护了一个双向链表.
2. linkedList中维护了两个属性first和last分别指向首节点和尾节点
3. 每个节点(Node对象)，里面又维护了prev、next、item三个属性， 其中通过prev指向前一个，通过next指向后一一个节点。最终实现双向链表.
4. 所以linkedList的元素的添加和删除，不是通过数组完成的，相对来说效率较高。

ArrayList 和 linkedList 的比较

如何选择ArrayList和linkedList:

1. 如果我们改查的操作多，选择ArrayList。
2. 如果我们增删的操作多，选择linkedList。
3. 一般来说，在程序中，80%-90%都是查询，因此大部分情况下会选择ArrayList。
4. 在一个项目中，根据业务灵活选择，也可能这样，一个模块使用的是ArrayList,另外一个模块是linkedList,也就是说，要根据业务来进行选择。

Set 接口基本介绍

1. 无序(添加和取出的顺序不一致) ,没有索引
2. 不允许重复元素，所以最多包含一个null

同Collection的遍历方式-样，因为Set接口是Collection接口的子接口。

1. 可以使用迭代器
2. 增强for
3. 不能使用索引的方式来获取.

HashSet 的全面说明

1. HashSet实现了Set接口
2. HashSet实际上是HashMap，看下源码.

public HashSet() {
    map = new HashMap<>();
}

3. 可以存放null值，但是只能有一个null
4. HashSet不保证元素是有序的,取决于hash后，再确定索引的结果. (即，不
   保证存放元素的顺序和取出顺序一 致)
5. 不能有重复元素/对象.在前面Set接口使用已经讲过

HashMap底层是（数组+链表+红黑树）

1. HashSet 底层是HashMap
2. 添加一个元素时，先得到hash值-会转成->索引值
3. 找到存储数据表table ,看这个索引位置是否已经存放的有元素
4. 如果没有，直接加入
5. 如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则
   添加到最后
6. 在Java8中，如果一条链表的元素个数到达TREEIFY THRESHOLD(默认是8)，并且table的大小 >=MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树),否则仍然采用数组扩容机制。

HashSet看源码！
HashSet源码解读

1. HashSet底层是HashMap,第一次添加时，table 数组扩容到16,临界值(threshold)是16*加载因子(loadFactor)是0.75 = 12
2. 如果table数组使用到了临界值12,就会扩容到16* 2 = 32,新的临界值就是32*0.75 = 24,依次类推
3. 在Java8中， 如果一条链表的元素个数到达TREEIFY THRESHOLD(默认是8 ),并且table的大小>=MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)，否则仍然采用数组扩容机制

linkedHashSet

1. linkedHashSet是HashSet的子类
2. linkedHashSet底层是一个linkedHashMap,底层维护了一个数组+双
   向链表
3. linkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使
   用链表维护元素的次序(图)，这使得元素看起来是以插入顺序保存的。
4. linkedHashSet不允许添重复元素

1. 在linkedHastSet 中维护了一个hash表和双向链表( linkedHashSet有head和tail )
2. 每一个节点有before和after属性，这样可以形成双向链表
3. 在添加一个元素时，先求hash值，在求索引.确定该元素在table的位置，然后将添加的元素加入到双向链表(如果已经存在，不添加[原则和hashset一样])
4. 这样的话，我们遍历linkedHashSet也能确保插入顺序和遍历顺序一致

Map

1. Map与Collection并列存在。 用于保存具有映射关系的数据:Key-Value
2. Map中的key和value可以是任何引用类型的数据，会封装HashMap$Node对象中
3. Map中的key不允许重复，原因和HashSet一样，前面分析过源码.
4. Map中的value可以重复
5. Map的key可以为null, value也可以为null,注意key为null,只能有一个，value为null可以多个。
6. 常用String类作为Map的key
7. key和value之间存在单向一对一关系，即通过指定的key总能找到对应的value
8. Map存放数据的key-value示意图，-对k-v是放在一-个HashMap$Node中的，因为Node实现了Entry 接口，有些书上也说一对k-v就是一个Entry

entrySet

HashMap 小结

1. Map接口的常用实现类: HashMap、Hashtable和Properties
2. HashMap是Map接口使用频率最高的实现类。
3. HashMap是以key-val对的方式来存储数据(HashMap$Node类型)
4. key不能重复，但是值可以重复，允许使用null键和null值。
5. 如果添加相同的key，则会覆盖原来的key-val等同于修改.(key不会替换，val会替换)
6. 与HashSet-样，不保证映射的顺序，因为底层是以hash表的方式来存储的. (jdk8的hashMap底层数组+链表+红黑树)
7. HashMap没有实现同步，因此是线程不安全的，方法没有做同步互斥的操作，没有synchronized

1. (k,v)是一个Node实现了Map.Entry，查看HashMap的源码可以看到.
2. jdk7.0的hashmap底层实现[数组+链表]，jdk8.0底层[数组+链表+红黑树]

➢扩容机制[和HashSet相同]

1. HashMap底层维护了Node类型的数组table,默认为null
2. 当创建对象时，将加载因子(loadfactor)初始化为0.75。
3. 当添加key-val时，通过key的哈希值得到在table的索引。然后判断该索引处是否有元素，如果没有元素直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key相是否等，如果相等，则直接替换val;如果不相等需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。
4. 第1次添加，则需要扩容table容量为16,临界值(threshold)为12 (16*0.75)
5. 以后再扩容，则需要扩容table容量为原来的2倍(32),临界值为原来的2倍,即24,依次类推。
6. 在Java8中，如果一条链表的元素个数超过 TREEIFY THRESHOLD(默认是8),并且table的大小>= MIN TREEIFY CAPACITY(默认64),就会进行树化(红黑树)

HashTable

1. 存放的元素是键值对:即K-V
2. hashtable的键和值都不能为null, 否则会抛出NullPointerException
3. hashTable使用方法基本上和HashMap-样
4. hashTable是线程安全的(synchronized), hashMap是线程不安全的

到8个进行扩容。(8=11*0.75)
扩容之后11*2+1=23

Map接口实现类——
Properties

1. Properties类继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据。
2. 它的使用特点和Hashtable类似。
3. Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，并进行读取和修改