首页 > 其他分享 >集合原理

集合原理

时间:2023-03-20 20:57:57浏览次数:42  
标签:node index int item length 集合 原理 public

集合原理

一、List的执行原理

要解决的痛点:

1.数组的目前唯一的数据批量存储的手段

2.数组的扩容效率极慢(必须要解决的问题)

解决痛点问题:

1.暂时没有其他策略之前,先丰富其功能

2.如果每扩容一次都需要消耗大量的时间,可以减少其扩容的次数;通过牺牲空间,将扩容所消耗的时间集中在某几个特定的时间节点

确定需求主体

package com.mine.demo01;

public interface List {

    /**
     * 添加元素
     * @param item
     */
    public void add(Object item);


    /**
     * 获取集合长度
     * @return
     */
    public int size();

    /**
     * 获取元素当前位置
     * @param item
     * @return
     */
    public int indexOf(Object item);


    /**
     * 获取元素最后所在位置
     * @param item
     * @return
     */
    public int lastIndexOf(Object item);


    /**
     * 根据游标获取元素
     * @param index
     * @return
     */
    public Object get(int index);

    /**
     * 根据游标修改元素
     * @param index
     */
    public void set(int index,Object item);


    /**
     * 根据游标删除某个元素
     * @param index
     */
    public void remove(int index);
}

二、ArrayList的实现

扩容策略:

1.默认空间长度为10

2.数据长度和空间长度分开治理

3.每次需要扩容的时候,扩容的长度为原本长度的一半

优势:

因为是基于数组,所以检索效率极高

劣势:

1.因为空间换时间,所以在特定节点上,依然存在扩容的时间大量消耗。同时,空间的浪费是不可避
免。增减效率在特定节点上不高。
2.空间有限

1.初始化默认长度

 //1.初始化默认长度
    private Object[] items;

    //默认集合初始长度
    public static final int DEFAULT_VALUE_LENGTH = 10;

    //最大扩容长度
    public static final int MAX_VALUE_LENGTH = Integer.MAX_VALUE - 8;

    public Scanner scanner;
    

    //初始化
    public ArrayList(){
        this(DEFAULT_VALUE_LENGTH);
    }


    public ArrayList(int defaultLength){
        this.items = new Object[defaultLength];
    }

2.初始化游标

private int length = 0; //初始的集合元素个数

3.判断游标是否存在越界

 //3.判断游标是否越界
    public boolean checkIndexBorder(int index){
        int maxIndex = this.length - 1;
        if(index < 0 || index > maxIndex){
            throw new RuntimeException("游标越界:"+ index);
        }
        return true;
    }

4.空间扩容

 //4.空间扩容
    public void spaceExpansion(){
        int nowLength = this.items.length;//当前元素个数
        int newLength = nowLength + (nowLength >> 1);//要扩容后的新的数组个数,>>为除2
        //扩容的上限
        if(newLength > MAX_VALUE_LENGTH){
            newLength = MAX_VALUE_LENGTH;
        }
        Object[] newItems = new Object[newLength];//新的数组
        System.arraycopy(this.items,0,newItems,0,nowLength);//将旧数组的元素移到新数组
        this.items = newItems;//把新的数组,赋值给旧的数组
    }



    public void spaceExpansion2(){//另一种写法
        int nowLength = this.items.length;//当前元素个数
        int newLength = nowLength + (nowLength >> 1);//要扩容后的新的数组个数,>>为除2
        //扩容的上限
        if(newLength > MAX_VALUE_LENGTH){
            newLength = MAX_VALUE_LENGTH;
        }
       this.items = Arrays.copyOf(this.items,newLength);

    }

5.添加元素

判断是否要扩容的依据是数据长度小于空间长度,如果数据长度等于空间长度,说明要先扩容,再加数据

//5.添加元素
    @Override
    public void add(Object item) {
        //判断集合是否满了
        if(this.length == MAX_VALUE_LENGTH){
            throw new RuntimeException("集合已满!");
        }
        //判断要不要扩容
        if(this.length == this.items.length){
            this.spaceExpansion();//扩容
        }

        //往末尾添加元素
        this.items[this.length] = item;
        this.length++;//数据长度迭代
    }

5.元素的长度和获取

//6.元素的长度和获取
    @Override
    public int size() {
        return this.length;
    }

6.ArrayList.java

package com.mine.demo01;

import java.util.Arrays;
import java.util.Scanner;

public class ArrayList implements List{

    //1.初始化默认长度
    private Object[] items;

    //默认集合初始长度
    public static final int DEFAULT_VALUE_LENGTH = 10;

