集合

1. 接口继承关系和实现

集合类存放于Java.util包中,主要有3种:set(集)、list(列表包含Queue)和map(映射)

  1. Collection:Collection是集合List、Set、Queue的基本的接口。
  2. Iterator:迭代器,可以通过迭代器遍历集合中的数据
  3. Map:是映射表的基础接口

image-20200723000014517

2.List

  • Java的List是非常常用的数据类型。

  • List是有序的Collection。

  • Java List一共三个实现类: 分别是ArrayList、Vector和LinkedList。

2.1ArrayList

ArrayList 是常用的 List 实现类,内部的具体实现是数组,所以允许对元素快速随机的访问。缺点是内部不能有间隔。

当数组大小不满足时需要增加存储能力,就要将已经有数 组的数据复制到新的存储空间中。当从 ArrayList 的中间位置插入或者删除元素时,需要对数组进 行复制、移动、代价比较高。

因此,它适合随机查找和遍历

不适合插入和删除。

2.2Vector

Vector与ArrayList一样,也是通过数组实现的

不同的是它支持线程的同步,即某一时刻只有一 个线程能够写 Vector

但实现同步需要很高的花费,因此, 访问它比访问ArrayList慢。

2.3 LinkList

LinkedList是用链表结构存储数据的,很适合数据的动态插入和删除

随机访问和遍历速度比较慢.

另外,他还提供了List接口中没有定义的方法,专门用于操作表头和表尾元素,可以当作堆、栈、队列和双向队列使用。

3.Set

Set注重独一无二的性质,该体系集合用于存储无序(存入和取出的顺序不一定相同)元素,值不能重复

对象的相等性本质是对象hashCode值(java是依据对象的内存地址计算出的此序号)判断 的

如果想要让两个不同的对象视为相等的,就必须覆盖Object的hashCode方法和equals方法

3.1HashSet(Hash表)

  • 它存储唯一元素并允许空值
  • 底层数据结构是哈希表
  • 它由HashMap支持
  • 它不保持插入顺序
  • 它不是线程安全的
  • HashSet通过hashCode值来确定元素在内存中的位置。
  • 一个hashCode位置上可以存放多个元 素。

哈希表边存放的是哈希值

HashSet首先判断两个元素的哈希值,如果哈希值一样,接着会比较 equals方法 如果 equlss结果为true ,HashSet就视为同一个元素。如果equals 为false就不是 同一个元素。
哈希值相同equals为false的元素是怎么存储呢,就是在同样的哈希值下顺延(可以认为哈希值相 同的元素放在一个哈希桶中,尽可能避免这种情况)。也就是哈希一样的存一列。如图1表示hashCode值不相同的情 况;图2表示hashCode值相同,但equals不相同的情况。

image-20200723204308243

在此我们可以看见hashcode和equals十分重要,我们要依据这两者对两个对象判断是否重复。

为什么我们不直接用hashcode进行判断呢?

首先,我们得深入的理解一下,什么是hashcode

什么是hash码值?
在java中存在一种hash表结构,它通过一个算法,计算出的结果就是hash码值;这个算法叫hash算法;

hash算法是怎么计算的呢?
是通过对象中的成员来计算出来的结果;
如果成员变量是基本数据类型的值, 那么用这个值 直接参与计算;
如果成员变量是引用数据类型的值,那么获取到这个成员变量的哈希码值后,再参数计算

hash算出来的值有可能重复吗?

hashCode是所有java对象的固有方法,如果不重载的话,返回的实际上是该对象在jvm的堆上的内存地址,而不同对象的内存地址肯定不同,所以这个hashCode也就肯定不同了。如果重载了的话,由于采用的算法的问题,有可能导致两个不同对象的hashCode相同

因此我们知道了,如果两个重载了hashcode的对象,hashcode是有可能重复的,

当重复的时候就需要我们引用equalse方法了

hashcode重复后的equals方法

public boolean equals(Object obj) {
    if (this == obj)     //先判断传入的对象地址是否和当前对象一样
      return true;     //如果一样的话,肯定为同一对象,直接返回true
    if (obj == null)       //如果传入的对象为空的话
      return false; //则直接返回false,添加到集合中,因为Set可以存null值
    if (getClass() != obj.getClass())//然后判断字节码文件的对象
      return false;//不相等的话说明两个元素肯定不同,就直接返回false
    Student other = (Student) 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;
}

3.2TreeSet(二叉树)

  • TreeSet的底层是二叉树
  • 它存放同一类型的数据

  • TreeSet 可以保存对象元素的唯一性(并不是一定保证唯一性,需要根据重写的compaaTo方法来确定)

  • TreeSet()是使用二叉树的原理对新add()的对象按照指定的顺序排序(升序、降序),每增 加一个对象都会进行排序,将对象插入的二叉树指定的位置。

  • Integer和String对象都可以进行默认的TreeSet排序,而自定义类的对象是不可以的,自 己定义的类必须实现Comparable接口,并且覆写相应的compareTo()函数,才可以正常使用.

  • 在覆写compare()函数时,要返回相应的值才能使TreeSet按照一定的规则来排序

  • 比较此对象与指定对象的顺序。如果该对象小于、等于或大于指定对象,则分别返回负整数、零或正整数。

class HeapSortUtil {
    void heapify(int tree[], int n,int i) {
        //1.规定n为整个数组节点的数量
        //2. 计算出i节点的两个子节点
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        //3. 默认在这个树中最大的是输入的i节点
        int maxPos = i;

        //4. 如果左节点没有到达极限,同时左节点的数比父节点i还大,那么最大的节点就是左节点
        if (c1 < n && tree[c1] > tree[maxPos])
            maxPos = c1;

        //5. 如果右节点没有到达极限,同时右节点的数比左节点和右节点都大,那么最大的节点就是右节点
        if (c2 < n && tree[c2] > tree[maxPos])
            maxPos = c2;

        //6. 如果最大的节点不是自身,那么就交换最大节点和父节点的数据
        //7. 同时进行递归,继续把最大节点当作父节点向下递归,如果其子节点不存在,则不会触发if判断,递归结束
        if (maxPos != i) {
            int temp;
            temp = tree[maxPos];
            tree[maxPos] = tree[i];
            tree[i] = temp;
            heapify(tree,n,maxPos);
        }

    }

    void build_heap(int tree[]) {
        //1. 构建堆需要从下往上开始,如不然则会发生下面堆的数据大于上面,上浮后却没有替换的情况,例如小根堆进行构建为大根堆
        int n = tree.length;
        int lastNode = n - 1;
        //2. 最后一个父节点为最后一个子节点-1除以2
        int lastParent = (lastNode - 1) / 2;

        //3.只要这一条支路进行了heapify就一直递归至这条路最后一个父节点为止
        for (int i = lastParent; i >= 0; i--) {
            heapify(tree,n,i);
        }
    }

    void heapSort(int tree[]) {
        int n = tree.length;
        build_heap(tree);

        //不得不将heapify函数写了一个n参数,因为每一次进行排序,都要把最后一位和第一位做互换,相当于减少堆的数量
        for (int i = n - 1; i >= 0; i--) {
            int temp;
            temp = tree[0];
            tree[0] = tree[i];
            tree[i] = temp;

            //每次只需要在首位进行heapify就可以了,因为之前构建的时候已经是堆了
            heapify(tree,i,0);

        }
    }
}

醉后不知天在水,满船清梦压星河