java集合

1.基本概念_Collection_Set_List 接口介绍

1.1 为什么需要集合?

1.2 容器框架

Java集合框架提供了一套性能优良、使用方便的接口和类，
它们位于 java.util 包中
存放在集合中的数据，被称为元素(element)

1.3 各接口的特点

Collection 接口存储一组不唯一，无序的对象
List 接口存储一组不唯一，有序（索引顺序）的对象
Set 接口存储一组唯一，无序的对象

2.List 接口_ArrayList_用法详解

ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。除了实现List接口外，此类还提供一些方法来操作内部用来存储列表的数组的大小。

每个ArrayList实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造ArrayList时指定其容量。在添加大量元素前，应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量，这可以减少递增式再分配的数量。

注意，此实现不是同步的。如果多个线程同时访问一个ArrayList实例，而其中至少一个线程从结构上修改了列表，那么它必须保持外部同步。

1.ArrayList的实现：

对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。下面我们来分析ArrayList的源代码：

1) 底层使用数组实现：

private transient Object[] elementData;  

private transient Object[] elementData;

2) 构造方法：

ArrayList提供了三种方式的构造器，可以构造一个默认初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。

public ArrayList() {  

    this(10);  

}  



public ArrayList(int initialCapacity) {  

    super();  

    if (initialCapacity < 0)  

        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);  

    this.elementData = new Object[initialCapacity];  

}  



public ArrayList(Collection<? extends E> c) {  

    elementData = c.toArray();  

    size = elementData.length;  

    // c.toArray might (incorrectly) not return Object[] (see 6260652)  

    if (elementData.getClass() != Object[].class)  

        elementData = Arrays.copyOf(elementData, size, Object[].class);  

}

View Code

3) 存储：

ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)这些添加元素的方法。下面我们一一讲解：

// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。  

public E set(int index, E element) {  

    RangeCheck(index);  



    E oldValue = (E) elementData[index];  

    elementData[index] = element;  

    return oldValue;  

}  



// 用指定的元素替代此列表中指定位置上的元素，并返回以前位于该位置上的元素。  

public E set(int index, E element) {  

    RangeCheck(index);  



    E oldValue = (E) elementData[index];  

    elementData[index] = element;  

    return oldValue;  

}  



// 将指定的元素添加到此列表的尾部。  

public boolean add(E e) {  

    ensureCapacity(size + 1);   

    elementData[size++] = e;  

    return true;  

}  



// 将指定的元素添加到此列表的尾部。  

public boolean add(E e) {  

    ensureCapacity(size + 1);   

    elementData[size++] = e;  

    return true;  

}  



// 将指定的元素插入此列表中的指定位置。  

// 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。  

public void add(int index, E element) {  

    if (index > size || index < 0)  

        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  

    // 如果数组长度不足，将进行扩容。  

    ensureCapacity(size+1);  // Increments modCount!!  

    // 将 elementData中从Index位置开始、长度为size-index的元素，  

    // 拷贝到从下标为index+1位置开始的新的elementData数组中。  

    // 即将当前位于该位置的元素以及所有后续元素右移一个位置。  

    System.arraycopy(elementData, index, elementData, index + 1, size - index);  

    elementData[index] = element;  

    size++;  

}  



// 将指定的元素插入此列表中的指定位置。  

// 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。  

public void add(int index, E element) {  

    if (index > size || index < 0)  

        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  

    // 如果数组长度不足，将进行扩容。  

    ensureCapacity(size+1);  // Increments modCount!!  

    // 将 elementData中从Index位置开始、长度为size-index的元素，  

    // 拷贝到从下标为index+1位置开始的新的elementData数组中。  

    // 即将当前位于该位置的元素以及所有后续元素右移一个位置。  

    System.arraycopy(elementData, index, elementData, index + 1, size - index);  

    elementData[index] = element;  

    size++;  

}  



// 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。  

public boolean addAll(Collection<? extends E> c) {  

    Object[] a = c.toArray();  

    int numNew = a.length;  

    ensureCapacity(size + numNew);  // Increments modCount  

    System.arraycopy(a, 0, elementData, size, numNew);  

    size += numNew;  

    return numNew != 0;  

}  



// 按照指定collection的迭代器所返回的元素顺序，将该collection中的所有元素添加到此列表的尾部。  

public boolean addAll(Collection<? extends E> c) {  

    Object[] a = c.toArray();  

    int numNew = a.length;  

    ensureCapacity(size + numNew);  // Increments modCount  

    System.arraycopy(a, 0, elementData, size, numNew);  

    size += numNew;  

    return numNew != 0;  

}  



// 从指定的位置开始，将指定collection中的所有元素插入到此列表中。  

public boolean addAll(int index, Collection<? extends E> c) {  

    if (index > size || index < 0)  

        throw new IndexOutOfBoundsException(  

            "Index: " + index + ", Size: " + size);  



    Object[] a = c.toArray();  

    int numNew = a.length;  

    ensureCapacity(size + numNew);  // Increments modCount  



    int numMoved = size - index;  

    if (numMoved > 0)  

        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);  



    System.arraycopy(a, 0, elementData, index, numNew);  

    size += numNew;  

    return numNew != 0;  

}  



// 从指定的位置开始，将指定collection中的所有元素插入到此列表中。  

public boolean addAll(int index, Collection<? extends E> c) {  

    if (index > size || index < 0)  

        throw new IndexOutOfBoundsException(  

            "Index: " + index + ", Size: " + size);  



    Object[] a = c.toArray();  

    int numNew = a.length;  

    ensureCapacity(size + numNew);  // Increments modCount  



    int numMoved = size - index;  

    if (numMoved > 0)  

        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);  



    System.arraycopy(a, 0, elementData, index, numNew);  

    size += numNew;  

    return numNew != 0;  

}

View Code

4) 读取：

// 返回此列表中指定位置上的元素。  

public E get(int index) {  

    RangeCheck(index);  



    return (E) elementData[index];  

}  

[java] view plaincopy

// 返回此列表中指定位置上的元素。  

public E get(int index) {  

    RangeCheck(index);  



    return (E) elementData[index];  

}

View Code

5) 删除：

ArrayList提供了根据下标或者指定对象两种方式的删除功能。如下：

// 移除此列表中指定位置上的元素。  

public E remove(int index) {  

    RangeCheck(index);  



    modCount++;  

    E oldValue = (E) elementData[index];  



    int numMoved = size - index - 1;  

    if (numMoved > 0)  

        System.arraycopy(elementData, index+1, elementData, index, numMoved);  

    elementData[--size] = null; // Let gc do its work  



    return oldValue;  

}  



// 移除此列表中指定位置上的元素。  

public E remove(int index) {  

    RangeCheck(index);  



    modCount++;  

    E oldValue = (E) elementData[index];  



    int numMoved = size - index - 1;  

    if (numMoved > 0)  

        System.arraycopy(elementData, index+1, elementData, index, numMoved);  

    elementData[--size] = null; // Let gc do its work  



    return oldValue;  

}  



// 移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。  

public boolean remove(Object o) {  

    // 由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。  

    if (o == null) {  

        for (int index = 0; index < size; index++)  

            if (elementData[index] == null) {  

                // 类似remove(int index)，移除列表中指定位置上的元素。  

                fastRemove(index);  

                return true;  

            }  

} else {  

    for (int index = 0; index < size; index++)  

        if (o.equals(elementData[index])) {  

            fastRemove(index);  

            return true;  

        }  

    }  

    return false;  

}  



// 移除此列表中首次出现的指定元素（如果存在）。这是应为ArrayList中允许存放重复的元素。  

public boolean remove(Object o) {  

    // 由于ArrayList中允许存放null，因此下面通过两种情况来分别处理。  

    if (o == null) {  

        for (int index = 0; index < size; index++)  

            if (elementData[index] == null) {  

                // 类似remove(int index)，移除列表中指定位置上的元素。  

                fastRemove(index);  

                return true;  

            }  

} else {  

    for (int index = 0; index < size; index++)  

        if (o.equals(elementData[index])) {  

            fastRemove(index);  

            return true;  

        }  

    }  

    return false;  

}

View Code

注意：从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向左移动一个位置。

6) 调整数组容量：

从上面介绍的向ArrayList中存储元素的代码中，我们看到，每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。数组扩容通过一个公开的方法ensureCapacity(int minCapacity)来实现。在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

public void ensureCapacity(int minCapacity) {  

    modCount++;  

    int oldCapacity = elementData.length;  

    if (minCapacity > oldCapacity) {  

        Object oldData[] = elementData;  

        int newCapacity = (oldCapacity * 3)/2 + 1;  

            if (newCapacity < minCapacity)  

                newCapacity = minCapacity;  

      // minCapacity is usually close to size, so this is a win:  

      elementData = Arrays.copyOf(elementData, newCapacity);  

    }  

}  