    //最大扩容长度
    public static final int MAX_VALUE_LENGTH = Integer.MAX_VALUE - 8;

    public Scanner scanner;


    //初始化
    public ArrayList(){
        this(DEFAULT_VALUE_LENGTH);
    }


    public ArrayList(int defaultLength){
        this.items = new Object[defaultLength];
    }


    //2.初始化游标
    private int length = 0;//初始的集合元素个数

    //3.判断游标是否越界
    public boolean checkIndexBorder(int index){
        int maxIndex = this.length - 1;
        if(index < 0 || index > maxIndex){
            throw new RuntimeException("游标越界:"+ index);
        }
        return true;
    }

    //4.空间扩容
    public void spaceExpansion(){
        int nowLength = this.items.length;//当前元素个数
        int newLength = nowLength + (nowLength >> 1);//要扩容后的新的数组个数,>>为除2
        //扩容的上限
        if(newLength > MAX_VALUE_LENGTH){
            newLength = MAX_VALUE_LENGTH;
        }
        Object[] newItems = new Object[newLength];//新的数组
        System.arraycopy(this.items,0,newItems,0,nowLength);//将旧数组的元素移到新数组
        this.items = newItems;//把新的数组,赋值给旧的数组
    }



    public void spaceExpansion2(){//另一种写法
        int nowLength = this.items.length;//当前元素个数
        int newLength = nowLength + (nowLength >> 1);//要扩容后的新的数组个数,>>为除2
        //扩容的上限
        if(newLength > MAX_VALUE_LENGTH){
            newLength = MAX_VALUE_LENGTH;
        }
       this.items = Arrays.copyOf(this.items,newLength);

    }

    //5.添加元素
    @Override
    public void add(Object item) {
        //判断集合是否满了
        if(this.length == MAX_VALUE_LENGTH){
            throw new RuntimeException("集合已满!");
        }
        //判断要不要扩容
        if(this.length == this.items.length){
            this.spaceExpansion();//扩容
        }

        //往末尾添加元素
        this.items[this.length] = item;
        this.length++;//数据长度迭代
    }


    //6.元素的长度和获取
    @Override
    public int size() {
        return this.length;
    }

