Weixl 的个人博客

贼拉正经的个人博客

  menu
22 文章
0 浏览
1 当前访客
ღゝ◡╹)ノ❤️

java集合

java集合底层原理探析

OOP

  • 面向对象:
    • 封装
    • 继承
    • 多态

集合接口继承体系概述

  • ArrayList : 是数组结构。 适合查询
  • LinkedList : 是链表结构。 适合增删
  • 集合体系图

1

  • 概述:
    collection接口 : 里面只放抽象反复噶,用来定义规范,所有的子类都能使用的 共性 规范
    List , Set , Map 接口 : 继承collection接口方法,用来增加自己所需求的个性规范,
    
    普通ArrayList,LinkedList。 实现类。 实现了 List抽象类
    重写之前继承的 所有方法。 并且加入 具体的行为。
    

List集合

  • List集合代表一个元素 是有序的且可以重复的集合。集合中每个元素都有其对应的顺序索引。

ArrayList

  • ArrayList 底层就是数组结构。在类初始化时,定义一个 长度为10的数组。进行存值。

  • 如果长度超过 定义的10。 那么就会 通过 cope数组的方式 来增加 数组的长度。

  • 代码:

    package com.czxy.list;
    import org.assertj.core.data.Index;
    
    /**
     * @author 遗憾就遗憾吧
     * @Date 2020/3/23
     * @jdk 1.8
     *
     * 手写实现的 ArrayList集合
     */
    public class MyArrayList {
    
        //ArrayList 需要两个 参数
    
        private int size = 0;
    
        private Object[] data;
    
        public MyArrayList() {
            //初始长度为10
            data = new Object[10];
        }
    
        /*
        * 进行存储
        * */
        public boolean add(Object obj){
            //判断长度 数据个数  是否 大于等于 数组的长度了
            if (size >= data.length){
                //进行cope 一个新的数组,宽容 1.5
                Object[] tmp = new Object[data.length * 2];
                //进行cope
                //参数src:源数组 , dest:目的数组 , srcPos: 源数组要复制的起始位置 , destPos: 目标数组的起始位置 , length:复制长度
                System.arraycopy(data , 0 , tmp , 0 , size);
                //然后将 扩容后的 数组 赋值到 data中
                data = tmp;
            }
            //进行数据的添加
            data[size++] = obj;
            return true;
        }
    
        public Object get(int index){
            return data[index];
        }
    }
    
  • ArrayList删除:

    //官方代码
        public E remove(int index) {
            //判断当前传递的索引,是不是大于 集合总长度
            rangeCheck(index);
            
        //d当前要删除的数据是什么,等下返回
        E oldValue = elementData(index);
    
        //判断从要删除的索引开始,往后还有几个索引
        int numMoved = size - index - 1;
        //如果往后的索引 > 0 表示当前不是最后一个索引
        if (numMoved > 0)
            //当前数组从删除索引+1开始,cope一份,覆盖当前数组。而最后一个数据 会 有两份
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将最后一个索引数据 赋值 null, 总会执行
        elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }
    



LinkedList

  • LinkedList , 底层是 链表结构。
  • 在LinkedList 中需要引用 一个 node类,来作为 链表上下结构存储的 媒介。
  • 链表底层存储的是对象。对象中有 上一个索引的对象, 和 下一个 索引的对象。一链 接着 一链。

2

  • 手写代码:

    package com.czxy.list;
    /**
     * @author 遗憾就遗憾吧
     * @Date 2020/3/23
     * @jdk 1.8
     *
     * 手动书写一个 LinkedList 集合类
     */
    public class MyLinkedList {
    
        /*
        * 三个属性: LinkedList作为 链表形式的储存。并没有一个数组来作为存储的媒介。而是通过,node对象中,包含另一个node对象,来作为
        * 上下的链接
        */
    
        //LinkedList的总长度
        private int size = 0;
    
        //链表中 第一个 node对象值
        private Node first;
    
        //链表中 最后一个node对象值
        private Node last;
    
        //添加数据
        public boolean add(Object obj){
            //先创建一个 node对象
            Node node = new Node();
    
            //判断first  链表中的第一个 值是否为空。
            //为空表示当前链表 要存储的是第一个数据
            if (first == null){
                //将 当前要存储的数据 赋值到 node 对象中
                node.setPrev(null);
                node.setNext(null);
                node.setItem(obj);
    
                //赋值到 first last
                this.first = node;
                this.last = node;
            }else {
                //否则表示,当前链表中 已经有了数据
                // 因为last就是之前 链表中的最后一个
                node.setItem(obj);
                node.setPrev(last);
                node.setNext(null);
    
                //last 之前 链表的最后一个 存储为当前的node
                last.setNext(node);
    
                //重新赋值 last
                this.last = node;
            }
    
            this.size++;
            return true;
        }
    
        /*
        * 查询方法,通过 index 查询对应的数据
        * */
        public Object get(int index){
            //判断查询的 索引。
            //如果index 查询的索引 <= 0 , 就查询第一个数据
            if (index <= 0){
                //返回 first 中node的数据
                return first.getItem();
            }else{
                //否则 查询肯定是 链表 结构中的某一个数据
                //通过 size 和 index 的比较循环查询 出 node数据
                Node node = null;
    
                //将 size-1 得出 集合中 所有的索引长度。 如果大于 你要查找的索引就一个循环。 不能大于等于。 要在链表 中后一位数据上 prev得出上一个链表的数据
                for (int i = size - 1  ; i > index  ; i--){
                    node = this.last.prev;
                }
                return node.getItem();
            }
        }
    
        /*
        * 创建一个内部类,用于 链表的 存储媒介
        * */
        private class Node{
            //存储的数据值
            Object item;
    
            //链表上一个 node对象
            Node prev;
    
            //链表的下一个node对象
            Node next;
    
            public Node() {
            }
    
            //一个node带参的构造方法
            public Node(Node prev , Object item , Node next){
                this.item = item;
                this.prev = prev;
                this.next = next;
            }
    
            public Object getItem() {
                return item;
            }
    
            public void setItem(Object item) {
                this.item = item;
            }
    
            public Node getPrev() {
                return prev;
            }
    
            public void setPrev(Node prev) {
                this.prev = prev;
            }
    
            public Node getNext() {
                return next;
            }
    
            public void setNext(Node next) {
                this.next = next;
            }
        }
    }
    



