容器【双例集合、TreeMap容器的使用、 Iterator接口、Collections工具类】(四)-全面详解（学习总结---从入门到深化）

灰太狼 2023-10-13 15:44 37阅读 0赞

## ![174acfb63e1e4d349ebb0149513bed12.gif][] ##

![29ec4a888e384f76bfdf06fb7870c84a.png][]

**目录**

通过元素自身实现比较规则

通过比较器实现比较规则

双例集合

TreeMap容器的使用

Iterator接口

Collections工具类

--------------------

## 通过元素自身实现比较规则 ##

![8084f2532477425f978b67b4cbf69208.png][]

在元素自身实现比较规则时，需要实现Comparable接口中的 compareTo方法，该方法中用来定义比较规则。TreeSet通过调用 该方法来完成对元素的排序处理。

**创建Users类**

public class Users implements Comparable<Users>{
        private String username;
        private int userage;
        public Users(String username, intuserage) {
            this.username = username;
            this.userage = userage;
       }
       public Users() { }
      
      @Override
        public boolean equals(Object o) {
            System.out.println("equals...");
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Users users = (Users) o;
            if (userage != users.userage) return false;
            return username != null ? username.equals(users.username) : users.username == null;
       }
        @Override
        public int hashCode() {
            int result = username != null ? username.hashCode() : 0;
            result = 31 * result + userage;
            return result;
       }
        public String getUsername() {
            return username;
       }
    
       public void setUsername(String username)
        {
            this.username = username;
       }
       
       public int getUserage() {
            return userage;
       }
       
       public void setUserage(int userage) {
            this.userage = userage;
       }
       
     @Override
      public String toString() {
            return "Users{" +
                    "username='" + username + '\'' +
                    ", userage=" + userage +
                    '}';
       }
        //定义比较规则
        //正数：大，负数：小，0：相等
        @Override
        public int compareTo(Users o) {
            if(this.userage > o.getUserage()){
                return 1;
           }
            if(this.userage == o.getUserage()){
               return this.username.compareTo(o.getUsername());
          }
            return -1;
       }
    }

Set<Users> set1 = new TreeSet<>();
    Users u = new Users("oldlu",18);
    Users u1 = new Users("admin",22);
    Users u2 = new Users("sxt",22);
    set1.add(u);
    set1.add(u1);
    set1.add(u2);
    for(Users users:set1){
        System.out.println(users);
    }

## 通过比较器实现比较规则 ##

![a16592f90b114bbabf49c6b1ad5dbddc.png][]

通过比较器定义比较规则时，我们需要单独创建一个比较器，比较 器需要实现Comparator接口中的compare方法来定义比较规则。 在实例化TreeSet时将比较器对象交给TreeSet来完成元素的排序处 理。此时元素自身就不需要实现比较规则了。

**创建Student类**

public class Student {
        private String name;
        private int age;
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
       }
        public Student() { }
        
      @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", 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 boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            if (age != student.age) return false;
            return name != null ? name.equals(student.name) : student.name == null;
       }
        @Override
        public int hashCode() {
            int result = name != null ? name.hashCode() : 0;
            result = 31 * result + age;
            return result;
       }
    }

**创建比较器**

public class StudentComparator implements Comparator<Student> {
        //定义比较规则
        @Override
        public int compare(Student o1, Student o2) {
            if(o1.getAge() > o2.getAge()){
                return 1;
           }
           
            if(o1.getAge() == o2.getAge()){
                return o1.getName().compareTo(o2.getName());
           }
          return -1;
       }
    }

public class TreeSetTest3 {
        public static void main(String[] args) {
            //创建TreeSet容器，并给定比较器对象
            Set<Student> set = new TreeSet<>(new StudentComparator());
            Student s = new Student("oldlu",18);
            Student s1 = new Student("admin",22);
            Student s2 = new Student("sxt",22);
            set.add(s);
            set.add(s1);
            set.add(s2);
            for(Student student:set){
                System.out.println(student);
           }
       }
    }