public void ensureCapacity(int minCapacity) {  

    modCount++;  

    int oldCapacity = elementData.length;  

    if (minCapacity > oldCapacity) {  

        Object oldData[] = elementData;  

        int newCapacity = (oldCapacity * 3)/2 + 1;  

            if (newCapacity < minCapacity)  

                newCapacity = minCapacity;  

      // minCapacity is usually close to size, so this is a win:  

      elementData = Arrays.copyOf(elementData, newCapacity);  

    }  

}

View Code

从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下：

public void trimToSize() {  

    modCount++;  

    int oldCapacity = elementData.length;  

    if (size < oldCapacity) {  

        elementData = Arrays.copyOf(elementData, size);  

    }  

}  



public void trimToSize() {  

    modCount++;  

    int oldCapacity = elementData.length;  

    if (size < oldCapacity) {  

        elementData = Arrays.copyOf(elementData, size);  

    }  

}

View Code

7) Fail-Fast机制：

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。具体介绍请参考我之前的文章深入Java集合学习系列：HashMap的实现原理中的Fail-Fast机制。

8) 关于其他的一些方法的实现都很简单易懂，读者可参照API文档和源代码，一看便知，这里就不再多说。

2.1ArrayList 的用法

package Collection;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;

public class TestArrayList {
public static void main(String[] args) {
    //创建集合对象，接口new实现类
    List list =new ArrayList();
    //（1）add
    list.add("hello");
    list.add(123);
    list.add(new Scanner(System.in));
    //(2)集合中元素的个数size()
    System.out.println(list.size());
    System.out.println("集合是否为空:"+list.isEmpty());
    //(3)addAll(Collection c)
    List list2=new ArrayList();
    list2.add("hello");
    list2.add(123);
    list.addAll(list2);
    System.out.println("list集合中的元素个数"+list.size());
    System.out.println(list);
    //(4)删除
    System.out.println("根据对象取删除");
    list.remove("hello");
    System.out.println(list);
    //list.remove(123);//认为是索引
    list.remove(new Integer(123));
    System.out.println(list);
    list.remove(0);
    System.out.println(list);
    list.add("world");
    //list.removeAll(list2);
    //list.retainAll(list2);
    System.out.println("list"+list);
    System.out.println("list2"+list2);
    
    
    //判断指定对象在集合中是否存在
    System.out.println("hello在指定集合中是否存在:"+list.contains("hello"));
    System.out.println("java在指定集合中是否存在:"+list.contains("java"));
    System.out.println(list.containsAll(list2));
    
    //list.clear();
    //System.out.println(list);
    //(7)获取指定索引位置上的元素对象
    System.out.println(list.get(1));
    //(8)设置
    list.set(1, "java");
    System.out.println(list);
    //(9)在指定的索引位置上添加元素对象
    list.add(1,"html");
    
    //(10)查找元素在集合中的位置
    System.out.println(list.indexOf("java")+"	"+list.indexOf("sql"));
    //(11)遍历集合中的元素内容
    /**
     * (1)使用增强for循环遍历集合中的元素
     */
    for(Object obj:list){
        System.out.println(obj);
    }
    /**
     * (2)使用普通for循环遍历集合中的元素对象
     */
    System.out.println("使用普通for循环遍历集合中元素对象
");
    for(int i=0;i<list.size();i++){
        System.out.println(list.get(i));
    }
    /**
     * (3)使用迭代器
     */
    System.out.println("
使用得迭代器遍历集合中的元素");
    Iterator ite = list.iterator();//正向遍历
    while(ite.hasNext()){//判断集合中是否有对象
        Object obj=ite.next();
        System.out.println(obj);
    }
    System.out.println("使用listIterator（）遍历");
    ListIterator listIte=list.listIterator();
    System.out.println("正向遍历");
    System.out.println("到达集合的开头，后面还有元素对象嘛？"+listIte.hasNext());
    System.out.println("到达集合的开头，前面还有元素对象嘛？"+listIte.hasPrevious());
    while(listIte.hasNext()){
        System.out.println(listIte.next());
    }
    System.out.println("到达集合的末尾，后面还有元素对象嘛？"+listIte.hasNext());
    System.out.println("到达集合末尾，前面还有元素对象嘛？"+listIte.hasPrevious());
    
    System.out.print("
逆向遍历集合中的元素

");
    while(listIte.hasPrevious()){
        System.out.println(listIte.previous());
    }
}
}

View Code

源码分析一arraylist

package com.bjsxt.arraylist;

import java.util.ArrayList;
import java.util.Arrays;


public class TestArrayList {
    /**ArrayList源码分析
     * (1)无参构造方法
     *       this.elementData 是一个Object类型的数组
     *       DEFAULTCAPACITY_EMPTY_ELEMENTDATA;也是一个Object类型的数组
     *       DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};默认长度为0
     *     public ArrayList() {
               this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
               //相当于this.elementData={};
          }
        (2)带参构造方法
            
         public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
                //this.elementData=new Object[20];
            } 
        }
        (3)添加方法 add(Object obj)
         public boolean add(E e) {
                //检测空间容量是否够用
                ensureCapacityInternal(size + 1);  // Increments modCount!!
                //添加元素    elementData[size]=e; size++;
                elementData[size++] = e;
                return true;
        }
        (4)检测空间容量是否够用
        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
        首先调用执行 ,计算容量
         calculateCapacity(elementData, minCapacity)
         
         //calculateCapacity方法定义
         private static int calculateCapacity(Object[] elementData, int minCapacity) {
                    //以下代码相当于elementData=={}
                if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  //true
                           //Math.max(10,1);
                    return Math.max(DEFAULT_CAPACITY, minCapacity);
                }
        return minCapacity;  //执行完之后的结果为  10
       }
        //容量计算完毕后，执行ensureExplicitCapacity方法    ensureExplicitCapacity(10)
         ensureExplicitCapacity方法定义
         
         private void ensureExplicitCapacity(int minCapacity) {  //10
            modCount++;
    
            // overflow-conscious code
             * 10-0 >0  true
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        (5)扩充容量
          private void grow(int minCapacity) {    //10
            // overflow-conscious code
            int oldCapacity = elementData.length;        //int oldCapactiy=0;
            
            int newCapacity = oldCapacity + (oldCapacity >> 1);   //int newCapacity=0+0>>1  结果为0
          
            if (newCapacity - minCapacity < 0)       // 0-10<0    true
            
                newCapacity = minCapacity;           //newCapacity=10;
                
          
            elementData = Arrays.copyOf(elementData, newCapacity); //数组拷贝 elementData的长度就是 10
    }
     * */
       
    public static void main(String[] args) {
        ArrayList list=new ArrayList();
        //第一次调用添加方法时，完成Object类型数组的初始化容量 ，10
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");
        list.add("hello");
        list.add("world");//10个元素对象
        /**当添加第11个元素时，所需容量为11，而数组的长度为10，已经无法容纳元素了，这个时候需要扩容，
         * 原始容量+原始容量>>1   得到新容量
         * 10+10>>1           15*/
        
        list.add("hello");//当添加第11个元素对象时 怎么办？
        
        Object [] obj={};
        
        
    }
}

View Code

5.LinkedList 的特点_链表_JDK 源码分析

5.1LinkedList 的特点

5.2 链表

单向链表

（1）一个节点

（2）多个节点组成单向链表

双向链表

（1）一个节点

（2）多个节点组成链表

5.3JDK 源码分析

1. add(Object obj)
2. addFirst()
3. removeFirst()
4. removeLast();

package Collection;
import java.util.LinkedList;

public class TestLinkedList {
    /**
     * LinkedList底层数据结构是链表,删除和添加元素的效率比较高，数据结构复杂
     * ArrayList底层数据结构是数组， 删除和添加元素效率比较低
     * LinkedList底层源码分析
     * (1)构造方法
     * public LinkedList() {
       }
       (2)添加方法
      public boolean add(E e) {
        linkLast(e);
        return true;
    }
      
     * */
    public static void main(String[] args) {
        LinkedList list=new LinkedList();
        //添加元素
        list.add("hello");
        list.addFirst("java");
        list.addLast("world");
        //删头，删尾
        //list.removeLast();
        //list.removeFirst();
        System.out.println(list);
        //遍历
        for(Object obj:list){
            System.out.println(obj);
        }
        }
        
    
}

View Code

6.Vector 用法和 ArrayList 区别_JDK 源码分析

6.1Vector 的用法

6.2Vector_JDK 源码分析

6.3Vector 与 ArrayList 的区别

底层数据结构相同，都是 Object 类型的数组

(1) Vector 的 add()方法是同步方法,ArrayList 的 add()方法是非同步方法

(2) Vector 扩容每次扩充 1 倍 ,ArrayList 每次扩充 0.5倍

(3) Vector是在调用构造方法时，直接初始化容量为10，ArrayList 是在第一次调用添加方法时，初始化容量为 10

(4) Vector 的版本是 JDK1.0,ArrayList，JDK1.2 版
(5) Vector 是线程同步的，安全性高，效率低，ArrayList 是线程非同步的，安全性低，效率高

package Collection;

import java.util.Iterator;
import java.util.Vector;

public class TestVector {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //创建集合对象
   Vector vector=new Vector();
   //添加
   vector.add("hello");
   vector.add(0,"world");
   vector.addElement("java");
   System.out.println("集合中的元素个数"+vector.size());
   System.out.println(vector);
   //删除
   //vector.remove(1);
  // vector.remove("java");
  // vector.clear();
   System.out.println(vector);
   //获取元素的方法
   System.out.println(vector.get(1));
   System.out.println(vector);

   System.out.println("加强for循环");
   for(Object obj:vector){
       System.out.println(obj);
   }
   System.out.println("使用迭代器遍历集合");
   for(Iterator ite=vector.iterator();ite.hasNext();){
       System.out.println(ite.next());
   }
       Iterator ite=vector.iterator();
       while(ite.hasNext()){
           System.out.println(ite.next());
       }
    }

}

View Code

7.Map 接口_HashMap_Hashtable 的用法详解

HashMap概述：

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构：

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

源码如下：

/**   
 * The table, resized as necessary. Length MUST Always be a power of two.    
 */     

transient Entry[] table;  



static class Entry<K,V> implements Map.Entry<K,V> {  

    final K key;  

    V value;  

    Entry<K,V> next;  

    final int hash;  

    ……  

}  

[java] view plaincopy

/**   
 * The table, resized as necessary. Length MUST Always be a power of two.   
 */    

transient Entry[] table;  



static class Entry<K,V> implements Map.Entry<K,V> {  

    final K key;  

    V value;  

    Entry<K,V> next;  

    final int hash;  

    ……  

}

View Code

可以看出，Entry就是数组中的元素，每个 Map.Entry 其实就是一个key-value对，它持有一个指向下一个元素的引用，这就构成了链表。

HashMap的存取实现：

1) 存储：

public V put(K key, V value) {  

    // HashMap允许存放null键和null值。  

    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  

    if (key == null)  

        return putForNullKey(value);  

    // 根据key的keyCode重新计算hash值。  

    int hash = hash(key.hashCode());  

    // 搜索指定hash值在对应table中的索引。  

    int i = indexFor(hash, table.length);  

    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  

        Object k;  

        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

            V oldValue = e.value;  

            e.value = value;  

            e.recordAccess(this);  

            return oldValue;  

        }  

    }  

    // 如果i索引处的Entry为null，表明此处还没有Entry。  

    modCount++;  

    // 将key、value添加到i索引处。  

    addEntry(hash, key, value, i);  

    return null;  

}  