HashMap源码分析

  • HashMap 是 数组+单向链表+红黑树 的形式。
  • jdk1.7是数组+链表。
  • 查看源代码:说明各个参数:
    // 初始化的 数组长度
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    //最大数组容量
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
    //负载因子。 默认的16 * 0.75= 12 , 当使用数组格子到达12的时候,就会进行扩容
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 桶的树化阈值,单向列表 的最大长度 , 当达到最大长度8时,就会转为红黑树
    static final int TREEIFY_THRESHOLD = 8;
    
    //当红黑树的长度小于6则需要转成链表
    static final int UNTREEIFY_THRESHOLD = 6;
    
    //存储的数组
    transient Node<K,V>[] table;
    
  • Hash算法3
    通过此代码 , 将key.hashcode值,进行一个位移运算。
    高16位和低16位,进行一个异或运算。 
    为了分散 hash值。 使结果hash值,尽最大可能不相同。
    从而充分利用数组的每一个位置。
    
    (h = key.hashCode()) ^ (h >>> 16) 解释: 
    ^用作二进制异或:列如

    10101010
    11110001
    --------
    01011011   相同为0  不同为1
  • hash算法概述: 先通过一个 hash函数,将key的hashcode值,进行一个位移运算,高16位和低16位的异或运算。 然后通过 n-1 & 刚计算出的hash值,进行 得出数组的下标。
  • map.put() 中 的putVal方法中:
        final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            //定义局部变量,为后面进行操作
            // tab为 桶数组
            // p 为数组中某一个格子 第一位
            // n 为数组长度
            Node<K,V>[] tab; Node<K,V> p; int n, i;

            //用来  当前的map集合中是否为空,为空就进行 初始化 数组操作
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length; //n数组的总长度

            //tab[i = (n - 1) & hash]是为了计算出 桶中存储当前元素的下标索引。
            // n-1 是为了 获取最大索引下标 , 模hash值,就得出下标
            //判断数组中当前下标 是否为null , 为null就添加
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);

            //否则不为null
            else {
                //局部变量
                Node<K,V> e; K k;

                //有三种情况:
                1. 数据存储在 数组的索引中,在链表的头一个
                2. 存储在 链表中
                3. 存储在 红黑树中

                //判断当前 数组索引下 的 key是否与 添加的key相同。,相同就替换。
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;

                //判断当前 p 是否为 红黑树, 是红黑树就往下进行一个插入的操作。
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

                //在链表中操作
                else {
          
                    //一个 死循环,因为 要判断 当前key已经存在的情况,
                    for (int binCount = 0; ; ++binCount) {

                        //如果当前 p 桶格子(但不是格子) 起始 。的数据一直 next判断。如果下一个 为null表示有位置可以放。
                        if ((e = p.next) == null) {
                            p.next = newNode(hash, key, value, null);
                          
                            //判断添加完后,长度是不是达到了8,要进行转为 红黑树
                            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;
                      
                        //以上两部都不满足,就赋值p 为 e,继续循环下一步。
                        p = e;
                    }
                }

                //通过标记的 e 来判断不为 null,表示key是重复的,就替换
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;

            //判断添加当前元素时,数组长度时候会超出 当前的 扩容临界点。超出了就调用 resize进行 扩容。
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
  • 扩容resize
    扩容的 数量必须是 2的n次幂。保证 分散性
    数组大小必须是2的n次幂,是为了 二进制时 是 100000000 那么-1,就会得到01111111111,才是最大值
    //扩容只会 数据的改变
    
    当数组 桶进行扩容后,重新计算hashcode和桶下标,然后把桶下标发生改变的元素迁移到新的位置
    
  • 运行流程:

5


标题:java集合
作者:Weixl
地址:http://loveless.top/articles/2020/10/08/1602155542452.html