Java数据结构和集合源码

Java数据结构和集合源码

目录

数据结构概述

概念

研究对象1:数据之间的逻辑关系

研究对象2:数据之间的存储关系

研究对象3:相关的算法操作

开发中常用的存储结构和理解

手写线性表

手写二叉树

常见存储结构之：栈(stack、先进后出、first in last out、FILO、LIFO）

常见存储结构之：队列(queue、先进先出、first in first out、FIFO)

ArrayList在JDK7和JDK8中的源码

ArrayList特点:

ArrayList源码解析：jdk7版本：(以jdk1.7.0_07为例)

ArrayList源码解析：jdk8版本:(以jdk1.8.0_271为例)

小结

vector在JDK8中的源码剖析

Vector特点

Vector源码解析：(以jdk1.8.0_271为例)

LinkedList在JDK8中的源码剖析

LinkedList的特点：

LinkedList在jdk8中的源码解析：

HashMap

HashMap中元素的特点

HashMap在JDK7中的源码剖析

jdk7中创建对象和添加数据过程(以JDK1.7.0_07为例说明)：

1.实例化过程

2. put(key,value)的过程

3. Entry的定义如下：

HashMap在JDK8中的不同之处

HashMap的属性和字段

LinkedHashMap,HashSet,LinkedHashSet源码剖析

LinkedHashMap 与 HashMap 的关系

LinkedHashMap重写了HashMap的如下方法：

底层结构：LinkedHashMap内部定义了一个Entry

HashSet和LinkedHashSet的源码分析

---

码云代码:data_structure

数据结构概述

概念

数据结构就是一种程序设计的优化的方法论,研究数据的逻辑结构和物理结构以及他们之间相互关系,并对这种结构定义为相应的运算,目的是为了加快程序的执行速度,减少内存的占用

研究对象1:数据之间的逻辑关系

集合结构

线性结构:一对一关系

树形结构:一对多关系

图形结构:多对多关系

研究对象2:数据之间的存储关系

顺序结构

链式结构

索引结构

散列结果

研究对象3:相关的算法操作

分配资源,建立结构,释放资源

插入删除

获取遍历

修改排序

开发中常用的存储结构和理解

线性表(一对一关系):一维数组,单向链表,双向链表,栈,队列

树(一对多关系):树,

图(多对多关系)

哈希表:HashMap,HashSet

手写线性表

package list;import org.junit.Test;/*** ClassName: list.Node* Package: PACKAGE_NAME* Description:** @Author TYUST-YHB* @Create 2023/8/3 14:20* @Version 1.0*/
//测试
public class test {//测试单向链表@Testpublic void test1() {Node1 node10 = new Node1("aaa");Node1 node11 = new Node1("bbb");node10.setNext(node11);System.out.Next());}//测试双向链表@Testpublic void test2() {Node2 node10 = new Node2("aaa");Node2 node11 = new Node2("bbb");Node2 node12 = new Node2("ccc");node10.setNext(node11);node11.setNext(node12);node12.setPrev(node11);node11.setPrev(node10);System.out.Next());System.out.Prev());}}
//单向链表
class Node1{private Object data;private Node1 next;public Object getData() {return data;}public void setData(Object data) {this.data = data;}public Node1 getNext() {return next;}public void setNext(Node1 next) { = next;}public Node1(Object data) {this.data = data;}public Node1 getNext(Node1 node){;}@Overridepublic String toString() {return "Node1{" +"data=" + data +'}';}
}
//双向链表
class Node2{private Node2 prev;private Object data;private Node2 next;public void setPrev(Node2 prev) {this.prev = prev;}public Object getData() {return data;}public void setData(Object data) {this.data = data;}public void setNext(Node2 next) { = next;}public Node2(Object data) {this.data = data;}public Node2 getNext( ){;}public Node2 getPrev( ){return this.prev;}@Overridepublic String toString() {return "Node2{" +"data=" + data +'}';}
}

手写二叉树

package Tree;import org.junit.Test;/*** ClassName: TreeNode* Package: Tree* Description:** @Author TYUST-YHB* @Create 2023/8/3 14:37* @Version 1.0*/
public class test {@Testpublic void test() {TreeNode leftNode = new TreeNode(null,"LLL",null);TreeNode rightNode = new TreeNode(null,"RRR",null);TreeNode node1 = new TreeNode(leftNode,"AA",rightNode);System.out.Left());System.out.Right());}
}class TreeNode {private TreeNode left;private Object data;private TreeNode right;public TreeNode(TreeNode left, Object data, TreeNode right) {this.left = left;this.data = data;this.right = right;}public TreeNode(Object data){this.data = data;}public TreeNode getLeft() {return left;}public void setLeft(TreeNode left) {this.left = left;}public Object getData() {return data;}public void setData(Object data) {this.data = data;}public TreeNode getRight() {return right;}public void setRight(TreeNode right) {this.right = right;}@Overridepublic String toString() {return "TreeNode{" +"data=" + data +'}';}
}