**TreeSet底层源码分析**

**成员变量**

/**
    * The backing map.
    */
    private transient NavigableMap<E,Object> m;
    
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

**构造方法**

public TreeSet() {
        this(new TreeMap<E,Object>());
    }

**添加元素**

/**
    * Adds the specified element to this set if it is not already present.
    * More formally, adds the specified element <tt>e</tt> to this set if
    * this set contains no element <tt>e2</tt> such that
    * <tt>(e==null ?  e2==null : e.equals(e2))</tt>.
    * If this set already contains the element, the call leaves the set
    * unchanged and returns <tt>false</tt>.
    *
    * @param e element to be added to this set
    * @return <tt>true</tt> if this set did not already contain the specified
    * element
    */
    
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

**单例集合使用案例**

> 需求： 产生1-10之间的随机数(\[1,10\]闭区间)，将不重复的10个随机数放到 容器中。

**使用List类型容器实现**

public class ListDemo {
        public static void main(String[] args) {
            List<Integer> list = new ArrayList<>();
           while(true){
               //产生随机数
               int num = (int) (Math.random()*10+1);
                //判断当前元素在容器中是否存在
               if(!list.contains(num)){
                    list.add(num);
               }
               //结束循环
               if(list.size() == 10){
                   break;
               }
           }
           for(Integer i:list){
               System.out.println(i);
           }
       }
    }

**使用Set类型容器实现**

public class SetDemo {
        public static void main(String[] args) {
            Set<Integer> set = new HashSet<>();
            while(true){
                int num = (int)(Math.random()*10+1);
                //将元素添加容器中，由于Set类型容器是、不允许有重复元素的，所以不需要判断。
                set.add(num);
                //结束循环
                if(set.size() == 10){
                    break;
               }
           }
            for(Integer i:set){
                System.out.println(i);
           }
       }
    }

## 双例集合 ##

![7788923995b647398df0b591f0bd0bd0.png][]

Map接口介绍

> Map接口定义了双例集合的存储特征，它并不是Collection接口的 子接口。双例集合的存储特征是以key与value结构为单位进行存 储。体现的是数学中的函数 y=f(x)感念。
> 
> Map与Collecton的区别：
> 
> 1、Collection中的容器，元素是孤立存在的（理解为单身），向集 合中存储元素采用一个个元素的方式存储。
> 
> 2、Map中的容器，元素是成对存在的(理解为现代社会的夫妻)。每 个元素由键与值两部分组成，通过键可以找对所对应的值。
> 
> 3、Collection中的容器称为单列集合，Map中的容器称为双列集 合。
> 
> 4、Map中的集合不能包含重复的键，值可以重复；每个键只能对应 一个值。
> 
> 5、Map中常用的容器为HashMap，TreeMap等。

**Map接口中常用的方法表**

![c03a66694dcb4b5fa4c0c42f1508f61d.png][]

**HashMap容器的使用**

HashMap采用哈希算法实现，是Map接口最常用的实现类。 由于 底层采用了哈希表存储数据，我们要求键不能重复，如果发生重 复，新的键值对会替换旧的键值对。 HashMap在查找、删除、修 改方面都有非常高的效率。