    @Override
    public int indexOf(Object item) {
        for(int i = 0 ; i < this.length ; i ++){
            if(item!=null && item.equals(this.items[i])){
                return i;
            }else if(this.items[i] != null && this.items[i].equals(item)){
                return i;
            }else if(this.items[i] == item){
                return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object item) {
        for(int i = this.length-1 ; i >= 0 ; i --){
            if(item!=null && item.equals(this.items[i])){
                return i;
            }else if(this.items[i] != null && this.items[i].equals(item)){
                return i;
            }else if(this.items[i] == item){
                return i;
            }
        }
        return -1;
    }

    @Override
    public Object get(int index) {
        //验证游标是否越界
        if(this.checkIndexBorder(index)){
            return this.items[index];
        }
        return null;
    }

    @Override
    public void set(int index,Object item) {

        if(this.checkIndexBorder(index)){

            this.items[index] = item;
            System.out.println("修改成功");
        }
    }

    @Override
    public void remove(int index) {
        if(this.checkIndexBorder(index)){
            Object[] newItems = new Object[this.items.length];
//            for(int i = 0;i < index;i++){
//                newItems[i] = this.items[i];
//            }
//            for(int i = index +1 ;i < this.items.length-1;i++){
//                newItems[i] = this.items[i];
//            }
//                this.items = newItems;
            System.arraycopy(this.items,0,newItems,0,index);
            System.arraycopy(this.items,index+1,newItems,index,this.length-index-1);
        }
        System.out.println(Arrays.toString(this.items));

    }
    public void checkItem(Object item){
        int index = -1;
        for(int i = 0;i < this.length; i++){
            if(this.items[i].equals(item)){
                index = i;
                break;
            }
        }
        System.out.println("游标是:"+index);
    }
}

三、链表的运用和开发:LinkedList

1.什么是双向链表

运用指针原理,在java当中即对象的内存地址。让对象和对象之间能够相互寻找前一位或者后一位

存在的意义:和ArrayList的性能进行互补

优势:增减元素效率极高

缺点:随机遍历效率不高,每次都要从头找

1.单个元素(节点)的设计:Node

//一个内部类
 public class Node {
        Node proe;//前一位(属性)
        Object item;//真正保存集合元素的属性
        Node next;//下一位(属性)
    }

2.开始和结束的位置

//开始的位置
private Node first;
//结束的位置
private Node last;
//元素的个数
private int length;

3.添加首尾元素

  public void addFirst(Object obj){
            Node node = new Node();
            node.item = obj; //要添加的元素
            if(this.first == null){//假定为第一次添加
                this.first = node;
                this.last = node;

            }else {
                node.next = this.first; //现在的首位,变成新建节点的下一位
                this.first.proe = node;//现在首位的上一位变成新建节点
                this.first = node; //现在的首位变成新建节点
            }
            this.length++;//元素长度迭代

        }
        public void addLast(Object obj){
            Node  node = new Node();
            node.item = obj; //要添加的元素
            if(this.last == null){
                this.first = null;
                this.last = null;
            }else {
                node.proe = this.last;
                node.proe.next = node;
                this.last = node;
            }
            this.length++;
        }

4.链表的遍历取值

 public Object get(int index) {
       //判断游标是否越界
        if(this.checkIndexBorder(index)){
            int i = 0;
            Node node = this.first;
            while (node.next != null & i < index){
                node = node.next;
                i++;
            }
            //循环结束,保存是是要检索的值
            return node.item;
        }
        return null;
    }

5.修改

 public void set(int index, Object item) {
            //判断游标是否越界
        if(this.checkIndexBorder(index)){
            int i = 0;
            Node node = this.first;
            while (node.next != null && i < index){
                node = node.next;
                i++;
            }
            node.item = item;
        }
    }

6.获取首位的元素和删除首位元素

  public Object getFirst(){
            return this.first.item;
        }
        public Object getLast(){
            return this.last.item;
        }


        public void removeFirst(){
            //找到第二个
            Node sen = this.first.next;
            //将第二个的上一个位置置空
            sen.proe = null;
            //将first指向第二个位置
            this.first = sen;
            //修改长度
            this.length--;

        }


        public void removeLast(){
            //找到倒数第二个
            Node sen = this.last.proe;
            //将倒数第二个的下一个位置置空
            sen.next = null;
            //将last指向倒数第二个
            this.last = sen;
            //修改长度
            this.length--;

        }

7.LinkedList.java

package com.mine.demo01;

public class LinkedList1 implements List{
    private class Node{
        Node proe;//前一位(属性)

        Object item;//真正保存集合元素的属性

        Node next;//下一位(属性)
    }

    //开始的位置
    private Node first = null;
    //结束的位置
    private Node last = null;
    //元素的个数
    private int length = 0;


    public void addFirst(Object obj){
        Node node = new Node();
        node.item = obj;//要添加的元素
        if(this.first == null){//假定为第一次添加
            this.first = node;
            this.last = node;
        }else{
            node.next = this.first;//现在的首位,变成新建节点的下一位
            this.first.proe = node;//现在首位的上一位变成新建节点
            this.first = node;//现在的首位变成新建节点
        }
        this.length++;//迭代元素长度
    }
    public void addLast(Object obj){
        Node node = new Node();
        node.item = obj;//要添加的元素
        if(this.last == null){//假定为第一次添加
            this.first = node;
            this.last = node;
        }else{
            node.proe = this.last;
            this.last.next = node;
            this.last = node;
        }
        this.length++;//迭代元素长度
    }
    public Object getFirst(){
        return this.first.item;
    }
    public Object getLast(){
        return this.last.item;
    }
    public void removeFirst(){
        if(this.length >= 1){
            //1.找到第二个
            Node sen = this.first.next;
            //2.把第二个的上一位置空
            sen.proe = null;
            //3.把first指向原第二位
            this.first = sen;
            //4.修改长度
            this.length --;
        }
    }
    public void removeLast(){
        if(this.length >= 1){
            //1.找到倒数第二个
            Node sen = this.last.proe;
            //2.把第二个的上一位置空
            sen.next = null;
            //3.把first指向原第二位
            this.last = sen;
            //4.修改长度
            this.length --;
        }
    }
    @Override
    public void add(Object item) {
        this.addLast(item);
    }

    @Override
    public int size() {
        return this.length;
    }

    @Override
    public int indexOf(Object item) {
        int i = 0;
        Node node = this.first;//链表的头,对应的游标为0
        //循环的条件是看当前节点是否有下一位
        while(node.next != null){
            if(item!=null && item.equals(node.item)){
                return i;
            }else if(node.item != null && node.item.equals(item)){
                return i;
            }else if(node.item == item){
                return i;
            }
            node = node.next;
            i ++;
        }
        //如果没找到给-1
        return -1;
    }

    @Override
    public int lastIndexOf(Object item) {
        int i = this.length - 1;
        Node node = this.last;//链表的尾部,对应的游标为length - 1
        //循环的条件是看当前节点是否有上一位
        while(node.proe != null){
            if(item!=null && item.equals(node.item)){
                return i;
            }else if(node.item != null && node.item.equals(item)){
                return i;
            }else if(node.item == item){
                return i;
            }
            node = node.proe;
            i --;
        }
        //如果没找到给-1
        return -1;
    }

    @Override
    public Object get(int index) {
        //验证是否越界
        if(this.checkIndexBorder(index)){
            int i = 0;
            Node node = this.first;//链表的头,对应的游标为0
            //循环的条件是看当前节点是否有下一位
            while(node.next != null && i < index){
                node = node.next;
                i ++;
            }
            //循环结束,保存的是要检索到的节点
            return node.item;
        }
        return null;
    }

    @Override
    public void set(int index, Object item) {
        //验证是否越界
        if(this.checkIndexBorder(index)){
            int i = 0;
            Node node = this.first;//链表的头,对应的游标为0
            //循环的条件是看当前节点是否有下一位
            while(node.next != null && i < index){
                node = node.next;
                i ++;
            }
            //循环到指定位置停止
            node.item = item;
        }
    }

    @Override
    public void remove(int index) {
        //验证是否越界
        if(this.checkIndexBorder(index)){
            int i = 0;
            Node node = this.first;//链表的头,对应的游标为0
            //循环的条件是看当前节点是否有下一位
            while(node.next != null && i < index){
                node = node.next;
                i ++;
            }
            //循环到指定位置停止
            Node p = node.proe;
            Node n = node.next;
            n.proe = p;
            p.next = n;
            //修改长度
            this.length --;
        }
    }

    /**
     * 判断游标是否越界
     */
    private boolean checkIndexBorder(int index){
        int maxIndex = this.length - 1;
        if(index < 0 || index > maxIndex){
            throw new RuntimeException("游标越界:"+index);
        }
        return true;
    }
}

四、泛型开发(了解原理)

标签:node,index,int,item,length,集合,原理,public
From: https://www.cnblogs.com/DFshmily/p/17237729.html

相关文章

  • day6(day5休息) | 1. 两数之和; 202. 快乐数; 242. 有效的字母异位词; 349. 两个数组
    1.两数之和 题目简述 给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个横竖,并返回他们的数组下标。 你可以假设每种输入......
  • 浅谈集合HashSet
    HashSet简介HashSet集合继承于Collection集合,Collection集合的常用方法也在HashSet中同样适用。底层原理:HashSet集合底层采用哈希表存储数据,底层是new了一个HashMap,a......
  • Redis整数集合
    集合键的底层实现之一,当集合只包含整数值元素,且报价函的元素不多时,就会使用整数集合作为集合键的底层实现。intset实现typedefstructintset{ uint32_tencoding;//......
  • 查找手机价格低于3000(返回集合类型)
    packagecom.itheima.test;importjava.util.ArrayList;publicclassTest8{publicstaticvoidmain(String[]args){ArrayList<Phone>list=new......
  • 知识图谱TransD原理
    TransD:"KnowledgeGraphEmbeddingviaDynamicMappingMatrix"(ACL2015)动机:不同类型的实体有不同的属性和作用,如果将全部实体都映射到同一空间,使用同一参数进行传递表......
  • 疯一样的向自己发问 - 剖析lsm 索引原理
    疯一样的向自己发问-剖析lsm索引原理lsm简析lsm更像是一种设计索引的思想。它把数据分为两个部分,一部分放在内存里,一部分是存放在磁盘上,内存里面的数据检索方式可以......
  • PostgreSQL temp table 全链路 实现原理
    文章目录​​背景​​​​使用​​​​实现​​​​创建表​​​​插入​​​​删除表​​背景表(table/relation)作为PostgreSQL数据库中最为常用的一种数据库对象,用户......
  • 小白如何从头理解FDB的运行机制和原理(入门版)
    什么是keyvalue分布式存储   Key-value分布式存储是一种高性能、可伸缩性和容错性强的分布式存储系统,它将数据以键值对的形式存储在分布式系统中的......
  • mybatis返回集合对象包含List<String>
    mybatis返回集合对象包含List<String>时间:2021-07-13本文章向大家介绍mybatis返回集合对象包含List<String>,主要包括mybatis返回集合对象包含List<String>使用实例、应用......
  • redis 操作集合基本操作
    Redis的Set是String类型的无序集合。集合成员是唯一的,这就意味着集合中不能出现重复的数据。集合对象的编码可以是intset或者hashtable。Redis中集合是通过哈......