常见存储结构之：栈(stack、先进后出、first in last out、FILO、LIFO）

public class test {@Testpublic void test() {Stack stack = new Stack(5);stack.push("aaa");stack.push("bbb");System.out.println(stack.pop());System.out.println(stack.pop());}
}
class Stack{Object[] values;int size;//记录存储的元素的个数public Stack(int length){values = new Object[length];}//入栈public void push(Object ele){if(size >= values.length){throw new RuntimeException("栈空间已满，入栈失败");}values[size] = ele;size++;}//出栈public Object pop(){if(size <= 0){throw new RuntimeException("栈空间已空，出栈失败");}Object obj = values[size - 1];values[size - 1] = null;size--;return obj;}}

常见存储结构之：队列(queue、先进先出、first in first out、FIFO)

package queue;import org.junit.Test;/*** ClassName: test* Package: queue* Description:** @Author TYUST-YHB* @Create 2023/8/3 14:47* @Version 1.0*/
public class test {@Testpublic void test() {Queue queue = new Queue(5);queue.add("aaa");queue.add("bbb");queue.add("ccc");System.out.());System.out.());System.out.());System.out.());}
}
class Queue{Object[] values;int size;//记录存储的元素的个数public Queue(int length){values = new Object[length];}public void add(Object ele){ //添加if(size >= values.length){throw new RuntimeException("Queue full, add failed");}values[size] = ele;size++;}public Object get(){  //获取if(size <= 0){throw new RuntimeException("Queue is empty, acquisition failed");}Object obj = values[0];//数据前移for(int i = 0;i < size - 1;i++){values[i] = values[i + 1];}//最后一个元素置空values[size - 1] = null;size--;return obj;}}

ArrayList在JDK7和JDK8中的源码

ArrayList特点:

实现了list接口,存储有序,可重复

底层为object[ ]数组存储

线程不安全

ArrayList源码解析：jdk7版本：(以jdk1.7.0_07为例)

//如下代码的执行：底层会初始化数组，数组的长度为10。Object[] elementData = new Object[10];
ArrayList<String> list = new ArrayList<>();list.add("AA"); //elementData[0] = "AA";
list.add("BB");//elementData[1] = "BB";
//... ...
//当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。

ArrayList源码解析：jdk8版本:(以jdk1.8.0_271为例)

//如下代码的执行：底层会初始化数组，即：Object[] elementData = new Object[]{};
ArrayList<String> list = new ArrayList<>();list.add("AA"); //首次添加元素时，会初始化数组elementData = new Object[10];elementData[0] = "AA";
list.add("BB");//elementData[1] = "BB";
//......
//当要添加第11个元素的时候，底层的elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素复制到新的数组中。

小结