public V put(K key, V value) {  

    // HashMap允许存放null键和null值。  

    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  

    if (key == null)  

        return putForNullKey(value);  

    // 根据key的keyCode重新计算hash值。  

    int hash = hash(key.hashCode());  

    // 搜索指定hash值在对应table中的索引。  

    int i = indexFor(hash, table.length);  

    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  

    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  

        Object k;  

        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

            V oldValue = e.value;  

            e.value = value;  

            e.recordAccess(this);  

            return oldValue;  

        }  

    }  

    // 如果i索引处的Entry为null，表明此处还没有Entry。  

    modCount++;  

    // 将key、value添加到i索引处。  

    addEntry(hash, key, value, i);  

    return null;  

}

View Code

从上面的源代码中可以看出：当我们往HashMap中put元素的时候，先根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置（即下标），如果数组该位置上已经存放有其他元素了，那么在这个位置上的元素将以链表的形式存放，新加入的放在链头，最先加入的放在链尾。如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上。

addEntry(hash, key, value, i)方法根据计算出的hash值，将key-value对放在数组table的i索引处。addEntry 是 HashMap 提供的一个包访问权限的方法，代码如下：

void addEntry(int hash, K key, V value, int bucketIndex) {  

    // 获取指定 bucketIndex 索引处的 Entry   

    Entry<K,V> e = table[bucketIndex];  

    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  

    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  

    // 如果 Map 中的 key-value 对的数量超过了极限  

    if (size++ >= threshold)  

    // 把 table 对象的长度扩充到原来的2倍。  

        resize(2 * table.length);  

}  



void addEntry(int hash, K key, V value, int bucketIndex) {  

    // 获取指定 bucketIndex 索引处的 Entry   

    Entry<K,V> e = table[bucketIndex];  

    // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry  

    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  

    // 如果 Map 中的 key-value 对的数量超过了极限  

    if (size++ >= threshold)  

    // 把 table 对象的长度扩充到原来的2倍。  

        resize(2 * table.length);  

}

View Code

当系统决定存储HashMap中的key-value对时，完全没有考虑Entry中的value，仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。

hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。

static int hash(int h) {  

    h ^= (h >>> 20) ^ (h >>> 12);  

    return h ^ (h >>> 7) ^ (h >>> 4);  

}  

[java] view plaincopy

static int hash(int h) {  

    h ^= (h >>> 20) ^ (h >>> 12);  

    return h ^ (h >>> 7) ^ (h >>> 4);  

}

View Code

我们可以看到在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量的分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，而不用再去遍历链表，这样就大大优化了查询的效率。

对于任意给定的对象，只要它的 hashCode() 返回值相同，那么程序调用 hash(int h) 方法所计算得到的 hash 码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中是这样做的：调用 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。indexFor(int h, int length) 方法的代码如下：

static int indexFor(int h, int length) {  

    return h & (length-1);  

}  

[java] view plaincopy

static int indexFor(int h, int length) {  

    return h & (length-1);  

}

View Code

这个方法非常巧妙，它通过 h & (table.length -1) 来得到该对象的保存位，而HashMap底层数组的长度总是 2 的 n 次方，这是HashMap在速度上的优化。在 HashMap 构造器中有如下代码：

int capacity = 1;  

    while (capacity < initialCapacity)  

        capacity <<= 1;  



int capacity = 1;  

    while (capacity < initialCapacity)  

        capacity <<= 1;

View Code

这段代码保证初始化时HashMap的容量总是2的n次方，即底层数组的长度总是为2的n次方。

当length总是 2 的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

这看上去很简单，其实比较有玄机的，我们举个例子来说明：

假设数组长度分别为15和16，优化后的hash码分别为8和9，那么&运算后的结果如下：

从上面的例子中可以看出：当它们和15-1（1110）“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8和9会被放到数组中的同一个位置上形成链表，那么查询的时候就需要遍历这个链表，得到8或者9，这样就降低了查询的效率。同时，我们也可以发现，当数组长度为15的时候，hash值会与15-1（1110）进行“与”，那么最后一位永远是0，而0001，0011，0101，1001，1011，0111，1101这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！而当数组长度为16时，即为2的n次方时，2n-1得到的二进制数的每个位上的值都为1，这使得在低位上&时，得到的和原hash的低位相同，加之hash(int h)方法对key的hashCode的进一步优化，加入了高位计算，就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表。

所以说，当数组长度为2的n次幂的时候，不同的key算得得index相同的几率较小，那么数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

根据上面 put 方法的源代码可以看出，当程序试图将一个key-value对放入HashMap中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但key不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部——具体说明继续看 addEntry() 方法的说明。

2) 读取：

public V get(Object key) {  

    if (key == null)  

        return getForNullKey();  

    int hash = hash(key.hashCode());  

    for (Entry<K,V> e = table[indexFor(hash, table.length)];  

        e != null;  

        e = e.next) {  

        Object k;  

        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  

            return e.value;  

    }  

    return null;  

}  



public V get(Object key) {  

    if (key == null)  

        return getForNullKey();  

    int hash = hash(key.hashCode());  

    for (Entry<K,V> e = table[indexFor(hash, table.length)];  

        e != null;  

        e = e.next) {  

        Object k;  

        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  

            return e.value;  

    }  

    return null;  

}

View Code

有了上面存储时的hash算法作为基础，理解起来这段代码就很容易了。从上面的源代码中可以看出：从HashMap中get元素时，首先计算key的hashCode，找到数组中对应位置的某一元素，然后通过key的equals方法在对应位置的链表中找到需要的元素。

3) 归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry。

HashMap的resize（rehash）：

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。

那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

HashMap的性能参数：

HashMap 包含如下几个构造器：

HashMap()：构建一个初始容量为 16，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity)：构建一个初始容量为 initialCapacity，负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数，它们是初始容量initialCapacity和加载因子loadFactor。

initialCapacity：HashMap的最大容量，即为底层数组的长度。

loadFactor：负载因子loadFactor定义为：散列表的实际元素数目(n)/ 散列表的容量(m)。

View Code

负载因子衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。

HashMap的实现中，通过threshold字段来判断HashMap的最大容量：


threshold = (int)(capacity * loadFactor);  



threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知，threshold就是在此loadFactor和capacity对应下允许的最大元素数目，超过这个数目就重新resize，以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时， resize后的HashMap容量是容量的两倍：


if (size++ >= threshold)     

    resize(2 * table.length);    



if (size++ >= threshold)     

    resize(2 * table.length);

Fail-Fast机制：

我们知道java.util.HashMap不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

HashIterator() {  

    expectedModCount = modCount;  

    if (size > 0) { // advance to first entry  

    Entry[] t = table;  

    while (index < t.length && (next = t[index++]) == null)  

        ;  

    }  

}  



HashIterator() {  

    expectedModCount = modCount;  

    if (size > 0) { // advance to first entry  

    Entry[] t = table;  

    while (index < t.length && (next = t[index++]) == null)  

        ;  

    }  

}

View Code

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：

注意到modCount声明为volatile，保证线程之间修改的可见性。

final Entry<K,V> nextEntry() {     

    if (modCount != expectedModCount)     

        throw new ConcurrentModificationException();  



final Entry<K,V> nextEntry() {     

    if (modCount != expectedModCount)     

        throw new ConcurrentModificationException();

View Code

在HashMap的API中指出：

由所有HashMap类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的 remove 方法，其他任何时间任何方式的修改，迭代器都将抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测程序错误。

7.1Map 接口

1. 实现 Map 接口的类用来存储键(key) -值(value)对
2. Map 接口的实现类有 HashMap 和 TreeMap 等
3. Map 类中存储的键-值对通过键来标识，所以键值不能重复

7.2HashMap 的使用

key唯一，value无序。

7.3HashMap 与 Hashtable 的区别

HashMap与Hashtable的区别

(1)版本不同 HashMap JDK1.2 Hashtable 1.0
(2)HashMap继承了AbstractMap，实现了Map接口，Hashtable继承了Dictionary实现Map接口
(3)HashMap允许null值和null键, 但是null作为key只允一个, Hashtable非null的键和值
(4)HashMap是线程不同步的 (效率高，安全性低),Hashtable(效率低，安全性高)线程同步

package com.bjsxt.hashmap;

import java.util.Collection;
import java.util.HashMap;
import java.util.Set;

public class TestHashMap {
    public static void main(String[] args) {
        //Map接口的特点,key不允许重复，值可以重复，而且key是无序的
        //创建集合对象
        HashMap hm=new HashMap();
        //(1)添加元素
        hm.put("hello", 123);//123自动装箱，Integer类型
        hm.put("world",456);
        hm.put("hello", 1000); //集合中的key不能重复，如果重复，将进行值的覆盖
        hm.put("java", 1000);
        System.out.println("集合中元素的个数:"+hm.size());
        System.out.println("集合是否为空:"+hm.isEmpty());
        System.out.println(hm);
        System.out.println(hm.remove("world"));//先输出后移除
        System.out.println(hm);
        //判断
        System.out.println(hm.containsKey("java")+"	"+hm.containsKey("world"));
        System.out.println(hm.containsValue(1000)+"	"+hm.containsValue(2000));
        //获取元素
        System.out.println(hm.get("java")+"	"+hm.get("world"));
        //获取所有key的集合
        Set set=hm.keySet();
        for(Object obj:set){
            System.out.println(obj);
        }
        //获取所有的value的集合
        System.out.println("
--------------------------");
        Collection coll=hm.values();
        for(Object obj:coll){
            System.out.println(obj);
        }
        //获取所有key-value关系的集合
        Set entrySet=hm.entrySet();
        for(Object obj:entrySet){
            System.out.println(obj);
        }
        
        /**
         * HashMap与Hashtable的区别
         * (1)版本不同 HashMap JDK1.2  Hashtable 1.0
         * (2)HashMap继承了AbstractMap，实现了Map接口，Hashtable继承了Dictionary实现Map接口
         * (3)HashMap允许null值和null键, 但是null作为key只允一个, Hashtable非null的键和值
         * (4)HashMap是线程不同步的 (效率高，安全性低),Hashtable(效率低，安全性高)线程同步
         * 
         * 
         * */
    }
}

View Code

package com.bjsxt.hashmap;

import java.util.HashMap;
import java.util.Hashtable;

public class TestHashtable {
    public static void main(String[] args) {
        //创建集合对象
        Hashtable ht=new Hashtable();
        //ht.put(null, null);
        System.out.println(ht);//NullPointerException
        HashMap hm=new HashMap();
        hm.put(null, null);
        hm.put(null, "hello");
        System.out.println(hm);
    }
}

View Code

8.HashMap 底层实现

1.哈希表的结构和特点

hashtable 也叫散列表
特点：快很快神奇的快
结构：结构有多种
最流行、最容易理解：顺序表+链表
主结构：顺序表
每个顺序表的节点在单独引出一个链表

2.哈希表是如何添加数据的

1.计算哈希码(调用 hashCode(),结果是一个 int 值，整数的哈希码取自身即可)

2.计算在哈希表中的存储位置 y=k(x)=x%11 x:哈希码 k(x) 函数 y：在哈希表中的存储位置

3.如何减少冲突因此，一般情况下，装填因子取经验值 0.5

4.哈希函数的选择

直接定址法平方取中法折叠法除留取余法（y
= x%11）查询相关资料
JDK1.8 开始，当链表的个数>=8 时，就会将链表转为红黑树，
目的是为了减少查询比较的次数。

LinkedHashMap概述：
LinkedHashMap是Map接口的哈希表和链接列表实现，具有可预知的迭代顺序。此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。

注意，此实现不是同步的。如果多个线程同时访问链接的哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

LinkedHashMap的实现：
对于LinkedHashMap而言，它继承与HashMap、底层使用哈希表与双向链表来保存所有元素。其基本操作与父类HashMap相似，它通过重写父类相关的方法，来实现自己的链接列表特性。下面我们来分析LinkedHashMap

1) Entry元素：

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定义了数组中保存的元素Entry，该Entry除了保存当前对象的引用外，还保存了其上一个元素before和下一个元素after的引用，从而在哈希表的基础上又构成了双向链接列表。看源代码：

/**   
 * 双向链表的表头元素。   
 */  
private transient Entry header;  

/**   
 * LinkedHashMap的Entry元素。    
 * 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。   
 */    

private static class Entry extends HashMap.Entry {  

    Entry before, after;  

    ……  

}  



/** 
 * 双向链表的表头元素。 
 */  
private transient Entry header;  

/**    
 * LinkedHashMap的Entry元素。    
 * 继承HashMap的Entry元素，又保存了其上一个元素before和下一个元素after的引用。    
 */    

private static class Entry extends HashMap.Entry {  

    Entry before, after;  

    ……  

}

View Code

2) 初始化：

通过源代码可以看出，在LinkedHashMap的构造方法中，实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组。如：

public LinkedHashMap(int initialCapacity, float loadFactor) {  

    super(initialCapacity, loadFactor);  

    accessOrder = false;  

}  


public LinkedHashMap(int initialCapacity, float loadFactor) {  

    super(initialCapacity, loadFactor);  

    accessOrder = false;  

}
 HashMap中的相关构造方法：


public HashMap(int initialCapacity, float loadFactor) {  

    if (initialCapacity < 0)  

        throw new IllegalArgumentException("Illegal initial capacity: " +  

                                           initialCapacity);  

    if (initialCapacity > MAXIMUM_CAPACITY)  

        initialCapacity = MAXIMUM_CAPACITY;  

    if (loadFactor <= 0 || Float.isNaN(loadFactor))  
        throw new IllegalArgumentException("Illegal load factor: " +  

                                           loadFactor);

View Code

9.二叉树和红黑树

9.1 树

1) 树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。

2) 父子关系在树的结点之间建立了一个层次结构。
3) 树的结点包含一个数据元素及若干指向其子树的若干分支。

4) 在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。

例如图（a）是一棵空树、（b）是只有一个根节点的树、（c）是一棵有 10 个结点的树，其中 A 是根，

9.2 二叉树

每个结点的度均不超过 2 的有序树，称为二叉树（binary tree）

由以上定义可以看出

1) 二叉树中每个结点的孩子数只能是 0、1 或 2 个，并且每个孩子都有左右之分。
2) 位于左边的孩子称为左孩子，位于右边的孩子称为右孩子；
3) 以左孩子为根的子树称为左子树，以右孩子为根的子树称为右子树。

9.3 二叉查找/搜索/排序树 BST (binary search/sort tree)

或者是一棵空树；
或者是具有下列性质的二叉树：

（1）若它的左子树不空，则左子树上所有结点的值均小于它的根节点的值；

（2）若它的右子树上所有结点的值均大于它的根节点的值；
（3）它的左、右子树也分别为二叉排序树。

9.4 平衡二叉树（Self-balancing binary search tree）

自平衡二叉查找树又被称为 AVL 树（有别于 AVL 算法）它是一棵空树或它的左右两个子树的高度差( 平衡因子 )的绝对值不超过1