public class HashMapTest {
        public static void main(String[] args) {
            //实例化HashMap容器
            Map<String,String> map = new HashMap<>();
            //添加元素
            map.put("a","A");
            map.put("b","B");
            map.put("c","C");
            map.put("a","D");
            //获取容器中元素数量
            int size = map.size();
            System.out.println(size);
            System.out.println("---------------");
        
            //获取元素
            //方式一
            String v = map.get("a");
            System.out.println(v);
            System.out.println("---------------");
            
            //方式二
            Set<String> keys = map.keySet();
            for(String key:keys){
                String v1 = map.get(key);
                System.out.println(key+" ----"+v1);
           }
            System.out.println("-------------------");
            
            //方式三
            Set<Map.Entry<String,String>> entrySet = map.entrySet();
            for(Map.Entry<String,String> entry:entrySet){
                String key = entry.getKey();
                String v2 = entry.getValue();
                System.out.println(key+" ---------- "+v2);
           }
            System.out.println("--------------------");
            //Map容器的并集操作
            Map<String,String> map2 = new HashMap<>();
            map2.put("f","F");
            map2.put("c","CC");
            map.putAll(map2);
            Set<String> keys2 = map.keySet();
            for(String key:keys2){
                System.out.println("key: "+key+" Value: "+map.get(key));
           }
            System.out.println("---------------");
            //删除元素
            String v3 = map.remove("a");
            System.out.println(v3);
            Set<String> keys3 = map.keySet();
            for(String key:keys3){
                System.out.println("key: "+key+" Value: "+map.get(key));
           }
            System.out.println("-------------------");
            //判断Key是否存在
            boolean b = map.containsKey("b");
            System.out.println(b);
            //判断Value是否存在
            boolean cc = map.containsValue("CC");
            System.out.println(cc);
    
        }
    }

HashTable类和HashMap用法几乎一样，底层实现几乎一样，只不 过HashTable的方法添加了synchronized关键字确保线程同步检 查，效率较低。

> HashMap与HashTable的区别
> 
> 1 HashMap: 线程不安全，效率高。允许key或value为null
> 
> 2 HashTable: 线程安全，效率低。不允许key或value为null

**HashMap的底层源码分析**

**底层存储介绍**

> HashMap底层实现采用了哈希表，这是一种非常重要的数据结构。 对于我们以后理解很多技术都非常有帮助。 数据结构中由数组和链表来实现对数据的存储，他们各有特点。
> 
> (1) 数组：占用空间连续。 寻址容易，查询速度快。但是，增加和 删除效率非常低。
> 
> (2) 链表：占用空间不连续。 寻址困难，查询速度慢。但是，增加 和删除效率非常高。 那么，我们能不能结合数组和链表的优点（即查询快，增删效率也 高）呢？ 答案就是“哈希表”。 哈希表的本质就是“数组+链表”。

![15a98b888069487e8b7ba20685a969fc.png][]

>  **Oldlu建议**
> 
> 对于本章中频繁出现的“底层实现”讲解，建议学有余力的童鞋将 它搞通。刚入门的童鞋如果觉得有难度，可以暂时跳过。入门 期间，掌握如何使用即可，底层原理是扎实内功，便于大家应 对一些大型企业的笔试面试。

**HashMap中的成员变量**

/**
    * The default initial capacity - MUST be a power of two.
    */
    
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    /**
    * The maximum capacity, used if a higher value is implicitly specified
    * by either of the constructors with arguments.
    * MUST be a power of two <= 1<<30.
    */
    
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    /**
    * The load factor used when none specified in constructor.
    */
    
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
    * The bin count threshold for using a tree rather than list for a
    * bin. Bins are converted to trees when adding an element to a
    * bin with at least this many nodes. The value must be greater
    * than 2 and should be at least 8 to mesh with assumptions in
    * tree removal about conversion back to plain bins upon
    * shrinkage.
    */
    
    static final int TREEIFY_THRESHOLD = 8;
    /**
    * The bin count threshold for untreeifying a (split) bin during a
    * resize operation. Should be less than TREEIFY_THRESHOLD, and at
    * most 6 to mesh with shrinkage detection under removal.
    */
    
    static final int UNTREEIFY_THRESHOLD = 6;
    /**
    * The smallest table capacity for which bins may be treeified.
    * (Otherwise the table is resized if too many nodes in a bin.)
    * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
    * between resizing and treeification thresholds.
    */
    static final int MIN_TREEIFY_CAPACITY = 64;
    /**
    * The number of key-value mappings contained in this map.
    */
    
    transient int size;
    /**
    * The table, initialized on first use, and resized as
    * necessary. When allocated, length is always a power of two.
    * (We also tolerate length zero in some operations to allow
    * bootstrapping mechanics that are currently not needed.)
    */
    
    transient Node<K,V>[] table;

