Java集合，超详细整理，适合新手入门

目录

1. 单列集合Collection

• 指的是在集合里面放的是单个的对象
• Collection 接口有两个重要的子接口 List、Set
• Collection提供了size()方法，List提供了get()方法

1.0 Collection接口实现类的特点

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

1.1 Collection常用方法

1. add添加单个元素,只要是Object的子类，都可以往里放,输入整数存在一个自动装箱的过程
2. remove()删除指定的元素 remove构成重载: remove(Object 0) 返回布尔值; remove(int index) 返回被删除的对象
3. contains()查找某个元素是否存在
4. size()获取元素个数,从1开始计数
5. addAll()可以添加多个元素 可以在某个下标存入一个实现了Collection接口的ArrayList
6. removeAll()删除多个元素 参数为一个实现了Collection接口的ArrayList
7. clear()清空
8. isEmpty()判断是否为空
9. containsAll()查找多个元素是否都存在 参数为一个实现了Collection接口的ArrayList

1.2 继承了Iterable接口

1. 由于Collection实现了Iterable接口，所以所有实现了Collection接口的集合类都有一个iterator()方法，返回一个实现了Iterator接口的对象，即迭代器；
2. iterator.next()取不到值的时候，NoSuchElementException；

1.3 Collection接口遍历元素的方法

1.3.1 Iterator迭代器

Iterator对象称为迭代器，主要用于遍历Collection集合中的元素；所有实现了Collection接口的实现类都有这个方法；(shortcuts: itit)

1. 遍历collection集合，得到collection对象对应的迭代器；iterator.next()，返回下一个元素，类型Object； obj编译类型是Object，运行类型是实际存的对象；
2. 如果要再次遍历，需要重置迭代器； 当迭代器到达最后一个元素时，重置迭代器

1.3.2 增强for循环

1. 增强for循环底层仍然是用的迭代器；所以可以认为增强for循环就是简化版的迭代器遍历；(shortcuts: I、iter) 返回一个Iterator对象； 调用iterator.hasNext()方法,判断是不是集合中的最后一个对象； 如果不是，调用iterator.next()取得下一个对象；

1.4 List接口

List支持索引；

1. List接口中的元素是有序的(添加顺序和取出顺序一致)，并且元素可以重复；
2. List集合中的每个元素都有其对应的顺序索引，List支持索引，索引从0开始；

1.4.1 List常用方法

1. void add(int index, Object ele); 在index位置插入ele对象；如果没有index，则默认在最后插入；
2. addAll(int index, Collection c);从index处将集合c中所有的元素添加进来； boolean addAll(int index, Collection c); boolean addAll(Collection c);
3. int indexOf(Object o); 返回o对象在集合中首次出现的索引；
4. int lastIndexOf(Object o);返回o对象在集合中最后一次出现的索引；
5. Object remove(int index); 移除给定索引处的元素，并返回该元素 boolean remove(Object o);
6. Object set(int index, Object ele); 设置index处的元素为ele，相当于替换 index不可以越界：IndexOutOfBoundsException
7. List subList(int fromIndex, int toIndex); 截取fromIndex到toIndex的元素，返回一个集合 前闭后开，fromIndex <= 返回的元素 < toIndex; [fromIndex, toIndex);

1.4.2 List接口遍历元素的方法

1. Iterator迭代器
2. 增强for循环
3. 普通for循环

1.4.3 ArrayList类

1. ArrayList 线程不安全,Vector 线程安全；
2. ArrayList中维护了一个Object类型的数组elementData；transient Object[] elementData;（transient修饰的属性表示这个属性不会被序列化）；
3. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData的容量为0；第一次添加时，elementData扩容为10，第二次添加时，elementData则扩容为原来的1.5倍；
4. 如果使用的是指定大小的构造器，则初始elementData为指定大小，如果需要扩容，则直接扩容为原来的1.5倍；

1.4.3.1 ArrayList底层源码，1.5倍扩容，Object[]数组