 jdk1.7.0_07版本中：ArrayList类似于饿汉式,直接创建10个存储位置

jdk1.8.0_271版本中：ArrayList类似于懒汉式,先是创建一个空数组,在第一次添加时创建10个存储位置并且添加数据.

vector在JDK8中的源码剖析

Vector特点

实现了list接口,存储有序可重复的数据

底层为object[ ]数组

线程安全

Vector源码解析：(以jdk1.8.0_271为例)

Vector v = new Vector(); //底层初始化数组，长度为10.Object[] elementData = new Object[10];
v.add("AA"); //elementData[0] = "AA";
v.add("BB");//elementData[1] = "BB";
//......
//当添加第11个元素时，需要扩容。默认扩容为原来的2倍。

LinkedList在JDK8中的源码剖析

LinkedList的特点：

实现了list接口,存储有序可重复的数据

底层为双向链表

线程不安全

LinkedList在jdk8中的源码解析：

LinkedList<String> list = new LinkedList<>(); //底层也没做啥
list.add("AA"); //将"AA"封装到一个Node对象1中，list对象的属性first、last都指向此Node对象1。
list.add("BB"); //将"BB"封装到一个Node对象2中，对象1和对象2构成一个双向链表，同时last指向此Node对象2
//......
/*
因为LinkedList使用的是双向链表，不需要考虑扩容问题。
LinkedList内部声明：
*/
private static class Node<E> {E item;Node<E> next;Node<E> prev;
}

LinkedList不存在扩容问题 

HashMap

HashMap中元素的特点

> HashMap中的所有的key彼此之间是不可重复的、无序的。所有的key就构成一个Set集合。--->key所在的类要重写hashCode()和equals()

> HashMap中的所有的value彼此之间是可重复的、无序的。所有的value就构成一个Collection集合。--->value所在的类要重写equals()

> HashMap中的一个key-value,就构成了一个entry。

> HashMap中的所有的entry彼此之间是不可重复的、无序的。所有的entry就构成了一个Set集合。

HashMap在JDK7中的源码剖析

jdk7中创建对象和添加数据过程(以JDK1.7.0_07为例说明)：

//创建对象的过程中，底层会初始化数组Entry[] table = new Entry[16];
HashMap<String,Integer> map = new HashMap<>();
...
map.put("AA",78); //"AA"和78封装到一个Entry对象中，考虑将此对象添加到table数组中。
...添加/修改的过程：
将(key1,value1)添加到当前的map中：
首先，需要调用key1所在类的hashCode()方法，计算key1对应的哈希值1，此哈希值1经过某种算法(hash())之后，得到哈希值2。
哈希值2再经过某种算法(indexFor())之后，就确定了(key1,value1)在数组table中的索引位置i。1.1 如果此索引位置i的数组上没有元素，则(key1,value1)添加成功。  ---->情况11.2 如果此索引位置i的数组上有元素(key2,value2),则需要继续比较key1和key2的哈希值2  --->哈希冲突2.1 如果key1的哈希值2与key2的哈希值2不相同，则(key1,value1)添加成功。   ---->情况22.2 如果key1的哈希值2与key2的哈希值2相同，则需要继续比较key1和key2的equals()。要调用key1所在类的equals(),将key2作为参数传递进去。3.1 调用equals()，返回false: 则(key1,value1)添加成功。   ---->情况33.2 调用equals()，返回true: 则认为key1和key2是相同的。默认情况下，value1替换原有的value2。说明：情况1：将(key1,value1)存放到数组的索引i的位置情况2,情况3：(key1,value1)元素与现有的(key2,value2)构成单向链表结构，(key1,value1)指向(key2,value2)随着不断的添加元素，在满足如下的条件的情况下，会考虑扩容：
(size >= threshold) && (null != table[i])
当元素的个数达到临界值(-> 数组的长度 * 加载因子)时，就考虑扩容。默认的临界值 = 16 * 0.75 --> 12.'
null != table[i]-->要添加的地方不是空的,要导致链表增多,那么就扩容
默认扩容为原来的2倍。

1.实例化过程

HashMap<String,Integer> map = new HashMap<>();

对应的源码：

public HashMap() {this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

public HashMap(int initialCapacity, float loadFactor) {//...略...//通过此循环，得到capacity的最终值，此最终值决定了Entry数组的长度。此时的capacity一定是2的整数倍int capacity = 1;while (capacity < initialCapacity)capacity <<= 1;this.loadFactor = loadFactor; //确定了加载因子的值threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  //确定了临界值table = new Entry[capacity]; //初始化数组，长度为capacity//..略..
}

其中：

static final int DEFAULT_INITIAL_CAPACITY = 16;
static final float DEFAULT_LOAD_FACTOR = 0.75f;final float loadFactor; //加载因子
int threshold;//临界值
transient Entry<K,V>[] table; //存储数组的数组

2. put(key,value)的过程

public V put(K key, V value) {//HashMap允许添加key为null的值。将此(key,value)存放到table索引0的位置。if (key == null)return putForNullKey(value);//将key传入hash()，内部使用了key的哈希值1，此方法执行结束后，返回哈希值2int hash = hash(key);//确定当前key，value在数组中的存放位置iint i = indexFor(hash, table.length);for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = dAccess(this);return oldValue;  //如果put是修改操作，会返回原有旧的value值。}}//.....addEntry(hash, key, value, i); //将key,value封装为一个Entry对象，并将此对象保存在索引i位置。return null; //如果put是添加操作，会返回null.
}

其中：

final int hash(Object k) {int h = 0;if (useAltHashing) {if (k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h = hashSeed;}h ^= k.hashCode();// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

static int indexFor(int h, int length) {return h & (length-1);
}

void addEntry(int hash, K key, V value, int bucketIndex) {//扩容的条件if ((size >= threshold) && (null != table[bucketIndex])) {resize(2 * table.length); //默认扩容为原有容量的2倍hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<>(hash, key, value, e);size++;
}

3. Entry的定义如下：

static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;  //使用key得到的哈希值2进行赋值。/*** Creates new entry.*/Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}
}

HashMap在JDK8中的不同之处

① 在jdk8中，当我们创建了HashMap实例以后，底层并没有初始化table数组。当首次添加(key,value)时，进行判断，
如果发现table尚未初始化，则对数组进行初始化。
② 在jdk8中，HashMap底层定义了Node内部类，替换jdk7中的Entry内部类。意味着，我们创建的数组是Node[]
③ 在jdk8中，如果当前的(key,value)经过一系列判断之后，可以添加到当前的数组角标i中。如果此时角标i位置上有元素。在jdk7中是将新的(key,value)指向已有的旧的元素（头插法），而在jdk8中是旧的元素指向新的(key,value)元素（尾插法）。 "七上八下"
④ jdk7:数组+单向链表jk8:数组+单向链表 + 红黑树什么时候会使用单向链表变为红黑树：如果数组索引i位置上的元素的个数达到8，并且数组的长度达到64时，我们就将此索引i位置上的多个元素改为使用红黑树的结构进行存储。（为什么修改呢？红黑树进行put()/get()/remove()操作的时间复杂度为O(logn)，比单向链表的时间复杂度O(n)的好。性能更高。什么时候会使用红黑树变为单向链表：当使用红黑树的索引i位置上的元素的个数低于6的时候，就会将红黑树结构退化为单向链表。

HashMap的属性和字段

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量 16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量  1 << 30
static final float DEFAULT_LOAD_FACTOR = 0.75f;  //默认加载因子
static final int TREEIFY_THRESHOLD = 8; //默认树化阈值8，当链表的长度达到这个值后，要考虑树化
static final int UNTREEIFY_THRESHOLD = 6;//默认反树化阈值6，当树中结点的个数达到此阈值后，要考虑变为链表//当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。
//当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容
static final int MIN_TREEIFY_CAPACITY = 64; //最小树化容量64transient Node<K,V>[] table; //数组
transient int size;  //记录有效映射关系的对数，也是Entry对象的个数
int threshold; //阈值，当size达到阈值时，考虑扩容
final float loadFactor; //加载因子，影响扩容的频率

LinkedHashMap,HashSet,LinkedHashSet源码剖析

LinkedHashMap 与 HashMap 的关系

> LinkedHashMap 是 HashMap的子类。
> LinkedHashMap在HashMap使用的数组+单向链表+红黑树的基础上，又增加了一对双向链表，记录添加的(key,value)的
先后顺序。便于我们遍历所有的key-value。

LinkedHashMap重写了HashMap的如下方法：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e);linkNodeLast(p);return p;
}

底层结构：LinkedHashMap内部定义了一个Entry

static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after; //增加的一对双向链表Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}
}

HashSet和LinkedHashSet的源码分析

> HashSet底层使用的是HashMap
> LinkedHashSet底层使用的是LinkedHashMap