**HashMap中存储元素的节点类型**

**Node类**

static class Node<K,V> implements
    Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
       }
        
    public final K getKey()       { return key; }
        
    public final V getValue()     { return value; }
        
    public final String toString() { return key + "=" + value; }
        
    public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
        
    public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
       }
        
    public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))
                    return true;
           }
            return false;
       }
    }

**TreeNode类**

/**
    * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
    * extends Node) so can be used as extension of either regular or
    * linked node.
    */
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
       }
        /**
         * Returns root of tree containing thisnode.
         */
        final TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p;;) {
                if ((p = r.parent) == null)
                    return r;
                r = p;
           }
       }

它们的继承关系

![359c93b80ab440a4a734c36e56ffd947.png][]

**HashMap中的数组初始化**

> 在JDK1.8的HashMap中对于数组的初始化采用的是延迟初始化方 式。通过resize方法实现初始化处理。resize方法既实现数组初始 化，也实现数组扩容处理。

/**
    * Initializes or doubles table size. If null, allocates in
    * accord with initial capacity target held in field threshold.
    * Otherwise, because we are using power-oftwo expansion, the
    * elements from each bin must either stay at same index, or move
    * with a power of two offset in the new table.
    *
    * @return the table
    */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
           }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
       }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initialthreshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                     (int)ft : Integer.MAX_VALUE);
       }
        threshold = newThr;
      
    @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V> [])new Node[newCap];
            table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                       
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null,loTail = null;
                        Node<K,V> hiHead = null,hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail ==null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                           }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                           }
                       } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                       }
                       if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                       }
                   }
               }
           }
       }
        return newTab;
    }

**HashMap中计算Hash值**

> 1 获得key对象的hashcode
> 
> 首先调用key对象的hashcode()方法，获得key的hashcode值。
> 
> 2 根据hashcode计算出hash值(要求在\[0, 数组长度-1\]区 间)hashcode是一个整数，我们需要将它转化成\[0, 数组长度-1\] 的范围。我们要求转化后的hash值尽量均匀地分布在\[0,数组长 度-1\]这个区间，减少“hash冲突”
> 
> 2.1 一种极端简单和低下的算法是： hash值 = hashcode/hashcode; 也就是说，hash值总是1。意味着，键值对对象都会存储到 数组索引1位置，这样就形成一个非常长的链表。相当于每存 储一个对象都会发生“hash冲突”，HashMap也退化成了一个 “链表”。
> 
> 2.2 一种简单和常用的算法是（相除取余算法）: hash值 = hashcode%数组长度;
> 
> 这种算法可以让hash值均匀的分布在\[0,数组长度-1\]的区间。 但是，这种算法由于使用了“除法”，效率低下。JDK后来改进 了算法。首先约定数组长度必须为2的整数幂，这样采用位运 算即可实现取余的效果：hash值 = hashcode&(数组长 度-1)。

/**
    * Associates the specified value with the specified key in this map.
    * If the map previously contained a mapping for the key, the old
    * value is replaced.
    *
    * @param key key with which the specified value is to be associated
    * @param value value to be associated with the specified key
    * @return the previous value associated with <tt>key</tt>, or
    * <tt>null</tt> if there was no mapping for <tt>key</tt>.
    *         (A <tt>null</tt> return can also indicate that the map
    *         previously associated <tt>null</tt> with <tt>key</tt>.)
    */
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

/**
    * Implements Map.put and related methods
    *
    * @param hash hash for key
    * @param key the key
    * @param value the value to put
    * @param onlyIfAbsent if true, don't change existing value
    * @param evict if false, the table is in creation mode.
    * @return previous value, or null if none
    */
    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 ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                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);
                        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;
    }