transient 瞬间；短暂的
final DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 0；
final DEFAULT_CAPACITY = 10;

privatestaticintcalculateCapacity(Object[] elementData,int minCapacity){if(elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){returnMath.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;}privatevoidensureCapacityInternal(int minCapacity){//calculateCapacity()返回的是10或者elementData数组的容量ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}privatevoidensureExplicitCapacity(int minCapacity){
        modCount++;// overflow-conscious codeif(minCapacity - elementData.length >0)grow(minCapacity);}privatevoidgrow(int minCapacity){// overflow-conscious codeint oldCapacity = elementData.length;//向右移动一位，除以2，1.5倍int newCapacity = oldCapacity +(oldCapacity >>1);if(newCapacity - minCapacity <0)
            newCapacity = minCapacity;if(newCapacity -MAX_ARRAY_SIZE>0)
            newCapacity =hugeCapacity(minCapacity);// minCapacity is usually close to size, so this is a win:
        elementData =Arrays.copyOf(elementData, newCapacity);}publicArrayList(int initialCapacity){if(initialCapacity >0){this.elementData =newObject[initialCapacity];}elseif(initialCapacity ==0){this.elementData =EMPTY_ELEMENTDATA;}else{thrownewIllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);}}

1. 使用无参构造器创建ArrayList源码 1.1 创建了一个空的elementData数组 1.2 先确定是否要扩容；然后然后再执行赋值操作 1.3 ensureCapacityInternal(): 该方法确定minCapacity(最小容量) (1) 第一次扩容为10 1.4 (1) modCount++；modCount用来记录当前这个集合被修改的次数，防止被多线程操作； (2) 如果elementData容量不够，就调用grow()去扩容 1.5 使用扩容机制来确定要扩容到多大； (1) 第一次扩容后newCapacity=10； 原因：elenmentData数组的长度为0，赋给oldCapacity；oldCapacity向右移一位，即: oldCapacity + oldCapacity / 2，赋给newCapacity，则newCapacity的值还为0；此时minCapacity为10，newCapacity < minCapacity，所以将minCapacity赋给newCapacity。 (2) 第二次扩容及其以后，按照1.5倍扩容； (3) 扩容使用的是Arrays.copyOf(); 保证原来数据安全的情况下，再增加空间； 1.6. Idea再Debug情况下，显示的数据默认是已简化的，如果希望看到完成的数据，需要做设置
2. 使用有参构造器创建和使用ArrayList 2.1 创建了一个指定大小的elementData数组(Object[capacity]) 如果是有参的构造器，那么扩容机制是：第一次按照elementData的1.5倍扩容，整个执行流程还是和前面一样；

1.4.4 Vector类

1. Vector类底层也是一个对象数组；protected Object[] elementData;

2. Vector是线程同步的，即线程安全，Vector常用方法都带有synchronized；

1.4.4.1 Vector底层源码，2倍扩容

1. 使用无参构造器创建Vector 1.1 new Vector()底层：调用无参构造器，初始容量为10，initialCapacity=10； Vector(int)，调用一个参数的构造器 Vector(int,int)，调用两个参数的构造器1.2 执行add()操作； 1.3 确定是否需要扩容【minCapacity - elementData.length > 0】 1.4 如果需要的elementData大小不够用，就扩容2倍； newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
2. 使用有参构造器创建Vector，初始容量为指定大小；
3. 使用两个参数的构造器：Vector(int,int)，可以自定义扩容步长； capacityIncrement > 0 ? capacityIncrement : oldCapacity

1.4.4.2 ArrayList 和Vector比较

〇底层结构版本线程安全(同步)效率扩容倍数ArrayList可变数组Object[]jdk1.2不安全，效率高(无参)10➡15➡22➡33➡49Vector可变数组Object[]jdk1.0安全，效率低(无参)10➡20➡40➡80➡160

1. Vector如果是无参构造器，则默认初始容量为10，之后扩容按照2倍扩容； 如果是有参构造器则第一次指定大小，之后扩容按照2倍扩容；
2. ArrayList第一次扩容为10，第二次扩容及其以后，按照1.5倍扩容；

