集合

集合层次结构：

List

List接口下有两个实现类

ArrayList

和

LinkedList

，其中都实现了List中的方法，并且都给出了可

以存储数据的空间。

特点：

有序可重复

新增内容 : 新增了一些根据索引操作的方法

泛型 :

增强程序的稳定性与可读性

强制检测数据的类型

使用：在类型的后面添加

<类型>

List<String> list = new ArrayList<>();
//规定当前集合对象中存储的所有数据的类型为String

List遍历

1、普通for循环

利用List元素有索引下标的特点，依次获取每一个元素

for (int i=0; i<list.size(); i++){ 
	System.out.println(list.get(i)); 
}

2、增强for循环

依次获取集合中每一个元素存入一个临时变量中

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

3、迭代器

Iterator

所有实现了Collection接口的容器类都有一个iterator方法用以返回一个实现了Iterator接口的对

象

boolean hasNext(); //判断是否有元素没有被遍历

Object next(); //返回游标当前位置的元素并将游标移动到下一个位置

void remove(); //删除游标左面的元素，在执行完next之后该 ,操作只能执行一次

Iterator<String> it = list.iterator(); 
while(it.hasNext()){ 
	System.out.println(it.next()); 
}

List 方法

List 的实现类也可以使用这些方法

注意：

当使用of(E… elements) 返回List后进行修改操作会出现

UnsupportedOperationException

运算操作不支持异常

ArrayList

ArrayList是

List接口的实现类

，特点依然是

有序、可重复

底层结构：可变数组

优点：根据索引查询效率高,访问速度快

缺点：增删涉及到数组的拷贝问题等效率较低

应用场景：

大量做查询,少量做增删的情况下适合使用ArrayList存储数据

扩容：

初始容量为10，扩容机制->

int newCapacity = oldCapacity + (oldCapacity >> 1);


每次扩容原容量的1.5倍,利用

Arrays.copyOf

实现扩容

新增方法：

void forEach(Consumer<? super E> action) 

对 Iterable每个元素执行给定操作，直到处理 Iterable所有元素或操作引发异常。

list.forEach(System.out::println);

ArrayList<String> list = new ArrayList<>();

LinkedList

LinkedList也是

List接口的实现类

，特点依然是

有序、可重复

底层结构：双向链表

优点：做查询效率较低

缺点：做增删效率较高

应用场景：大量做增删少量做查询推荐使用LinkedList

新增功能：新增了一些可以操作链表头尾的方法

链表：以节点为单位，分为单向链表和双向链表

单向链表：由数据Data和下一个节点地址组成，关注链表头节点

双向链表：由上一个节点地址、数据Data和下一个节点地址组成，关注链表头与链表尾节点

链表结构中不存在索引但是可以假设有索引

链表结构特点:

做查询效率较低

做增删效率较高

LinkedList<String> list = new LinkedList<>();

自定义LinkedList容器：以节点为单位

public class MyLinkedList {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.add("zhangsan");
        System.out.println(list.size);
        list.add("lisi");
        System.out.println(list.size);
        System.out.println(list);
    }
}
//定义类
class MyLinkedList{
    //链表头节点
    private Node head;
    //集合中存储数据的个数
    int size;

    public MyLinkedList() {}
    /**
     * 添加数据的方法
     * @param value 要添加的数据
     */
    public void add(Object value) {
        //创建新节点
        Node newNode = new Node(value,null);
        //判断是否为链表头节点
        if(head==null && size==0){
            head = newNode;
            //size++
            size++;
            return;
        }
        //原链表中存在数据:
        //遍历原链表,找到最后一个节点,新节点挂上去
        //创建临时变量 : 永远指向判断的新节点
        Node temp = head;
        while(true){
            //死循环结束的条件 当temp指向最后一个节点结束
            if(temp.getNext()==null){
                break;
            }
            //temp引用指向下一个新节点
            temp = temp.getNext();
        }
        //temp指向原链表的最后一个节点,新节点挂上去
        temp.setNext(newNode);
        //size++
        size++;
    }