平衡二叉树：每个结点的平衡因子都为 1、－1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差 1 的二叉排序树。

平衡二叉树的目的是为了减少二叉查找树层次，提高查找速度

9.5 红黑树

R-B Tree，全称是 Red-Black Tree，又称为"红黑树"，它一种平衡二叉树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL 或 NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：

(01) 特性(3)中的叶子节点，是只为空(NIL 或 null)的节点。
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树

10.TreeMap 的使用和底层实现

10.1TreeMap 的使用

Key:唯一，有序，升序
底层数据结构:红黑树

10.2TreeMap 的底层实现

如果使用 TreeMap 存储自定义对象做为 key 时，要求必须具备比较规则，否则运行报错

package com.bjsxt.treemap;

import java.util.Comparator;

public class CompareCharactor implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        Person p1=(Person)o1;
        Person p2=(Person)o2;
                     //调用了String类中按照英文字母升序比较大小的方法
        return p1.getName().compareTo(p2.getName());
    }
    
}

View Code

package com.bjsxt.treemap;

import java.util.Comparator;
//编写一个外部比较器的实现类，用于实现根据英文字母的个数进行升序比较
public class CompareLength implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        //向下类型转换
        String s1=(String)o1;
        String s2=(String)o2;
        return s1.length()-s2.length();
    }

}

View Code

package com.bjsxt.treemap;

public class Person implements Comparable {
    private String name;
    private int 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;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    @Override
    public int compareTo(Object o) {
        // TODO Auto-generated method stub
        Person p=(Person)o;
        return this.age-p.getAge();
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]";
    }
    
}

View Code

package com.bjsxt.treemap;

import java.util.Comparator;
import java.util.TreeMap;


public class TestTreeMap {
    /***
     * TreeMap的底层实现
     * 
     *  private final Comparator<? super K> comparator;  外部比较器，用于比较大小的
     *  private transient Entry<K,V> root;   //代表的是树根
     * public TreeMap() {
        comparator = null;
       }
       public V put(K key, V value) {
        Entry<K,V> t = root;   //指向树根
        if (t == null) {
              //比较大小
            compare(key, key); // type (and possibly null) check
            //创建一个根节点
            root = new Entry<>(key, value, null);
            
            size = 1;   //个数++
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;   //父节点
        // split comparator and comparable paths
         * 
        Comparator<? super K> cpr = comparator;   //null
         //如果外部比较器不等于null,说明外部比较器存在
        if (cpr != null) {
            do {
                parent = t;   //把root赋给父节点
                
                cmp = cpr.compare(key, t.key);  //调用外部比较器的比较方法开始比大小,结果是一个int类型的值
                
                if (cmp < 0)
                    t = t.left;   //在左子树上查找
                else if (cmp > 0)   //在右子树上查找
                    t = t.right;
                else
                    return t.setValue(value);   //找到了，值进行覆盖
            } while (t != null);
        }
        else {  //外部比较器不存在，使用内部比较器进行比较
            if (key == null)
                throw new NullPointerException();
            @SuppressWarnings("unchecked")
                Comparable<? super K> k = (Comparable<? super K>) key;
            do {
                parent = t;    //root赋给父节点
                cmp = k.compareTo(t.key);  //调用内部比较器的比较大小的方法，比较结果为int类型
                if (cmp < 0)   
                    t = t.left;     //在左子树上查找
                else if (cmp > 0)   //在右子树上查找
                    t = t.right;
                else
                    return t.setValue(value);   找到了值的覆盖
            } while (t != null);
        }
         //创建一个节点
        Entry<K,V> e = new Entry<>(key, value, parent);
        
        if (cmp < 0)
            parent.left = e;   //添加到左子树
        else
            parent.right = e;    //添加到右子树
        fixAfterInsertion(e);
        size++;      
        modCount++;
        return null;
    }
     */
    public static void main(String[] args) {
        //创建集合对象
        //TreeMap treeMap=new TreeMap();
        //创建外部比较器对象,定义比较规则
        Comparator comLength=new CompareLength();
        TreeMap treeMap=new TreeMap(comLength);
        //添加数据
        treeMap.put("hello", 123);
        treeMap.put("world1", 456);
        treeMap.put("hello11", 789);
        treeMap.put("java", 1000);
        System.out.println("集合中元素的个数:"+treeMap.size());
        System.out.println(treeMap);
        System.out.println(treeMap.containsKey("hello")+"	"+treeMap.containsKey("sql"));
        System.out.println(treeMap.containsValue(789)+"	"+treeMap.containsValue(1002));
        System.out.println(treeMap.get("java"));
        
        
    }
}

View Code

package com.bjsxt.treemap;

import java.util.Comparator;
import java.util.TreeMap;

public class TreeMapTest {
    public static void main(String[] args) {
        //创建TreeMap集合对象
        //TreeMap tm=new TreeMap();//使用内部比较器
        /**key希望按照英文字母的升序排序*/
        CompareCharactor cc=new CompareCharactor();
        TreeMap tm=new TreeMap(cc);
        Person p1=new Person("marry",20);
        Person p2=new Person("lili",19);
        Person p3=new Person("small-apple",23);
        tm.put(p1, p1.getName());
        tm.put(p2, p2.getName());
        tm.put(p3, p3.getName());
        System.out.println(tm);
    }
}

View Code

11.Set 接口_HashSet 的用法

11.1Set 接口

Set 接口：唯一，无序

11.2HashSet 的用法

HashSet概述：

HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set的迭代顺序；特别是它不保证该顺序恒久不变。此类允许使用null元素。

HashSet的实现：

对于HashSet而言，它是基于HashMap实现的，HashSet底层使用HashMap来保存所有元素，因此HashSet的实现比较简单，相关HashSet的操作，基本上都是直接调用底层HashMap的相关方法来完成， HashSet的源代码如下：

public class HashSet<E>  

    extends AbstractSet<E>  

    implements Set<E>, Cloneable, java.io.Serializable  

{  

    static final long serialVersionUID = -5024744406713321676L;  



    // 底层使用HashMap来保存HashSet中所有元素。  
    private transient HashMap<E,Object> map;  



    // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。  
    private static final Object PRESENT = new Object();  



    /**     
     * 默认的无参构造器，构造一个空的HashSet。    
     *     
     * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。     
     */     

    public HashSet() {  

    map = new HashMap<E,Object>();  

    }  



    /**   
     * 构造一个包含指定collection中的元素的新set。   
     *    
     * 实际底层使用默认的加载因子0.75和足以包含指定    
     * collection中所有元素的初始容量来创建一个HashMap。    
     * @param c 其中的元素将存放在此set中的collection。   
     */     

    public HashSet(Collection<? extends E> c) {  

    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));  

    addAll(c);  

    }  


    /**    
     * 以指定的initialCapacity和loadFactor构造一个空的HashSet。    
     *    
     * 实际底层以相应的参数构造一个空的HashMap。    
     * @param initialCapacity 初始容量。    
     * @param loadFactor 加载因子。    
     */    

    public HashSet(int initialCapacity, float loadFactor) {  

    map = new HashMap<E,Object>(initialCapacity, loadFactor);  

    }    

    /**    
     * 以指定的initialCapacity构造一个空的HashSet。    
     *    
     * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。    
     * @param initialCapacity 初始容量。     
     */     

    public HashSet(int initialCapacity) {  

    map = new HashMap<E,Object>(initialCapacity);  

    }  


    /**    
     * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。     
     * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。   
     *     
     * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。    
     * @param initialCapacity 初始容量。     
     * @param loadFactor 加载因子。     
     * @param dummy 标记。   
     */     

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {  

    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);  

    }  


    /**    
     * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。     
     *      
     * 底层实际调用底层HashMap的keySet来返回所有的key。    
     * 可见HashSet中的元素，只是存放在了底层HashMap的key上，    
     * value使用一个static final的Object对象标识。   
     * @return 对此set中元素进行迭代的Iterator。   
     */     

    public Iterator<E> iterator() {  

    return map.keySet().iterator();  

    }  

    /**    
     * 返回此set中的元素的数量（set的容量）。    
     *     
     * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。    
     * @return 此set中的元素的数量（set的容量）。    
     */    

    public int size() {  

    return map.size();  

    }  



    /**     
     * 如果此set不包含任何元素，则返回true。      
     *       
     * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。       
     * @return 如果此set不包含任何元素，则返回true。      
     */       
    public boolean isEmpty() {  

    return map.isEmpty();  

    }  



    /**    
     * 如果此set包含指定元素，则返回true。    
     * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))    
     * 的e元素时，返回true。     
     *    
     * 底层实际调用HashMap的containsKey判断是否包含指定key。    
     * @param o 在此set中的存在已得到测试的元素。    
     * @return 如果此set包含指定元素，则返回true。   
     */     

    public boolean contains(Object o) {  

    return map.containsKey(o);  

    }  



    /**     
     * 如果此set中尚未包含指定元素，则添加指定元素。     
     * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))    
     * 的元素e2，则向此set 添加指定的元素e。     
     * 如果此set已包含该元素，则该调用不更改set并返回false。    
     *     
     * 底层实际将将该元素作为key放入HashMap。    
     * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key 
     * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true），     
     * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变，    
     * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中，     
     * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。    
     * @param e 将添加到此set中的元素。    
     * @return 如果此set尚未包含指定元素，则返回true。   
     */     

    public boolean add(E e) {  

    return map.put(e, PRESENT)==null;  

    }  



    /**     
     * 如果指定元素存在于此set中，则将其移除。     
     * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e，    
     * 则将其移除。如果此set已包含该元素，则返回true    
     * （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。    
     *     
     * 底层实际调用HashMap的remove方法删除指定Entry。    
     * @param o 如果存在于此set中则需要将其移除的对象。    
     * @return 如果set包含指定元素，则返回true。     
     */    

    public boolean remove(Object o) {  

    return map.remove(o)==PRESENT;  

    }  



    /**    
     * 从此set中移除所有元素。此调用返回后，该set将为空。   
     *     
     * 底层实际调用HashMap的clear方法清空Entry中所有元素。    
     */     

    public void clear() {  

    map.clear();  

    }  



    /**    
     * 返回此HashSet实例的浅表副本：并没有复制这些元素本身。    
     *    
     * 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。   
     */      

    public Object clone() {  

        try {  

            HashSet<E> newSet = (HashSet<E>) super.clone();  

            newSet.map = (HashMap<E, Object>) map.clone();  

            return newSet;  

        } catch (CloneNotSupportedException e) {  

            throw new InternalError();  

        }  

    }  

}  