**HashMap中添加元素**

/**
    * Associates the specified value with the specified key in this map.
    * If the map previously contained a mapping for the key, the old
    * value is replaced.
    *
    * @param key key with which the specified value is to be associated
    * @param value value to be associated with the specified key
    * @return the previous value associated with <tt>key</tt>, or
    *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
    *         (A <tt>null</tt> return can also indicate that the map
    *         previously associated <tt>null</tt> with <tt>key</tt>.)
    */
    
    public V put(K key, V value) {
        return putVal(hash(key), key, value,false, true);
    }

**HashMap中数组扩容**

/**
    * Implements Map.put and related methods
    *
    * @param hash hash for key
    * @param key the key
    * @param value the value to put
    * @param onlyIfAbsent if true, don't change
    existing value
    * @param evict if false, the table is in creation mode.
    * @return previous value, or null if none
    */
    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 ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
      tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
               ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                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);
                        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;
    }

/**
    * Initializes or doubles table size. If null, allocates in
    * accord with initial capacity target held in field threshold.
    * Otherwise, because we are using power-oftwo expansion, the
    * elements from each bin must either stay at same index, or move
    * with a power of two offset in the new table.
    *
    * @return the table
    */
    final Node<K,V>[] resize() {
         Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
           }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
       }
        else if (oldThr > 0) // initial capacity
            was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
            (int)ft : Integer.MAX_VALUE);
       }
        threshold = newThr;
      
    @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V> [])new Node[newCap];
            table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                       
                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                              if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                           }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                           }
                       } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                       }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                       }
                   }
               }
           }
       }
     return newTab;
    }

## TreeMap容器的使用 ##

![65388726e944404b99d88a4a0a64ed96.png][]

TreeMap和HashMap同样实现了Map接口，所以，对于API的用法 来说是没有区别的。HashMap效率高于TreeMap；TreeMap是可 以对键进行排序的一种容器，在需要对键排序时可选用TreeMap。 TreeMap底层是基于红黑树实现的。

> 在使用TreeMap时需要给定排序规则：
> 
> 1、元素自身实现比较规则
> 
> 2、通过比较器实现比较规则

**元素自身实现比较规则**

public class Users implements
    Comparable<Users>{
        private String username;
        private int userage;
    public Users(String username, int userage) {
            this.username = username;
            this.userage = userage;
       }
        public Users() { }
        @Override
        public boolean equals(Object o) {
            System.out.println("equals...");
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Users users = (Users) o;
            if (userage != users.userage) return false;
            return username != null ? username.equals(users.username) : users.username == null;
       }
        @Override
        public int hashCode() {
            int result = username != null ? username.hashCode() : 0;
            result = 31 * result + userage;
            return result;
    }
        public String getUsername() {
            return username;
       }
        public void setUsername(String username)
         {
            this.username = username;
         }
        public int getUserage() {
            return userage;
         }
        public void setUserage(int userage) {
            this.userage = userage;
       }
        @Override
        public String toString() {
            return "Users{" +
                    "username='" + username + '\'' +
                    ", userage=" + userage +
                    '}';
       }
        //定义比较规则
        //正数：大，负数：小，0：相等
        @Override
        public int compareTo(Users o) {
           if(this.userage < o.getUserage()){
                return 1;
           }
            if(this.userage == o.getUserage()){
               return this.username.compareTo(o.getUsername());
           }
            return -1;
       }
    }

public class TreeMapTest {
        public static void main(String[] args) {
            //实例化TreeMap
            Map<Users,String> map = new TreeMap<>();
            Users u1 = new Users("oldlu",18);
            Users u2 = new Users("admin",22);
            Users u3 = new Users("sxt",22);
            map.put(u1,"oldlu");
            map.put(u2,"admin");
            map.put(u3,"sxt");
            Set<Users> keys = map.keySet();
            for(Users key :keys){
                System.out.println(key+" --------- "+map.get(key));
           }
       }
    }