    //size()  返回集合中的数据个数
    public int size(){
        return this.size;
    }
	//重写toString()方法
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        //遍历链表中的每一个节点,获取到每一个节点的data属性值,拼接到sb中
        Node temp = head;

        while(temp != null){
            //当钱节点的值拼接到sb中
            sb.append(temp.getData()+", ");
            //temp执行新节点
            temp = temp.getNext();
        }
        //结束的 ]
        sb.delete(sb.length()-2,sb.length());
        sb.append("]");
        return sb.toString();
    }
}

//节点类型
class Node{
    //存储数据
    private Object data;
    //记录下一个节点的地址
    private Node next;

    public Node() {}
    public Node(Object data, Node next) {
        this.data = data;
        this.next = next;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        return Objects.equals(data, node.data) &&
                Objects.equals(next, node.next);
    }
}

Set

Set 接口下有一个

HashSet

实现类，HashSet的底层是用 HashMap 实现的，查询效率高。由于采用Hashcode算法直接确定元素的内存地址，增删效率也高。

HashSet 接口中的元素特点：

无序不可重复

（

去重

），不包含重复元素，最多包含一个 null，元素没有顺序 。

去重：两个数据调用equals方法返回值true,相同需要去重,false不同可以添加

Set<Integer> set = new HashSet<>();
set.add(12345);
set.add(12345);
set.add(12345);
System.out.println(set);
//[2345]

无序：存放的顺序与内部真实存储的顺序不一致(内部与自己存储的规则)

Set<Integer> set = new HashSet<>();
set.add(14);
set.add(88);
set.add(65);
set.add(94);
set.add(26);
set.add(72);
System.out.println(set);
//[65, 88, 72, 26, 14, 94]

新增方法:

Set<E> of(E... elements)

返回包含任意数量元素的不可修改集。

Set<Integer> set = Set.of(1,5,7,2,9,7,6,8);
System.out.println(set);
//抛出异常：IllegalArgumentException，数据不可重复

Set遍历

1、for…each

for (Object obj:set) {
	System.out.println(obj);
}

2、迭代器

Iterator it = set.iterator();
while (it.hasNext()){
    System.out.println(it.next());
}

HashSet

HashSet是Set接口的实现类。

底层结构 :

哈希表

(数组+链表+红黑树) ->是由HashMap维护

优点 : 查询,增删效率较高

缺点 : 无序

应用场景 : 实现不存储相同数据,查询,增删效率较高的时候建议使用HashSet

新增功能 : 无新增功能

去重 : 需要在存储数据的类型中

重写hashcode与equals方法

实现数据的去重

HashSet<Integer> hash = new HashSet<>();
hash.add(23);
hash.add(10);
hash.add(67);
hash.add(55);
hash.add(55);
hash.add(23);
System.out.println(hash);
//[67, 23, 55, 10]   

哈希表 (数组+链表+红黑树)

储存数据的步骤：

1、数据hashcode() –>得到一个int类型的返回值hashcode()

默认根据对象的地址通过hash指定的算法计算出来的int整数

2、把第一步得到的整数通过一个指定hash算法计算位桶的索引

哈希算法:不同的jdk版本不尽相同->尽量散列的分布在每一个位桶中

3、确定了位桶的索引之后,找到对应的位桶

如果桶中链表中没有节点数据,当前数据直接以节点为单位存储在链表中作为链表头

如果存在节点数据,遍历链表,那当前要存放的数据与已有的节点数据比较是否相等

调用equals方法比较true代表相等,false表示不相等

相等不存放则继续遍历,所有数据都不相等,就存在链表的最后

红黑树：

当链表长度>8 并且数组的总长度>64 的时候，会把链表变成红黑树

规律：

前提：重写hashcode与equals方法,让根据成员变量的值去计算非地址

equals相等,hashcode结果一定相等

hashcode结果一样,equals不一定相等