public class HashSet<E>  

    extends AbstractSet<E>  

    implements Set<E>, Cloneable, java.io.Serializable  

{  

    static final long serialVersionUID = -5024744406713321676L;  



    // 底层使用HashMap来保存HashSet中所有元素。     
    private transient HashMap<E,Object> map;  



    // 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。     
    private static final Object PRESENT = new Object();  

    /**    
     * 默认的无参构造器，构造一个空的HashSet。    
     *    
     * 实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。   
     */     

    public HashSet() {  

    map = new HashMap<E,Object>();  

    }  

    /**    
     * 构造一个包含指定collection中的元素的新set。    
     *    
     * 实际底层使用默认的加载因子0.75和足以包含指定    
     * collection中所有元素的初始容量来创建一个HashMap。    
     * @param c 其中的元素将存放在此set中的collection。   
     */     

    public HashSet(Collection<? extends E> c) {  

    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));  

    addAll(c);  

    }  

    /**    
     * 以指定的initialCapacity和loadFactor构造一个空的HashSet。    
     *      
     * 实际底层以相应的参数构造一个空的HashMap。     
     * @param initialCapacity 初始容量。    
     * @param loadFactor 加载因子。    
     */     

    public HashSet(int initialCapacity, float loadFactor) {  

    map = new HashMap<E,Object>(initialCapacity, loadFactor);  

    }  



    /**    
     * 以指定的initialCapacity构造一个空的HashSet。    
     *    
     * 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。    
     * @param initialCapacity 初始容量。    
     */    

    public HashSet(int initialCapacity) {  

    map = new HashMap<E,Object>(initialCapacity);  

    }  



    /**    
     * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。    
     * 此构造函数为包访问权限，不对外公开，实际只是是对LinkedHashSet的支持。   
     *   
     * 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。   
     * @param initialCapacity 初始容量。     
     * @param loadFactor 加载因子。     
     * @param dummy 标记。      
     */    

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {  

    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);  

    }  



    /** 
     * 返回对此set中元素进行迭代的迭代器。返回元素的顺序并不是特定的。     
     *      
     * 底层实际调用底层HashMap的keySet来返回所有的key。     
     * 可见HashSet中的元素，只是存放在了底层HashMap的key上，    
     * value使用一个static final的Object对象标识。    
     * @return 对此set中元素进行迭代的Iterator。    
     */      

    public Iterator<E> iterator() {  

    return map.keySet().iterator();  

    }  



    /**    
     * 返回此set中的元素的数量（set的容量）。    
     *    
     * 底层实际调用HashMap的size()方法返回Entry的数量，就得到该Set中元素的个数。    
     * @return 此set中的元素的数量（set的容量）。    
     */    

    public int size() {  

    return map.size();  

    }  



    /**   
     * 如果此set不包含任何元素，则返回true。    
     *   
     * 底层实际调用HashMap的isEmpty()判断该HashSet是否为空。    
     * @return 如果此set不包含任何元素，则返回true。    
     */     

    public boolean isEmpty() {  

    return map.isEmpty();  

    }  



    /**    
     * 如果此set包含指定元素，则返回true。    
     * 更确切地讲，当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))    
     * 的e元素时，返回true。     
     *    
     * 底层实际调用HashMap的containsKey判断是否包含指定key。     
     * @param o 在此set中的存在已得到测试的元素。      
     * @return 如果此set包含指定元素，则返回true。    
     */     

    public boolean contains(Object o) {  

    return map.containsKey(o);  

    }  



    /**     
     * 如果此set中尚未包含指定元素，则添加指定元素。     
     * 更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2))     
     * 的元素e2，则向此set 添加指定的元素e。      
     * 如果此set已包含该元素，则该调用不更改set并返回false。    
     *    
     * 底层实际将将该元素作为key放入HashMap。    
     * 由于HashMap的put()方法添加key-value对时，当新放入HashMap的Entry中key   
     * 与集合中原有Entry的key相同（hashCode()返回值相等，通过equals比较也返回true），     
     * 新添加的Entry的value会将覆盖原来Entry的value，但key不会有任何改变，    
     * 因此如果向HashSet中添加一个已经存在的元素时，新添加的集合元素将不会被放入HashMap中，     
     * 原来的元素也不会有任何改变，这也就满足了Set中元素不重复的特性。    
     * @param e 将添加到此set中的元素。    
     * @return 如果此set尚未包含指定元素，则返回true。    
     */      

    public boolean add(E e) {  

    return map.put(e, PRESENT)==null;  

    }  



    /**      
     * 如果指定元素存在于此set中，则将其移除。         
     * 更确切地讲，如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e，     
     * 则将其移除。如果此set已包含该元素，则返回true      
     * （或者：如果此set因调用而发生更改，则返回true）。（一旦调用返回，则此set不再包含该元素）。     
     *    
     * 底层实际调用HashMap的remove方法删除指定Entry。     
     * @param o 如果存在于此set中则需要将其移除的对象。    
     * @return 如果set包含指定元素，则返回true。    
     */     

    public boolean remove(Object o) {  

    return map.remove(o)==PRESENT;  

    }  



    /**     
     * 从此set中移除所有元素。此调用返回后，该set将为空。      
     *      
     * 底层实际调用HashMap的clear方法清空Entry中所有元素。     
     */     

    public void clear() {  

    map.clear();  

    }  



    /**   
     * 返回此HashSet实例的浅表副本：并没有复制这些元素本身。    
     *    
     * 底层实际调用HashMap的clone()方法，获取HashMap的浅表副本，并设置到HashSet中。    
     */     

    public Object clone() {  

        try {  

            HashSet<E> newSet = (HashSet<E>) super.clone();  

            newSet.map = (HashMap<E, Object>) map.clone();  

            return newSet;  

        } catch (CloneNotSupportedException e) {  

            throw new InternalError();  

        }  

    }  

}

View Code

相关说明：

1) 相关HashMap的实现原理，请参考我的上一遍总结：深入Java集合学习系列：HashMap的实现原理。

2) 对于HashSet中保存的对象，请注意正确重写其equals和hashCode方法，以保证放入的对象的唯一性。

hash表的原理

(1)调用hashcode()方法计算hash码值
(2)根据y=k(x)这样的函数计算存储位置
(3)如果位置上没有元素，则将元素存储
(4)如果该位置上有元素，则需调用equals方法比较内容是否相同

package com.bjsxt.hashset;

public class Person {
    private String name;
    private int 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;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    //Person类必须重写hashCode()方法及equals()方法
    //Hash表原理
    /***
     * (1)调用hashCode()方法计算Hash码值
     * (2)根据y=k(x)这样的函数计算存储位置
     * (3)如果位置上没有元素，则将元素存储
     * (4)如果该位置上有元素，则需调用equals方法比较内容是否相同
     */
    @Override
    public int hashCode() {
        System.out.println("Person.hashCode()");
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        System.out.println("Person.equals()");
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Person other = (Person) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]";
    }
    
}

View Code

package com.bjsxt.hashset;

import java.util.HashSet;
import java.util.Iterator;

