集合框架(二)

集合框架

就是内存中的”容器对象” - 存储数据的.开发中来替代数组的使用.

结构

api:java.util
  
Collection[I]
  - List[I] - 有序可重复
    - ArrayList[C]
    - linkedList[C]
    - Vector[C]
  - Set[I] - 无序不可重复
    - HashSet[C]
    - SortedSet[I]
      - TreeSet[C]
Map[I]
  - HashMap[C] - key-value的形式存储数据的,针对key是无序不可重复.
  - Hashtable[C]
    - Properteis[C] - 属性文件在内存中的映射的对象

Collection[I]

1. boolean add(E e);//向容器中添加一个元素
2. void clear();//清空容器
3. boolean contains(Object o);//判断容器中是否包含某个对象
4. boolean isEmpty();//如果集合中没有数据,集合大小为0,返回true
5. Iterator iterator();// 获取集合对象的迭代器
6. boolean remove(Object obj);//删除集合容器中第一次出现的这个对象.只能删除1个
7. int size();//返回集合中的数据的个数 - 集合的大小

List[I]

特点 - 有序并且是可以重复的.

1. E get(int index);//根据下标去取.集合下标边界[0,集合.size()-1]
2. int indexOf(Object obj);//返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。
3. E remove(int index);//根据下标删除,并且返回刚刚删除的那个元素
4. Object[] toArray();//将集合转换成数组.

ArrayList[C]

特点:有序可重复的,底层数据结构就是一个”动态增长”的数组.

优点:因为数组是一个有序的序列,所以它可以通过下标直接取值 - 查询效率高.

缺点:增删效率会低.因为涉及到下标的移动.

分析源码

 
private static final int DEFAULT_CAPACITY = 10;


private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//就是真正的存储数据的数组
transient Object[] elementData;

 
private int size;


//构造
public ArrayList() {
  //1. 初始化elementData,长度为0
  //2. 是为了后面的ensureCapacityInternal方法中判断是否是第一次调用add方法
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  //this.elementData = {}
}

剖析add方法

ArrayList扩容的原理