1.4.5 LinkedList类

1. LinkedList中维护了两个属性first和last，分别指向首结点和尾结点；
2. 每个节点中(Node对象)，又维护了prev、next、item三个属性；其中通过prev指向前一个，通过next指向后一个，最终实现双向链表；
3. 所有LinkedList的元素的添加和删除，不是通过数组完成的，所以效率极高；
4. LinkedList也是线程不安全的；

1.4.5.1 简单实现双向链表

• 从头到尾循环链表
• 从尾到头循环链表
• 添加节点

1.4.5.2 LinkedList底层源码，没有扩容，双向链表

1. 调用无参构造器后LinkedList的属性first=null，last=null size大小为0，只是做了一个初始化 1.2 执行add方法； 1.2.1 添加第一个节点，加入到双向链表的最后； 1.2.2 LinkedList的first属性和last属性都指向了同一个节点，这个节点两头为空，item值为1； 1.2.3 内存布局图： 1.2.4 向链表添加第二个节点
2. remove()，默认删除第一个节点；（新版本遗弃了此方法） 2.1 首先让f指向first，即f指向了第一个节点； 2.2 将f.next即第二个节点赋给了next 2.3 将第一个节点的item和next置空 2.4 first指向next，即first也指向了第二个节点 2.5 将next.pre置空，此时第一个节点成为垃圾；
3. linkedList.set(1,999); 修改某个节点对象；索引从0开始；
4. linkedList.get(1); 取得第二个节点对象；

1.4.5.3 ArrayList和LinkedList比较

〇底层结构增删的效率改查的效率ArrayList可变数组较低，涉及数组扩容较高LinkedList双向链表较高，通过链表追加较低

1.5 Set接口，不提供索引

1. Set接口是无序的（添加顺序和取出顺序不一致），原因： 添加元素时，会根据元素的哈希值进行排序；排序后，位置就固定了；
2. 不允许重复元素，最后只能包含一个null；
3. Set接口的实现类没有索引；
4. Set接口的遍历方式

• 迭代器
• 增强for循环

1. HashSet底层机制: HashMap，即：数组+链表+红黑树

1.5.1 HashSet

1.5.1.1 简单实现数组+链表

1. 数组+链表

1.5.1.2 HashSet底层机制，数组+链表+红黑树

LinkedList、HashSet和HashMap都是在添加元素时初始化大小的，只有Vector是通过无参构造器初始化容量的；
final Object PRESENT = new Object();
final DEFAULT_LOAD_FACTOR=0.75;
final DEFAULT_INITIAL_CAPACITY = 1 << 4;//16

tips:

1. HashSet的底层是HashMap；
2. HashSet添加元素时，先得到hash值，根据hash值 &（n-1）得到索引值；
3. 找到存储数据的数组[表]table，看这个索引位置是否已经有元素； (1)如果没有，直接添加； (2)如果有，调用equals方法[程序员自己定义]比较，如果相同，放弃添加; 如果不相同，添加到最后；
4. 在jdk8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认值是8）[即到第九个元素时],并且table数组的大小 >= MIN_TREEIFY_CAPACITY（默认是64），就会转化成红黑树； 实操：
5. 调用HashSet无参构造器 调用HashMap的构造器，将加载因子赋予0.75
6. 执行第一个add(“java”)方法，（e就是加的元素） private static final Object PRESENT = new Object(); 起到占位作用； 2.1 进入到put方法; key=e=“java”，value=PRESENT 2.2 进入到hash(key)方法 如果key=null，返回一个0； 如果key不等于null，将key的hashCode无符号右移十六位（防止冲突），返回key的哈希值； 2.3 进入到putVal()方法 2.4 如果table的大小为0，进入到resize()方法，给table赋DEFAULT_INITIAL_CAPACITY（16）tips: (n - 1) & hash 决定key的索引（即应该在table的哪个位置存放） table是HashMap里的属性，是存放节点的数组 这是HashMap留给子类(比如linkedHashMap)实现的一个方法
7. 执行第二个add(“php”)方法
8. 执行第三个add(“java”)方法

finalVputVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict){Node<K,V>[] tab;Node<K,V> p;int n, i;//定义了辅助变量//table 就是 HashMap的一个属性，类型是 Node[]，存放节点的数组//if语句表示如果当前这个table是空或者大小为0//  就第一次扩容到16if((tab = table)==null||(n = tab.length)==0)
                n =(tab =resize()).length;//(1)根据key得到的哈希值去计算 该key应该存放到table表的哪个索引//   并且把这个索引位置的对象赋给辅助变量p//(2)接下来就要判断这个索引位置的对象(即p)是否为空//如果p为null(表示这个索引位置还没有存放数据),将创建一个Node(key="java",value=PRESENT)//放在该位置tab[i] = newNode(hash, key, value, null);//   Node(hash,key,value,null)//          这个value只起到占位作用[value=PRESENT]//          这个哈希值用于比较下一次存放的key和这个key是否相等//          null就是nextif((p = tab[i =(n -1)& hash])==null)
                tab[i]=newNode(hash, key, value,null);else{//一个开发技巧tip：在需要局部变量(辅助变量)的时候，再创建Node<K,V> e;K k;//老韩的理解：//如果当前索引位置对应的链表的第一个元素和准备添加进来的key哈希值相同//并且满足下列条件之一：//  条件一：如果准备加入的key和(即p指向的Node节点处的key)这个索引处的key是同一个对象//  条件二：或着p指向的Node节点的key经equals方法和准备加入的key比较后相同(不是同一个对象，但是内容相同)//则不能在此处添加//自己的理解：//就是判断这个索引处的对象是否为空，如果不为空，且两个key哈希值相同，//且经equals()比较内容也相同[程序员自己定义标准]，则不能在此处添加//总结：第一个if语句判断和表的第一个节点是否相同，不同则要考虑表的情况进行添加操作//     如果表是红黑树，则执行putTreeVal()方法添加//     如果不是红黑树，则判断key和每一个节点是否都相同，如果没有相同的则添加在末尾if(p.hash == hash &&//[自己的理解]这个if里的语句就是如果两个即传进来的key和p指向的位置的第一个节点完全一样，则不能在此处添加((k = p.key)== key ||(key !=null&& key.equals(k))))
                    e = p;//这里判断p是否是一颗红黑树//  如果是一颗红黑树，就调用putTreeVal方法来进行比较添加elseif(p instanceofTreeNode)
                    e =((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else{//如果table对应的索引位置已经是一个链表，就使用for循环依次比较//  (1)依次和该链表的每一个节点比较后都不相同，则添加在链表末尾;//     注意在把元素添加到链表末尾后，立即判断 该链表是否已经达到8个节点//     如果达到8个节点，就调用treeifyBin() 对当前这个链表进行树化(转成红黑树)//     注意，在转成红黑树时，还进行一个判断：//     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))//          resize();//     如果上面条件成立，对table表扩容。//     只有上面条件不成立时，才转成红黑树；//  (2)依次和该链表的每一个节点比较，如果有相同的情况，直接breakfor(int binCount =0;;++binCount){if((e = p.next)==null){//e可以当作一个指针，比较完之后通过p.next指向下一个节点
                            p.next =newNode(hash, key, value,null);//加到链表末尾if(binCount >=TREEIFY_THRESHOLD[8]-1)// -1 for 1sttreeifyBin(tab, hash);break;//从这里退出循环e为空}if(e.hash == hash &&((k = e.key)== key ||(key !=null&& key.equals(k))))break;//从这里退出循环e不为空
                        p = e;}}if(e !=null){// existing mapping for keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)
                        e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//size 每加入一个Node(h,k,v,next)节点, size++if(++size > threshold)resize();afterNodeInsertion(evict);returnnull;}

1.5.1.3 HashSet扩容+红黑树机制

1. //容量: 0->16->32->64->128 //临界值:0->12->24->48->96 HashSet底层是HashMap，第一次添加时，table数组扩容到16，临界值(threshold)是12;
2. 如果table数组元素增加到了临界值12，就会扩容到16 * 2=32，新的临界值就是32*0.75=24，依此类推；
3. 在jdk8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认值是8）[即到第九个元素时],并且table数组的大小 >= MIN_TREEIFY_CAPACITY（默认是64），就会转化成红黑树；否则仍然采用数组扩容机制
4. 每加入一个Node(h,k,v,next)节点, size就会++

publicclassHashSetIncrement{publicstaticvoidmain(String[] args){HashSet hashSet =newHashSet();for(int i =1; i <=100; i++){
            hashSet.add(newDog(i));}System.out.println(hashSet);}}classDog{privateint age =1;publicDog(int age){this.age = age;}@OverridepublicinthashCode(){return100;}}

练习题

1. 重写equals方法，两个都勾选，说明只有两个字段都相同equals才返回true；
2. 重写hashCode方法，两个都勾选，说明只有两个字段都相同hashCode才返回true；

1.5.2 LinkedHashSet

1. LinkedHashSet是HashSet的子类;
2. LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表;
3. LinkedHashSet使用双向链表维护元素的次序，所以元素看起来是以插入顺序保存的；（取出顺序和插入顺序一致）
4. LinkedHashSet根据元素的hashCode值来决定元素的存储位置;
5. LinkedHashSet不允许重复元素； (LinkedHashSet有head和tail)；

1.5.2.1 数组+双向链表

1. 每一个节点都有before和after属性，这样可以形成双向链表；
2. 在添加一个元素时，先求hash值，再求索引，确定该元素在table中的位置，然后将添加的元素加入到双向链表，如果已经存在(原则和HashSet一致)，则放弃添加；这样在遍历LinkedHashSet是也能确保插入顺序和遍历顺序一致； tail.after = newElement; newElement.before = tail; tail = newElement;
3. 第一次添加时将数组扩容到16；
4. 数组类型是HashMap$Node[]；存放的节点类型是LinkedHashMap$Entry;Entry是一个静态内部类，实现了双向链表，Node只是单向链表； 只确定了loadfactor和threshold LinkedHashSet底层维护的是LinkedHashMap（是HashMap的子类） LinkedHashMap底层维护的是HashMap：数据+双向链表 数组类型是HashMap$Node, 数组存放的节点类型是LinkedHashMap$Entry ➡(多态数组) 原因：LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>

1.5.3 TreeSet

当使用无参构造器创建TreeSet并添加元素的时候，插入顺序和取出顺序不一致（这是因为TreeSet会默认按照传入的key从小到大排序）
原因：创建TreeSet对象时如果传入了一个Comparator对象，就用实现的compare方法比较；如果没有传入Comparator对象，则以添加对象的实现的Comparable接口的compareTo方法比较；

当传入第一个元素时，若这个元素没有实现Comparable接口，则会报错


以后传入的对象如果没有实现Comparable接口，也会报类转换异常ClassCastException

解决方案：让对象实现Comparable接口，重写compareTo方法；
去重机制：
创建TreeSet对象时如果传入了一个Comparator对象，就用实现的compare方法去除重复元素，如果方法返回0，就认为不应该添加；如果没有传入Comparator对象，则以添加对象的实现的Comparable接口的compareTo方法去除重复元素；

1. 使用无参构造器创建TreeSet并添加元素
2. 使用TreeSet 提供的一个有参构造器，传入一个比较器(匿名内部类)，指定一个排序规则 treeSet底层是treeMap； treeSet构造器，把传入的实现了 Comparator接口的匿名内部类传给了TreeMap的属性comparator； 当调用treeSet.add()方法时，在底层会执行到: 能不能加得进去，要看compare()比较的内容，如果内容相等，即cmp返回0，这个key就不会加入 在这里会动态绑定到：匿名内部类的compare()方法 这里是长度相等就相同，所以长度相等的加不进去；

2. 双列集合(Map)：

• 指的是在集合里面放的是键值对
• Map 接口的实现子类是双列集合，存放的是 k-v
• Map接口没有继承迭代器，不能使用迭代器遍历，也不能使用增强for循环遍历

2.1 Map接口实现类的特点

1. Map用于保存具有映射关系的数据Key-Value；
2. Map中的key、value可以是任意引用类型，封装进HashMap的Node内部类中；
3. Map中的数据key不允许重复,原因：根据hash值和equals判断
4. 当有相同的key时，就相当于替换value值
5. Map中的value值可以重复；
6. Map【Hashtable、Properties除外】中的key、value都可以为null，但key只能有一个null，value可以有多个；
7. 习惯是key放字符串，但是key可以放任意类型
8. 通过get()方法传入一个key，返回key对应的value，value只有一个；
9. k-v 最后都是 HashMap$Node node = newNode(hash,key,value,null);
10. k-v 为了方便程序员的遍历，还会创建 EntrySet 集合，该集合存放的元素的类型是 Entry, 而一个Entry对象就有k,v -> EntrySet<Entry<K,V>>
11. 在EntrySet中，定义的类型是 Map.Entry,但是实际上存放的还是HashMap$Node,这是因为HashMap$Node 实现了 Map.Entry接口
12. 把HashMap$Node 对象 存放到entrySet集合，方便我们的遍历，因为Map.Entry提供了重要的方法
13. HashMap没有做同步互斥，没有syntronized，因此是线程不安全的；

@SuppressWarnings({"all"})publicclassMapSource{publicstaticvoidmain(String[] args){Map map =newHashMap();
        map.put("No1","scott");
        map.put("No2","zzw");
        map.put(newPerson("zzw"),newCar());//1.k-v 最后都是 HashMap$Node node = newNode(hash,key,value,null)//2.k-v 为了方便程序员的遍历，还会创建 EntrySet 数组，该集合存放的元素的类型是 Entry，但元素的运行类型是Node//  而一个Entry对象就有k,v EntrySet<Entry<K,V>>//  即：transient Set<Map.Entry<K,V>> entrySet;//3.在EntrySet中，定义的类型是 Map.Entry,但是实际上存放的还是HashMap$Node//  这是因为HashMap$Node 实现了 Map.Entry接口//4.把HashMap$Node 对象 存放到entrySet，方便我们的遍历，因为Map.Entry提供了重要的方法//  K getKey();//  V getValue();Set set = map.entrySet();System.out.println(set.getClass());//HashMap$EntrySet 是HashMap的一个内部类for(Object obj : set){System.out.print(obj +" ");System.out.println(obj.getClass());//HashMap$Node//为了从HashMap$Node中取出k-v//1.先向下转型Map.Entry entry =(Map.Entry) obj;System.out.println(entry.getKey());System.out.println(entry.getValue());}Set set1 = map.keySet();System.out.println(set1.getClass());//HashMap$KeySetCollection values = map.values();System.out.println(values.getClass());//HashMap$Values}}classPerson{privateString name;publicPerson(String name){this.name = name;}}classCar{}

2.2 Map常用方法，不支持索引

1. put(key,value) 添加键值对
2. remove(k,v) remove(k)
3. get(k)
4. size() 获取k-v个数
5. isEmpty() 是否为空
6. clear() 清空键值对
7. containsKey():查找键是否存在

2.3 Map接口三组遍历方法

2.3.1 keySet+增强for循环

2.3.2 keySet+迭代器

2.3.3 values()+增强for循环

2.3.4 values()+迭代器

2.3.5 EntrySet+增强for循环

2.3.6 EntrySet+迭代器

2.4 HashMap扩容机制

1. HashMap底层维护了Node类型的数组table，默认为null；
2. 当创建HashMap对象时，将加载因子(loadfactor)初始化为0.75；
3. 当添加k，v时，通过key的哈希值得到在table的索引，然后判断该索引处是否有元素。如果没有元素，则直接添加； 如果有元素，则判断该索引处的key是否和准备加入的key相等； 如果key相同，则执行完if语句直接跳到，替换value【e.value = value;】 如果key不相同，需要判断是树结构，还是链表结构，然后做出相应处理； 树结构 链表结构中，如果每个元素的key都不相同，则会一直循环到链表的最后 添加时，发现容量不对，则需要扩容；
4. 第一次添加，需要将table扩容为16，临界值threshold为12,； 以后再次扩容，则需要将table扩容为2倍；临界值也变为原来的2倍，即24，以此类推；
5. 在java8中，如果在binCount到达TREEIFY_THRESHOLD-1，即一条链表的元素超过TREEIFY_THRESHOLD（默认为8）， 个数： 2 3 4 5 6 7 8 9 binCount: 0 1 2 3 4 5 6 7 并且table表的大小超过MIN_TREEIFY_CAPACITY（默认为64），就会进行树化，变为红黑树；

1. 如果底层的table 数组为null，或者 length=0，则扩容到16，调用resize()方法;
2. 取出hash值对应的table的索引位置的Node，如果为null，就直接把加入的k-v创建成一个Node，加入即可； tab[i] = newNode(hash, key, value, null);
3. 如果key相同，则替换value【e.value = value;】 走到e != null，说明那个位置有元素并且元素相同，所以在这里不在添加；这段代码专门替换value值；
4. 剪枝：红黑树删除节点到一定数量之后转为链表；

publicclassHashMapSource01{publicstaticvoidmain(String[] args){Map hashMap =newHashMap();for(int i =1; i <=12; i++){
            hashMap.put(newDog(i),"zze");}Set entrySet = hashMap.entrySet();for(Object entry : entrySet){System.out.println(entry);}}}//所有的Dog对象的hashCode都一样classDog{privateint age;publicDog(int age){this.age = age;}@OverridepublicinthashCode(){return100;}@OverridepublicStringtoString(){return"Dog{"+"age="+ age +'}';}}

2.5 Hashtable扩容机制(数组+链表)

1. Hashtable存放的元素是键值对，使用方法基本上和HashMap一致；
2. Hashtable的键和值都不能为null，否则会抛出NullPointerException；
3. Hashtable是线程安全的，HashMap是线程不安全的；
4. Hashtable底层有一个 Hashtable$Entry的数组。第一次初始化大小为11，临界值是8； threshold = 11 * 0.75； Hashtable 底层维护的是一个Hashtable$Entry
5. 第二次扩容 table大小：11-》23 临界值：8 -》17
6. 扩容会执行addEntry(hash,key,value,index); 当数量大于等于临界值时，扩容 大小变为原来的2倍+1；newCapacity = (oldCapacity << 1) + 1;

2.5.1 Hashtable与HashMap比较

〇版本线程安全(同步)效率允许键为null，值为nullHashMapjdk1.2不安全效率高可以Hashtablejdk1.0安全效率低不可以Hashtable扩容机制容量11➡23➡47➡95临界值8➡17➡35➡71

2.5.2 Properties实现类(继承Hashtable)

1. Properties类继承Hashtable类并实现了Map接口，也是使用键值对的形式来存储数据；使用特点和Hashtable相似；
2. Properties还可以用于 从某个后缀名为properties的文件中，加载数据到Properties对象，并进行读取和修改；
3. Properties不允许键值为null；键或值为空会抛异常NullPointerException
4. xxx.properties文件常常作为配置文件【IO流】；

1. put()；添加键值对，及修改value值
2. get(key)方法，获取value
3. remove()； 删除键值对 remove(Object key) boolean remove(Object key, Object value)

2.6 treeMap

当使用无参构造器创建TreeSet并添加元素的时候，插入顺序和取出顺序不一致（这是因为TreeSet会默认从小到大升序排序）
第一次添加时，把key、value封装到Entry对象，放入root

第二次添加时，遍历所有的key

3. 小结

集合类扩容机制红黑树机制ArrayList第一次添加时，elementData扩容为10，第二次扩容时，elementData则扩容为原来的1.5倍；-----Vector第一次初始化elementData为10，如果需要的elementData大小不够用，就扩容2倍；(可自定义容量增量)-----LinkedList✖-----HashSet(HashMap)第一次添加时，table数组扩容到16，临界值为12；第二次扩容时，table数组扩容为原来的2倍
容量: 0->16->32->64->128，临界值:0->12->24->48->96-----Hashtable第一次添加时，table数组扩容到11，临界值为8；第二次扩容时，table数组扩容为原来的（2倍+1）,临界值变为原来的(2倍+1)
容量: 11->23->47->95，临界值:8->17->35->71-----
在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行选择，如下：

1. 先判断存储的类型：（一组对象即单列；一组键值对即双列）
2. 一组对象[单列]：Collection接口 - 允许重复：List - 增删多：LinkedList 【底层维护了一个双向链表】- 改查多：ArrayList 【底层维护了Object类型的可变数组】- 不允许重复：Set - 无序：HashSet 【底层是HashMap，维护了一个哈希表，即数组+链表+红红黑树】- 排序：TreeSet- 插入和取出顺序一致：LinkedHashSet，【底层维护的是数组+双向链表】
3. 一组键值对[双列]：Map 3.1 键无序：HashMap【底层：哈希表 jdk7：数组+链表，jdk8：数组+链表+红黑树】 3.2 键排序：TreeMap 3.3 键插入和取出顺序一致：LinkedHashMap 读取文件：Properties

3.1 Collections集合工具类

3.1.1 Collections.reverse()，反转集合

3.1.2 Collections.shuffle()，打乱集合顺序

3.1.3 Collections.sort(list); 默认按照字符串大小升序排列

Comparator接口匿名内部类的用法👉传送门

Collections.sort(list, Comparator comparator); 自定义排序规则
1)我们希望按照字符串的长度大小排序

3.1.4 swap(list, int, int)；将指定集合中的i处元素和j处元素互换

3.1.5 Collections.max(collection); 根据元素的自然顺序，返回指定集合中的最大值

Collections.max(collection, Comparator comparator); 自定义排序，返回指定集合中的最大值

1. Collections.min(collection); 根据元素的自然顺序，返回指定集合中的最小值 Collections.min(collection, Comparator comparator); 自定义排序，返回指定集合中的最小值

3.1.6 Collection.frequency(collection，Object); 返回指定集合中指定元素出现的次数

3.1.7 Collections.copy(List dest, List src); 把src集合中的数据拷贝到dest中去

3.1.8 Collections.replaceAll(List list, oldVal, newVal)；用newVal替换集合中的oldVal

3.2 史上巨坑题

publicclassHomework06{publicstaticvoidmain(String[] args){HashSet set =newHashSet();Person p1 =newPerson(1001,"AA");Person p2 =newPerson(1002,"BB");
        set.add(p1);//HashMap$Node tab[i] = newNode(hash, 1001, "AA", null);
        set.add(p2);//HashMap$Node tab[i] = newNode(hash, 1002, "BB", null);
        p1.name ="CC";
        set.remove(p1);//此时p1的哈希值改变了System.out.println(set);//p1,p2
        set.add(newPerson(1001,"CC"));//trueSystem.out.println(set);
        set.add(newPerson(1001,"AA"));//true}}classPerson{privateint id;publicString name;publicPerson(int id,String name){this.id = id;this.name = name;}@OverridepublicStringtoString(){return"Person{"+"id="+ id +", name='"+ name +'\''+'}';}@Overridepublicbooleanequals(Object o){if(this== o){returntrue;}if(o ==null||getClass()!= o.getClass()){returnfalse;}Person person =(Person) o;return id == person.id &&Objects.equals(name, person.name);}@OverridepublicinthashCode(){returnObjects.hash(id, name);}}