**通过比较器实现比较规则**

public class Student {
        private String name;
        private int age;
        public Student(String name, int age) {
            this.name = name;
            this.age = age;
       }
        public Student() { }
        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", 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 boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            if (age != student.age) return false;
            return name != null ? name.equals(student.name) : student.name == null;
       }
        @Override
        public int hashCode() {
            int result = name != null ? name.hashCode() : 0;
            result = 31 * result + age;
            return result;
       }
    }

public class StudentComparator implements Comparator<Student> {
        //定义比较规则
      @Override
        public int compare(Student o1, Student o2) {
            if(o1.getAge() > o2.getAge()){
                return 1;
           }
            if(o1.getAge() == o2.getAge()){
                return
               o1.getName().compareTo(o2.getName());
           }
            return -1;
       }
    }

public class TreeMapTest {
        public static void main(String[] args) {
              Map<Student,String> treeMap = new TreeMap<>(new StudentComparator());
        Student s1 = new Student("oldlu",18);
        Student s2 = new Student("admin",22);
        Student s3 = new Student("sxt",22);
        treeMap.put(s1,"oldlu");
        treeMap.put(s2,"admin");
        treeMap.put(s3,"sxt");
        Set<Student> keys1 = treeMap.keySet();
        for(Student key :keys1){
            System.out.println(key+" ----"+treeMap.get(key));
         }
       }
    }

**TreeMap的底层源码分析**

TreeMap是红黑二叉树的典型实现。我们打开TreeMap的源码，发 现里面有一行核心代码：

private transient Entry<K,V> root = null;

> root用来存储整个树的根节点。我们继续跟踪Entry（是TreeMap的 内部类）的代码：

![85990425bd67454f8ed1a8a42a9af398.png][]

> 可以看到里面存储了本身数据、左节点、右节点、父节点、以及节 点颜色。 TreeMap的put()/remove()方法大量使用了红黑树的理 论。在本节课中，不再展开。需要了解更深入的，可以参考专门的 数据结构书籍。 TreeMap和HashMap实现了同样的接口Map，因此，用法对于调 用者来说没有区别。HashMap效率高于TreeMap；在需要排序的 Map时才选用TreeMap。

## Iterator接口 ##

![528c0c744398468e9d9e1e4ae385d4a3.png][]

**Iterator迭代器接口介绍**

> Collection接口继承了Iterable接口，在该接口中包含一个名为 iterator的抽象方法，所有实现了Collection接口的容器类对该方法 做了具体实现。iterator方法会返回一个Iterator接口类型的迭代器 对象，在该对象中包含了三个方法用于实现对单例容器的迭代处 理。

**Iterator对象的工作原理**

![1c231ef70adc4b0b92721039c2d32407.png][]

> Iterator接口定义了如下方法：
> 
> 1 boolean hasNext(); //判断游标当前位置的下一个位置是否还有元素没有被遍历；
> 
> 2 Object next(); //返回游标当前位置的下一个元素并将游标移动到下一个位置；
> 
> 3 void remove(); //删除游标当前位置的元素，在执行完next后该操作只能执行一次；

**Iterator迭代器的使用**

**迭代List接口类型容器**

public class IteratorListTest {
        public static void main(String[] args) {
            //实例化容器
            List<String> list  = new ArrayList<>();
            list.add("a");
            list.add("b");
            list.add("c");
            //获取元素
            //获取迭代器对象
            Iterator<String> iterator = list.iterator();
            //方式一:在迭代器中，通过while循环获取元素
            while(iterator.hasNext()){
                String value = iterator.next();
                System.out.println(value);
           }
            System.out.println("-------------------------------");
            //方法二：在迭代器中，通过for循环获取元素
            for(Iterator<String> it = list.iterator();it.hasNext();){
                String value = it.next();
                System.out.println(value);
           }
       }
    }

**迭代Set接口类型容器**