public boolean add(E e) {
ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

扩容方法

private void ensureCapacityInternal(int minCapacity) {	 //第一次进来1
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {	 //true

//第一次minCapacity = 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

继续ensureExplicitCapacity(minCapacity);

private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
//第一次进来10-0>0
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

grow(minCapacity)

private void grow(int minCapacity) {
// 第一次
//oldCapacity = 0
//newCapacity = 0
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);	//1.5倍
if (newCapacity - minCapacity < 0)//第一次会进来
newCapacity = minCapacity;//newCapacity = 10
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:

//第一次执行add方法的时候,底层会给我们初始化了一个长度为10的Object[]数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

集合的遍历

1. 直接输出

2. 增强for循环 - 只读

   //只读的循环.如果在循环的过程中进行了remove操作 
   //抛出java.util.ConcurrentModificationException并发修改异常
      
   //实际的底层,调用迭代器对象中的next方法
      
   private class Itr implements Iterator {
           int cursor;       // index of next element to return
           int lastRet = -1; // index of last element returned; -1 if no such
           int expectedModCount = modCount;
            public E next() {
             checkForComodification();
             //....
           }
    final void checkForComodification() {
      //modCount是当初调用add方法,添加1个元素,modCount自增1个
      if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    }
   }
      
   发现只要调用了remove方法 - modCount++
    private void fastRemove(int index) {
     modCount++;
     int numMoved = size - index - 1;
     if (numMoved > 0)
       System.arraycopy(elementData, index+1, elementData, index,
                        numMoved);
     elementData[--size] = null; // clear to let GC do its work
   }
      
   

3.普通for

4.迭代器

因为不同的集合的底层的数据结构是不一样的.数据结构不一样,它的遍历方式不一样

为了访问/遍历不同数据结构的集合提供一种统一的遍历方式

 //1. 获取集合的迭代器
Iterator iter = list.iterator();
//2. 调用hasNext方法
while(iter.hasNext()){		//判断迭代器中是否仍有下一个元素可被迭代
  Long p = iter.next();		//获取当前迭代的
  System.out.println(p);
}

5.jdk8提供的新的遍历方式

list.forEach(new Consumer() {		//匿名内部类
  @Override
  public void accept(Long aLong) {
    System.out.println(aLong);
  }
});
      
//lambda表达式来替代匿名内部类的写法
//配合函数式接口[只能包含【一个】抽象方法]
System.out.println("====== lambda ====");
list.forEach(e -> System.out.println(e));
      
System.out.println("========");
list.forEach(System.out::println);

linkedList[C]

有序的序列,底层的数据结构双向链表,jdk6以及之前是双向循环链表

链表结构的特点:查询效率很低,每次都会从头节点开始遍历.但是增删效率高,只会涉及到相邻节点的移动.

适合解决栈列和队列的业务题型 - 贪吃蛇

栈列 - 先进后出

队列 - 先进先出

链表结构

相对于数组这种数据结构,需要占用更多的内存.每个节点除了保存具体的数据,还需要保存相邻节点的地址.

1. 单向链表

   head - 头节点

   tail - 尾节点

   element - 节点中真正的保存的数据

   next - 下一个节点的地址
   

2. 单向循环链表

   尾节点的next又指向了头节点.
   

3. 双向链表 - linkedList底层数据结构

   增加了一个pre - 保存的是上一个节点的地址.

4. 双向循环链表

剖析源码

//Node代表的是链表的节点 
private static class Node {
   E item;//真正的元素
   Node next;	//下一个节点的地址
   Node prev;	//上一个节点的地址

   Node(Node prev, E element, Node next) {
     this.item = element;
     this.next = next;
     this.prev = prev;
   }
 }

//双向链表如何插入一个新的节点
public boolean add(E e) {
  linkLast(e);
  return true;
}

void linkLast(E e) {
  //第【一】次进入last最后一个节点Node - null
  final Node l = last;//l = null
  
  //第二次进入 l = new Node<>(null,"ok",null)
  
  //第【一】次进入
  //newNode = new Node<>(null,"ok",null)
  
  //第二次进入
  //newNode =  new Node<>(链表中原来的最后一个节点l, "java", null);
  final Node newNode = new Node<>(l, e, null);
  
  //新插入的节点肯定是作为最后一个节点 - 尾节点
  last = newNode;
  if (l == null)	//第【一】次进入,链表之前没有任何元素
    first = newNode;	//新的节点作为头节点
  else					
    l.next = newNode;	//原来链表中的最后一个节点的next同时也指向新的节点
  size++;
  modCount++;
}

查找源码

 public E get(int index) {
   checkElementIndex(index);
   return node(index).item;
 }

Node node(int index) {	//index = 3
  				// 假设集合中有10个元素 = size = 10
				//index<5 - 链表的坐标
  if (index < (size >> 1)) {
    Node x = first;//确定头节点
    for (int i = 0; i < index; i++)
      x = x.next;
      //① - x第二个 ,i=0
      //i=1  x第三个
      //i=2  x第四个
    return x;
  } else {//index>=5
    Node x = last;
    for (int i = size - 1; i > index; i--)
      x = x.prev;
    return x;
  }
}

删除源码

 public E remove(int index) {
   checkElementIndex(index);
   //找到index对应的Node对象,传入到了unlink方法中.
   return unlink(node(index));
 }

E unlink(Node x) {
  // assert x != null;
  final E element = x.item;
  final Node next = x.next;
  final Node prev = x.prev;

  if (prev == null) {	//防止删除的是头节点
    first = next;	//需要删除的那个节点的下一个节点作为头节点了.
  } else {		//删除的是中间节点
    prev.next = next;	//原来节点的上一个节点的next指向原来节点的下一个节点
    x.prev = null;	//优化,更快让GC会回收pre指针.
  }

  if (next == null) {	//删除的是尾结点
    last = prev;	//原来节点的上一个节点作为尾节点
  } else {		//删除的是中间节点
    next.prev = prev;	//原来节点的下一个节点指向原来节点的上一个节点
    x.next = null;
  }

  x.item = null;
  size--;
  modCount++;
  return element;
}

练习-括号匹配

package stu.aistar.day11.homework;

import java.util.linkedList;
import java.util.Scanner;


public class BracketsDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("输入括号: >");
        String line = sc.nextLine();
        if(matches(line)){   		//isEmpty()  返回true
            System.out.println("匹配");
        }else{
            System.out.println("不匹配");
        }
    }

    private static boolean matches(String line) {
        //1. 将字符串转成字符数组
        char[] arr = line.toCharArray();
        //2. 新建一个linkedList集合
        linkedList list = new linkedList<>();
        //3. 将数组中的第一个元素压入栈顶
        list.push(arr[0]);
        //4. 从arr数组的第二个位置开始遍历
        for (int i = 1; i < arr.length; i++) {
            //()[]{}
            
            Character c = arr[i];		//获取当前的arr[i]
           
            if(list.isEmpty()){		 	//为了避免在栈顶已经没有元素的情况下还去获取
                list.push(c);			//栈顶元素,非空判断
                continue;
            }

            Character top = list.getFirst();    //5. 先获取栈顶元素

           					//6. 栈顶元素和当前的arr[i]进行匹配
            if(top.equals('(')&&c.equals(')') || top.equals('{')&&c.equals('}') || top.equals('[')&&c.equals(']')){
                list.pop();		//弹出栈顶元素
            }else{ 
                list.push(c);		//继续将当前的arr[i]压入栈顶
            }
        }
        return list.isEmpty();
    }
}

Map[I] HashMap[C]

数据存储的形式是key-value,针对key是无序不可重复的.

jdk8.x之前,底层的数据结构是桶数组+链表

jd8.0开始,底层的数据结构是桶数组+链表+红黑树

桶(哈希桶)数组 - 里面的元素放在数组的这个位置是通过一个哈希算法计算得到的.

图示

剖析put方法

public V put(K key, V value) {
  return putVal(hash(key), key, value, false, true);
}

//hash函数就是扰动函数
//1. 尽可能减少哈希冲突
static final int hash(Object key) {
  int h;
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//map数据结构图示中每个节点
static class Node implements Map.Entry {
  final int hash;
  final K key;
  V value;
  Node next;//单向链表

  Node(int hash, K key, V value, Node next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
  }

transient Node[] table;//默认值是null

//hash(key)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
  //第一次进来
  Node[] tab; Node p; int n, i;
  
  //第一次进来,第二次肯定不走
  if ((tab = table) == null || (n = tab.length) == 0)
    //第一次肯定会进来
    //1. 对tab进行一个初始化操作
    //2. 得到初始化数组的长度,赋值给了n
    n = (tab = resize()).length;//n=16
  
  //第一次肯定判断结果为null
  if ((p = tab[i = (n - 1) & hash]) == null)
    //tab[i] = 新的节点
    tab[i] = newNode(hash, key, value, null);
  else {
    //哈希碰撞了,哈希冲突了.
    Node e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
      //key值冲突了.
      //e = 数组中的旧的Node对象
      e = p;
    //hash虽然碰撞了,但是key是不一样
    else if (p instanceof TreeNode)//判断是否为红黑树结构
      //当链表的节点>8个,链表结构转成红黑树结构
      //当红黑树节点<6个,恢复成链表结构
      e = ((TreeNode)p).putTreeval(this, tab, hash, key, value);
    else {//链表结构
      for (int binCount = 0; ; ++binCount) {
        //p代表的就是哈希碰撞位置的第一个Node对象
        if ((e = p.next) == null) {//新的节点挂载到链表的末尾
          p.next = newNode(hash, key, value, null);
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        //新的节点可能和链表结构中的某个节点的key也是一样的
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
          break;
        
        //e肯定是不为null
        p = e;
      }
    }
    if (e != null) { // existing mapping for key
      //把旧的节点的value赋值给了oldValue,put方法的返回结果
      V oldValue = e.value;
      if (!onlyIfAbsent || oldValue == null)
        //新值覆盖旧值
        e.value = value;
      afterNodeAccess(e);
      return oldValue;
    }
  }
  ++modCount;
  if (++size > threshold)
    resize();
  afterNodeInsertion(evict);
  return null;
}

扩容方法

final Node[] resize() {
        Node[] 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
            //第一进来就会执行到此处 , 16
             //扩容因子是0.75
            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;
        //初始化一个长度为16的数组
        @SuppressWarnings({"rawtypes","unchecked"})
            Node[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node 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)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node 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;
    }

map集合的迭代方式

//第一种方式 - 将map集合中所有的key全部取出来放入到一个Set集合中.
//set集合 -   无序不可重复,map集合的key也是无序不可重复.
Set sets = maps.keySet();
//遍历set集合
Iterator iter = sets.iterator();
while(iter.hasNext()){
  Integer key = iter.next();
  String value = maps.get(key);
  System.out.println(key+":"+value);
}

//第二种方式 - 将map集合中的每对key-value封装到了一个内置的Entry对象中
//然后将每个entry对象放入到Set集合中
Set> entries = maps.entrySet();
Iterator> iter2 = entries.iterator();
while(iter2.hasNext()){
  Map.Entry e = iter2.next();
  Integer key = e.getKey();
  String value = e.getValue();
  System.out.println(key+"->"+value);
}

Map作业

String str = "python java python java mysql java mysql php";   spilt("\s")
//统计	String[] arr = ["python","java","python","java","php","python"];    
public static void main(String[] args) {
    String[] arr = {"python","java","python","java","php","python"};
    Map maps = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        maps.put(arr[i],maps.get(arr[i])==null?1:maps.get(arr[i])+1);
    }

    Set> entries = maps.entrySet();		//遍历
    Iterator> it = entries.iterator();  
    while (it.hasNext()){
        Map.Entry e = it.next();
        System.out.println(e.getKey()+":"+e.getValue());
    }
}

//统计	int[] arr = {1,2,1,2,3,4,1,2,5,.....}
public class CalNumCount {
    public static void main(String[] args) {
        int[] arr = {1,2,1,2,3,4,1,2,5,3,4,2,1,3};
        Map maps = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            maps.put(arr[i],maps.get(arr[i])==null?1:maps.get(arr[i])+1);
        }
        System.out.println(maps);
    }
}

//统计	String str = "sfhdsfkdfdfjdfjdfdjfdsa";
public class CountStrDemo {
    public static void main(String[] args) {

        String str = "ahfdfjdkfjsdafsed";

        count(str);

    }
    private static void count(String str) {
        Map maps = new HashMap<>();

        for (int i = 0; i < str.length(); i++) {  //用增强for循环更方便
            if (maps.containsKey(str.charAt(i))){
                Integer count = maps.get(str.charAt(i));
                maps.put(str.charAt(i),count+1);
            }else {
                maps.put(str.charAt(i),1);
            }
        }
	//定义list集合 用来存放map中的数据，只有list集合有sort方法！
        List> list = new ArrayList<>();       							

        Set> entries = maps.entrySet();
        Iterator> it = entries.iterator();
        while (it.hasNext()){
            Map.Entry nt = it.next();   //把map里面的值 传给 list里面
            list.add(nt);
        }

        list.sort((o1,o2)->o2.getValue()-o1.getValue());
	//遍历排好序的集合，完成了排序
        for (Map.Entry characterIntegerEntry : list) {
            System.out.println(characterIntegerEntry);			 
        }

    }
}

//下面有一个分割的 map 和 list排序方法 一致
//分割如下：
    String str = "python java python java mysql java mysql php";
    String[] arr1 = str.split("\s");   //     \s  是空格  其他的符号就用 \+符号
    for (String s : arr1) {
        System.out.print(s+"t");
    }

排序 比较器接口Comparator

jdk8.0开始,在List接口中已经定义了排序的方法

void sort(Comparator c) ; 中 Comparator c 就是排列的规则的意思，并且这个规则需要自己去定义。

分析:java.util.Comparator[I]函数式接口 - 允许使用lambda表达式

package stu.aistar.day11;

import stu.aistar.day10.Book;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;


public class ListSortDemo {
    public static void main(String[] args) {
        Book b1 = new Book(1,"1001","java",100.0d);
        Book b2 = new Book(2,"1002","java",200.0d);
        Book b3 = new Book(3,"1003","java",200.0d);
        Book b4 = new Book(4,"1004","python",300.0d);

        List bookList = new ArrayList<>();
        bookList.add(b1);
        bookList.add(b2);
        bookList.add(b3);
        bookList.add(b4);

//        bookList.sort(new Comparator() {
//            @Override
//            public int compare(Book o1, Book o2) {
//                if(o1.getPrice()>o2.getPrice())
//                    return -1;
//                else if(o1.getPrice(){
//            if(o1.getPrice()>o2.getPrice())
//                return -1;
//            else if(o1.getPrice() o2.getIsbn().compareTo(o1.getIsbn()));


        //根据价格降序排,如果价格一样的话,按照编号继续降序排
        bookList.sort((o1,o2)->{
            if(o1.getPrice()>o2.getPrice())
                return -1;
            else if(o1.getPrice() 

可比较接口

排序的对象对应的实体类实现java.lang.Comparable接口

package stu.aistar.day11.compares;

										
//implements Comparable   特别是里面的泛型需要自己定义
public class Teacher implements Comparable{
    private int id;

    private String name;

    private int age;

    public Teacher() {
    }

    public Teacher(int id, String name, int age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    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 String toString() {
        final StringBuilder sb = new StringBuilder("Teacher{");
        sb.append("id=").append(id);
        sb.append(", name='").append(name).append(''');
        sb.append(", age=").append(age);
        sb.append('}');
        return sb.toString();
    }

    @Override
    public int compareTo(Teacher o) {
        //定制排序的规则
        return o.age - this.age;
    }
}

package stu.aistar.day11.compares;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class TestTeacherSort {
    public static void main(String[] args) {
        Teacher t1 = new Teacher(1,"tom",23);
        Teacher t2 = new Teacher(2,"jack",25);
        Teacher t3 = new Teacher(3,"james",18);
        Teacher t4 = new Teacher(4,"rose",17);

        List list = new ArrayList<>();
        list.add(t1);
        list.add(t2);
        list.add(t3);
        list.add(t4);

		//for (Teacher teacher : list) { 	//为了查看排序之前
		//	  System.out.println(teacher);
		//}

        Collections.sort(list);				//调用可比较接口

        for (Teacher teacher : list) {
            System.out.println(teacher);
        }
    }
}

Collections

java.util.Collections[C] - 集合工具类

面试题 - Collection和Collections有什么区别?

1. static void sort(List list, Comparator c)
   根据指定的比较器引起的顺序对指定的列表进行排序。

   Collections.sort(bookList,((o1, o2) -> (int) (o2.getPrice()-o1.getPrice())));
   Collections.sort() //有两种方法  这是第一种
   

2. static > void sort(List list) ; //集合中的对象必须要实现java.lang.Comparable可比较接口 - 第二种

HashSet

Set[I]接口下的实现类 - 存储的数据是无序不可重复复的.

添加数据到容器的原理:

1. 当把对象添加到容器中之前,会调用对象的hashCode方法,得到一个哈希值.
2. 如果这个哈希值在这之前没有出现过,说明这个位置没有被占用,那么就可以直接将这个对象放入到这个容器中的这个位置
3. 如果这个哈希值在这之前出现过了.产生了哈希碰撞或者哈希冲突.但是这个时候,还不能确定哈希碰撞的俩个对象是同一个对象
4. 继续调用对象的equals方法,如果返回true,说明是同一个对象.则拒绝添加.

底层数据结构

1. 散列表
2. 桶数组 + 链表 + 红黑树

查看HashSet源码

Set sets = new HashSet<>();

public HashSet() {
//HashSet的底层是HashMap
map = new HashMap<>();
}

HashSet的add方法的底层

private static final Object PRESENT = new Object();

//此处的e是添加到容器中的对象
public boolean add(E e) {
//实际上还是在调用map的put方法
//HashSet中添加的对象是作为了Map集合的key
//Map的key具有什么特点 = HashSet中的数据有何特点.
return map.put(e, PRESENT)==null;
}