public class TestHashSet {
    public static void main(String[] args) {
        //HashSet底层数组结构使用的是hash表  ,主结构数组, +链表
        //创建集合对象
        HashSet hs=new HashSet();
        hs.add("hello");
        System.out.println(    hs.add("world"));
        hs.add("java");
        System.out.println(hs.add("world"));
        System.out.println("集合中元素的个数:"+hs.size());
        System.out.println(hs);
        System.out.println(hs.contains("java")+"	"+hs.contains("sql"));
        //使用迭代器遍历元素
        Iterator ite=hs.iterator();
        while(ite.hasNext()){
            System.out.println(ite.next());
        }
        
    }
}

View Code

package com.bjsxt.hashset;

import java.util.HashSet;

public class TestPerson {
    public static void main(String[] args) {
        HashSet hs=new HashSet();
        //创建4个Person类型的对象
        Person p1=new Person("marry", 20);
        Person p2=new Person("lili", 23);
        Person p3=new Person("marry", 20);
        Person p4=new Person("jack", 30);
        //添加集合中
        hs.add(p1);
        hs.add(p2);
        hs.add(p3);
        hs.add(p4);
        System.out.println(hs);
    }
}

View Code

13.TreeSet 的使用_JDK 源码分析

13.1TreeSet 的底层数据结构

1）TreeMap（key，唯一，而且有序，升序），底层数据结构黑红树，而且 TreeMap 中的 key 实际上就是一个 TreeSet，如果使用自定义对象作为 key,要求必须具备比较规则

2）使用 TreeMap 要求使用内部比较器或外部比较器

13.2TreeSet 的使用

13.3JDK 源码分析

package com.bjsxt.treeset;

import java.util.Comparator;

public class ComCharactor implements Comparator{

    @Override
    public int compare(Object o1, Object o2) {
        Person p1=(Person)o1;
        Person p2=(Person)o2;
        //compareTo是String类中指供的比较大小的方法
        return p1.getName().compareTo(p2.getName());
    }

}

View Code

package com.bjsxt.treeset;

import java.util.Comparator;

public class ComCharactorAndAge implements Comparator {

    @Override
    public int compare(Object o1, Object o2) {
        Person p1=(Person)o1;
        Person p2=(Person)o2;
        if(p1.getName().compareTo(p2.getName())<0){
            return -1;
        }else if(p1.getName().compareTo(p2.getName())>0){
            return 1;
        }else{
            return p1.getAge()-p2.getAge();
        }
        //return 0;
    }

}

View Code

package com.bjsxt.treeset;

public class Person implements Comparable {
    private String name;//姓名
    private int 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;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]";
    }
    @Override
    public int compareTo(Object o) {
        //按照年龄的升序比较
        Person p=(Person)o;
        
        return this.age-p.getAge();
    }
    
}

View Code

package com.bjsxt.treeset;

import java.util.Comparator;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.TreeSet;

/** 
 * TreeSet的底层所使用的是TreeMap   -->红黑树
 * TreeSet JDK源码分析
 *  private transient NavigableMap<E,Object> m;  //一个接口,间接继承了Map
 *    private static final Object PRESENT = new Object();
 *  public TreeSet() {
        this(new TreeMap<E,Object>());  //创建了一个TreeMap的对象
    }
    //调用的本类中的带参构造方法
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;   //接口new 实现类
    }
     public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));  //调用了本类中的带参构造方法
    }
    添加方法
     public boolean add(E e) {
        return m.put(e, PRESENT)==null;  //传入的元素作为Map中的key，统一的值为Object类型的对象
    }
    public int size() {
        return m.size();
    }
    
    
 * @author Administrator
 *
 */
public class TestTreeSet {
    public static void main(String[] args) {
    
        //创建集合对象
        //TreeSet ts=new TreeSet();
        //Comparator comc=new ComCharactor();//创建外部比较器对象
        Comparator com=new ComCharactorAndAge();
        TreeSet ts=new TreeSet(com);
        //创建Person对象
        Person p1=new Person("marry", 20);
        Person p2=new Person("lili", 19);
        Person p3=new Person("jack", 20);
        Person p4=new Person("marry", 18);
        //添加到集合中
        ts.add(p1);
        ts.add(p2);
        ts.add(p3);
        ts.add(p4);
        System.out.println("集合中元素的个数:"+ts.size());
        System.out.println(ts);
    }
}

View Code

14.泛型

14.1 为什么需要使用泛型

起因：
JDK1.4 以前类型不明确：
装入集合的类型都被当作 Object 对待，从而失去自己的实际类型。

从集合中取出时往往需要转型，效率低，容易产生错误。

解决办法：
泛型，在定义集合的时候同时定义集合中对象的类型

好处：
增强程序的可读性和安全性

14.2 泛型的分类

(1)泛型类
(2)泛型接口
(3)泛型方法

package com.bjsxt.generic;

public class MyGeneric<T> {//T就是一个英文字母，代表一种数据类型

}
class TestMyGeneric{
    public static void main(String[] args) {
        MyGeneric<String> my1=new MyGeneric<String>();
        MyGeneric<Integer> my2=new MyGeneric<Integer>();
    }
}

View Code

package com.bjsxt.generic;

public interface MyInterface<T> {

}
class MyImplement implements MyInterface<String>{
    
}
class MyImplement1<T> implements MyInterface<T>{
    
}
class TestMyInterface{
    public static void main(String[] args) {
        MyImplement my=new MyImplement();
        
        MyImplement1<Integer> my2=new MyImplement1<Integer>();
    }
}

View Code

package com.bjsxt.generic;

public class MyMethod<T> {//泛型类
    public void show(T t){  //在创建MyMethod类的对象时决定
        System.out.println(t);
    }
    public <Q> void method(Q q){ //在调用method这个方法时明确
        System.out.println(q);
    }
    public <K>void fun(K...k){ //可变参数的泛型方法
        for (int i = 0; i < k.length; i++) {
            System.out.println(k[i]);
        }
    }
}

View Code

package com.bjsxt.generic;

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        //在创建集合对象时，明确集合中所存储的元素的类型
        
        ArrayList<String> al=new ArrayList<String>();
        al.add("hello");
        //al.add(123);
        for (String str : al) {
            System.out.println(str);
        }
        
        int [] arr=new int[5];
    }
}

View Code

package com.bjsxt.generic;

public class TestMyMethod {
    public static void main(String[] args) {
        MyMethod<String> my=new MyMethod<String>();
        my.show("hello");//在创建类的对象时明确了数据类型为String
        
        //在了泛型方法，解决了参数个数相同的情况下的方法重载
        my.method("hello");
        my.method(123);
        my.method('a');
        
        //可变参数的泛型方法，解决参数的个数不同，类型不同的方法重载
        my.fun("hello");
        my.fun("hello","world","java");
        my.fun(123,456);
    }
}

View Code

15.泛型的高级使用_在容器中使用泛型

15.1 泛型的高级使用

泛型的上限:使用关键字 extends，表示参数化的类型可能是所指定的类型或者是此类型的子类

泛型的下限:使用关键字 super 进行声明，表示参数化的类型可能是所指定的类型，或者是此类型的父类型，直至 Object类

15.2 在容器中使用泛型

package com.bjsxt.generic;

public class Person implements Comparable<Person> {
    private String name; //姓名
    private int 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;
    }
    public Person(String name, int age) {
        super();
        this.name = name;
        this.age = age;
    }
    public Person() {
        super();
    }
    @Override
    public String toString() {
        return "Person [name=" + name + ", age=" + age + "]";
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Person other = (Person) obj;
        if (age != other.age)
            return false;
        if (name == null) {
            if (other.name != null)
                return false;
        } else if (!name.equals(other.name))
            return false;
        return true;
    }
    @Override
    public int compareTo(Person o) {
        
        return this.getName().compareTo(o.getName());
    }
    
}

View Code

package com.bjsxt.generic;

public class Student extends Person {
    private String stuNo;//学号

    public String getStuNo() {
        return stuNo;
    }

    public void setStuNo(String stuNo) {
        this.stuNo = stuNo;
    }

    public Student(String name, int age, String stuNo) {
        super(name, age);
        this.stuNo = stuNo;
    }

    public Student() {
        super();
    }

    @Override
    public String toString() {
        return super.toString()+"Student [stuNo=" + stuNo + "]";
    }
    
}

View Code

package com.bjsxt.generic;

import java.util.ArrayList;