public class IteratorSetTest {
        public static void main(String[] args) {
            //实例化Set类型的容器
            Set<String> set  = new HashSet<>();
            set.add("a");
            set.add("b");
            set.add("c");
            //方式一：通过while循环
            //获取迭代器对象
            Iterator<String> iterator = set.iterator();
            while(iterator.hasNext()){
                String value = iterator.next();
                System.out.println(value);
               }
            System.out.println("-------------------------");
            //方式二：通过for循环
            for(Iterator<String> it = set.iterator();it.hasNext();){
                String value = it.next();
                System.out.println(value);
           }
       }
    }

**迭代Map接口类型容器**

public class IteratorMapTest {
        public static void main(String[] args) {
            //实例化HashMap容器
            Map<String, String> map = new HashMap<String, String>();
            //添加元素
            map.put("a", "A");
            map.put("b", "B");
            map.put("c", "C");
            //遍历Map容器方式一
            Set<String> keySet = map.keySet();
            for (Iterator<String> it = keySet.iterator(); it.hasNext();){
                String key = it.next();
                String value = map.get(key);
                System.out.println(key+" ------------- "+value);
           }
            System.out.println("------------------------");
            //遍历Map容器方式二
            Set<Map.Entry<String, String>> entrySet = map.entrySet();
            Iterator<Map.Entry<String, String>> iterator = entrySet.iterator();
            while(iterator.hasNext()){
                Map.Entry entry = iterator.next();
              
             System.out.println(entry.getKey()+" ------------ "+ entry.getValue());
           }
       }
    }

**在迭代器中删除元素**

public class IteratorRemoveTest {
        public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("a");
            list.add("b");
            list.add("c");
            list.add("d");
            Iterator<String> iterator = list.iterator();
            while(iterator.hasNext()){
                //不要在一次循环中多次调用next方法。
                String value = iterator.next();
                iterator.remove();
           }
            System.out.println("----------------");
            for(Iterator<String> it = list.iterator();
               it.hasNext();){
                System.out.println(it.next());
                list.add("dddd");
           }
       }
    }

**遍历集合的方法总结**

**遍历List方法一：普通for循环**

for(int i=0;i<list.size();i++){//list为集合的对象名
     String temp = (String)list.get(i);
     System.out.println(temp);
    }

**遍历List方法二：增强for循环(使用泛型！)**

for (String temp : list) {
     System.out.println(temp);
    }

**遍历List方法三：使用Iterator迭代器(1)**

for(Iterator iter=
    list.iterator();iter.hasNext();){
     String temp = (String)iter.next();
     System.out.println(temp);
    }

**遍历List方法四：使用Iterator迭代器(2)**

Iterator  iter =list.iterator();
    while(iter.hasNext()){
     Object  obj =  iter.next();
     iter.remove();//如果要遍历时，删除集合中的元素，建议使用这种方式！
     System.out.println(obj);
    }

**遍历Set方法一：增强for循环**

for(String temp:set){
     System.out.println(temp);
    }

**遍历Set方法二：使用Iterator迭代器**

for(Iterator iter =
    set.iterator();iter.hasNext();){
     String temp = (String)iter.next();
     System.out.println(temp);
    }

**遍历Map方法一：根据key获取value**

Map<Integer, Man> maps = new HashMap<Integer,
    Man>();
    Set<Integer>  keySet =  maps.keySet();
    for(Integer id : keySet){
     System.out.println(maps.get(id).name);
    }

**遍历Map方法二：使用entrySet**

