网易云音乐
java集合底层原理探析
OOP
- 面向对象：
- 封装
- 继承
- 多态
集合接口继承体系概述
- ArrayList ： 是数组结构。 适合查询
- LinkedList ： 是链表结构。 适合增删
- 集合体系图
- 概述：
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类，来作为 链表上下结构存储的 媒介。
- 链表底层存储的是对象。对象中有 上一个索引的对象， 和 下一个 索引的对象。一链 接着 一链。
-
手写代码：
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算法
通过此代码 ， 将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和桶下标，然后把桶下标发生改变的元素迁移到新的位置 - 运行流程：