public class Test {
    public static void main(String[] args) {
        //创建集合对象，同时明确了集合中所存储的对象的类型只能是Person类型
        ArrayList<Person> al=new ArrayList<Person>();
        //创建Person类型的对象添加到集合中
        Person p1=new Person("marry", 20);
        Person p2=new Person("lili",29);
        Person p3=new Person("jack",18);
        //添加以集合中
        al.add(p1);
        al.add(p2);
        al.add(p3);
        //遍历集合
        print(al);
        
        
        
        //创建一个集合对象，用于存储Student类型的对象
        ArrayList<Student> al2=new ArrayList<Student>();
        Student stu1=new Student("sean", 20, "sxt1001");
        Student stu2=new Student("nico",19,"sxt1002");
        //添加到集合中
        al2.add(stu1);
        al2.add(stu2);
        //需要遍历集合
        print(al2);
        
        //调用show方法
        System.out.println("
---------------------------
");
        show(al);
        show(al2);
        ArrayList<Object> alObject=new ArrayList<Object>();
        Object ob1=new Object();
        Object obj2=new Object();
        alObject.add(ob1);
        alObject.add(obj2);
        
        show(alObject);
    }
    //Person及Person的子类
    public static void print(ArrayList<? extends Person> al){ //相当于ArrayList<Person> al=new ArrayList<Student>();不匹配
        for (Person p : al) {
            System.out.println(p);
        }
    }
    public static void show(ArrayList<? super Student> al){
        for (Object obj : al) {
            System.out.println(obj);
        }
    }
}

View Code

package com.bjsxt.generic;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.TreeMap;
import java.util.TreeSet;

public class Test2 {
    public static void main(String[] args) {
        
        ArrayList<String> al=new ArrayList<String>();
        al.add("hello");
        
        LinkedList<Integer> linkedList=new LinkedList<Integer>();
        linkedList.add(123);//123进行了自动装箱
        
        //存储自定时对象时，要求Person类重写hashCode()及equals()方法
        HashSet<Person> hs=new HashSet<Person>();
        
        //Person 对象具备比较规则 ，可以是内部比较器，也可以外部比较器
        TreeSet<Person> treeSet=new TreeSet<Person>();
        
        HashMap<String,Integer> hm=new HashMap<String,Integer>();
        hm.put("hello", 123);
        
        HashMap<Person,String> hm2=new HashMap<Person,String>();
        Person p1=new Person("marry",20);
        hm2.put(p1, p1.getName());
        
        TreeMap<Person,Integer> tm=new TreeMap<Person,Integer>();
        tm.put(p1, p1.getAge());
        
        //泛型只在编译期间起作用
    }
}

View Code

16.迭代器_遍历 List_Set

16.1 迭代器的由来

16.2 使用迭代器遍历集合

package com.bjsxt.list_arraylist;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Scanner;

public class TestArrayList {
    public static void main(String[] args) {
        //创建集合对象, 接口 new 实现类
        List list=new ArrayList();
        //(1)添加add (Object obj)
        list.add("hello");
        list.add(123);//自动装箱
        list.add(new Scanner(System.in));
        //(2)集合中元素的个数 size()
        System.out.println(list.size());
        System.out.println("集合是否为空:"+list.isEmpty());
        //(3)addAll(Collection c)
        List list2=new ArrayList();
        list2.add("hello");
        list2.add(123);
        list.addAll(list2);
        System.out.println("list集合中元素的个数:"+list.size());
        System.out.println(list);
        //(4)删除
        System.out.println("根据对象去删除:");
        list.remove("hello");
        System.out.println(list);
        //list.remove(123);//认为123是索引
        list.remove(new Integer(123));
        System.out.println(list);
        list.remove(0);//根据索引去删除
        System.out.println(list);
        list.add("world");  //list [hello,123,world] list2[hello,123]
        //list.removeAll(list2);
        //list.retainAll(list2);
        System.out.println(list);
        
        //(5)判断
        System.out.println("hello在集合中是否存在:"+list.contains("hello"));
        System.out.println("java在集合中是否存在:"+list.contains("java"));
        //(6)清空集合中所有的元素对象
        System.out.println(list);
        System.out.println(list2);
        System.out.println(list.containsAll(list2));
        //list.clear();
        //System.out.println(list);
        //(7)获取指定索引位置上的元素对象
        System.out.println(list.get(1));
        //(8)设置
        list.set(1, "java");
        System.out.println(list);
        //(9)在指定的索引位置上添加元素对象
        list.add(1, "html");
        System.out.println(list);
        
        //(10)查找元素在集合中的位置
        System.out.println(list.indexOf("java")+"	"+list.indexOf("sql"));
        //(11)遍历集合中元素的内容
        /**(1)使用加强for循环遍历集合中的元素*/
        System.out.println("
使用加强for循环遍历集合中的元素
");
        for(Object obj:list){
            System.out.println(obj);
        
        }
        /**(2)使用普通for循环遍历集合中的元素对象*/
        System.out.println("
使用普通for循环遍历集合中的元素对象
");
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }
        /**(3)使用迭代器*/
        System.out.println("
使用迭代器遍历集合中的元素
");
        Iterator ite=list.iterator();  //正向遍历
        while(ite.hasNext()){//判断集合中是否有元素对象
            Object obj=ite.next();
            System.out.println(obj);
        }
        System.out.println("使用listIterator()遍历");
        ListIterator listIte=list.listIterator();
        System.out.println("正向遍历");
        System.out.println("在集合的开头，后面还有元素对象吗?"+listIte.hasNext());
        System.out.println("在集合的开头，前面有元素对象吗?"+listIte.hasPrevious());
        while(listIte.hasNext()){
            System.out.println(listIte.next());
        }
        System.out.println("到达集合的末尾，后面还有元素对象吗?"+listIte.hasNext());
        System.out.println("到达集合的末尾，前面有元素对象吗?"+listIte.hasPrevious());
        System.out.println("
逆向遍历集合中的元素
");
        while(listIte.hasPrevious()){
            System.out.println(listIte.previous());
        }
        
    }
}

View Code

17.迭代器遍历 Map

17.1ListIterator 接口

ListIterator 是对 Iterator 接口的扩展，用于解决并发修改的异常

17.2 遍历 Map

package com.bjsxt.listiterator;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;

/**
 *  public ListIterator<E> listIterator() {
        return new ListItr(0);
    }*/
public class Test {
    public static void main(String[] args) {
        ArrayList<String> al=new ArrayList<String>();
        al.add("hello");
        al.add("world");
        al.add("java");
        ListIterator<String> ite    =al.listIterator();//ListIterator是Iterator接口的扩展
        while(ite.hasNext()){
            String str=ite.next();
            if ("world".equals(str)) {
                ite.add("sql");
            }
        }
        System.out.println(al);
        System.out.println("逆向遍历元素");
        while(ite.hasPrevious()){
            System.out.println(ite.previous());
        }
    }
}

View Code

package com.bjsxt.listiterator;

import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class TestMap {
    public static void main(String[] args) {
        HashMap<String,Integer> hm=new HashMap<String,Integer>();
        hm.put("hello", 123);
        hm.put("world", 345);
        hm.put("java", 567);
        //第一种
        Set<String> set=hm.keySet();
        for (String str : set) {
            System.out.println(str+"	"+hm.get(str));
        }
        //第二种遍历  Entry<String, Integer>键值关系的类型
        Set<Entry<String, Integer>> entry=hm.entrySet();
        for (Entry<String, Integer> ent : entry) {
            System.out.println(ent.getKey()+"	"+ent.getValue());
        }
    }
}

View Code

java集合

1.基本概念_Collection_Set_List 接口介绍

1.1 为什么需要集合?

1.2 容器框架

1.3 各接口的特点

2.List 接口_ArrayList_用法详解

1.ArrayList的实现：

2.1ArrayList 的用法

源码分析一arraylist

5.LinkedList 的特点_链表_JDK 源码分析

5.1LinkedList 的特点

5.2 链表

5.3JDK 源码分析

6.Vector 用法和 ArrayList 区别_JDK 源码分析

6.1Vector 的用法

6.2Vector_JDK 源码分析

6.3Vector 与 ArrayList 的区别

7.Map 接口_HashMap_Hashtable 的用法详解

7.1Map 接口

7.2HashMap 的使用

7.3HashMap 与 Hashtable 的区别

HashMap与Hashtable的区别

8.HashMap 底层实现

1.哈希表的结构和特点

2.哈希表是如何添加数据的

9.二叉树和红黑树

9.1 树

9.2 二叉树

9.3 二叉查找/搜索/排序树 BST (binary search/sort tree)

9.4 平衡二叉树 （Self-balancing binary search tree）

9.5 红黑树

10.TreeMap 的使用和底层实现

10.1TreeMap 的使用

10.2TreeMap 的底层实现

11.Set 接口_HashSet 的用法

11.1Set 接口

11.2HashSet 的用法

13.TreeSet 的使用_JDK 源码分析

13.1TreeSet 的底层数据结构

13.2TreeSet 的使用

13.3JDK 源码分析

14.泛型

14.1 为什么需要使用泛型

14.2 泛型的分类

15.泛型的高级使用_在容器中使用泛型

15.1 泛型的高级使用

15.2 在容器中使用泛型

16.迭代器_遍历 List_Set

16.1 迭代器的由来

16.2 使用迭代器遍历集合

17.迭代器遍历 Map

17.1ListIterator 接口

17.2 遍历 Map

19.容器体系框架总结

9.4 平衡二叉树（Self-balancing binary search tree）