Set<Map.Entry<Integer, Man>>  ss =
    maps.entrySet();
    for (Iterator<Map.Entry<Integer, Man>>
    iterator = ss.iterator();
    iterator.hasNext();) {
     Map.Entry e =  iterator.next();
     System.out.println(e.getKey()+"--
    "+e.getValue());
    }

## Collections工具类 ##

![e1852d9363eb4820acdbfb41ae16b5e9.png][]

类 java.util.Collections 提供了对Set、List、Map进行排序、填充、 查找元素的辅助方法。

![c3c1e983912140cb844418389db2cf2b.png][]

**Collections工具类的常用方法**

public class CollectionsTest {
        public static void main(String[] args) {
            List<String> list = new ArrayList<>();
            list.add("c");
            list.add("b");
            list.add("a");
            //对元素排序
            Collections.sort(list);
            for(String str:list){
                System.out.println(str);
           }
            System.out.println("-------------------");
            List<Users> list2 = new ArrayList<>();
            Users u = new Users("oldlu",18);
            Users u2 = new Users("sxt",22);
            Users u3 = new Users("admin",22);
            list2.add(u);
            list2.add(u2);
            list2.add(u3);
            //对元素排序
            Collections.sort(list2);
            for(Users user:list2){
                System.out.println(user);
           }
            System.out.println("-------------------");
            List<Student> list3 = new ArrayList<>();
            Student s = new Student("oldlu",18);
            Student s1 = new Student("sxt",20);
            Student s2 = new Student("admin",20);
            
            list3.add(s);
            list3.add(s1);
            list3.add(s2);
            
            Collections.sort(list3,new StudentComparator());
            for(Student student:list3){
                System.out.println(student);
           }
            System.out.println("-------------------");
            List<String> list4 = new ArrayList<>();
            list4.add("a");
            list4.add("b");
            list4.add("c");
            list4.add("d");
            //洗牌
            Collections.shuffle(list4);
            for(String str:list4){
                System.out.println(str);
           }
       }
    }

[174acfb63e1e4d349ebb0149513bed12.gif]: https://img-blog.csdnimg.cn/174acfb63e1e4d349ebb0149513bed12.gif
[29ec4a888e384f76bfdf06fb7870c84a.png]: https://img-blog.csdnimg.cn/29ec4a888e384f76bfdf06fb7870c84a.png
[8084f2532477425f978b67b4cbf69208.png]: https://img-blog.csdnimg.cn/8084f2532477425f978b67b4cbf69208.png
[a16592f90b114bbabf49c6b1ad5dbddc.png]: https://img-blog.csdnimg.cn/a16592f90b114bbabf49c6b1ad5dbddc.png
[7788923995b647398df0b591f0bd0bd0.png]: https://img-blog.csdnimg.cn/7788923995b647398df0b591f0bd0bd0.png
[c03a66694dcb4b5fa4c0c42f1508f61d.png]: https://img-blog.csdnimg.cn/c03a66694dcb4b5fa4c0c42f1508f61d.png
[15a98b888069487e8b7ba20685a969fc.png]: https://img-blog.csdnimg.cn/15a98b888069487e8b7ba20685a969fc.png
[359c93b80ab440a4a734c36e56ffd947.png]: https://img-blog.csdnimg.cn/359c93b80ab440a4a734c36e56ffd947.png
[65388726e944404b99d88a4a0a64ed96.png]: https://img-blog.csdnimg.cn/65388726e944404b99d88a4a0a64ed96.png
[85990425bd67454f8ed1a8a42a9af398.png]: https://img-blog.csdnimg.cn/85990425bd67454f8ed1a8a42a9af398.png
[528c0c744398468e9d9e1e4ae385d4a3.png]: https://img-blog.csdnimg.cn/528c0c744398468e9d9e1e4ae385d4a3.png
[1c231ef70adc4b0b92721039c2d32407.png]: https://img-blog.csdnimg.cn/1c231ef70adc4b0b92721039c2d32407.png
[e1852d9363eb4820acdbfb41ae16b5e9.png]: https://img-blog.csdnimg.cn/e1852d9363eb4820acdbfb41ae16b5e9.png
[c3c1e983912140cb844418389db2cf2b.png]: https://img-blog.csdnimg.cn/c3c1e983912140cb844418389db2cf2b.png