Java集合底层源码数据结构（java集合底层源码数据结构怎么写）

package unit6;

import java.util.*;

/*

1.数据结构

队列：先进先出，后进后出

栈：后进先出，先进后出

数组：内存连续区域，根据索引查询快，增删慢

链表：元素是游离的，查询慢，双向链表首尾操作极快

二叉树：永远只有一个根节点，每个节点不超过2个子节点的树

二叉查找树：小的左边，大的右边，但是可能树会变得很高，查询性能变差

平衡查找二叉树：让树的高度差不大于1，增删改查都提高了

红黑树：基于红黑规则实现了自平衡的排序二叉树

2.集合数据结构

List:

ArrayList：数组

LinkedList：链表

Set：

HashSet：底层HashMap

TreeSet：底层TreeMap

Map：

HashMap：数组+链表+红黑树(链表长度大于阈值8)

TreeMap：红黑树

*/

public class CollectionTest extends Object {

public static void main(String[] args) {

// (1)ArrayList数组结构

// public class ArrayList<E> extends AbstractList<E>

// implements List<E>, RandomAccess, Cloneable, java.io.Serializable

// List 有序集合接口

// RandomAccess 通过元素序号快速获取元素对象、快速随机访问

// Cloneable 重写clone、能被克隆

// Serializable 序列化接口、对象流化

// ArrayList<Integer> arrayList = new ArrayList();

// this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

// private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// Object[]数组、初始长度为0

// arrayList.add(1);

// 当添加第一个元素的时候、创建一个长度为10的Object数组

// private static final int DEFAULT_CAPACITY = 10;

// grow扩容的方法、扩容1.5倍

// if (minCapacity - elementData.length > 0) grow(minCapacity); }

// int newCapacity = oldCapacity + (oldCapacity >> 1);

// elementData = Arrays.copyOf(elementData, newCapacity);

// System.out.println(arrayList.get(0));

// int a = 4;

// System.out.println(a << 2); // 右移一位就是除2、左移一位就是乘2

// (2)LinkedList链表结构

// public class LinkedList<E>

// extends AbstractSequentialList<E>

// implements List<E>, Deque<E>, Cloneable, java.io.Serializable

// private static class Node<E> {

// E item;

// LinkedList.Node<E> next;

// LinkedList.Node<E> prev;

//

// Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {

// this.item = element;

// this.next = next;

// this.prev = prev;

// }

// }

// LinkedList linkedList = new LinkedList();

// linkedList.add(1);

// final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);

// last = newNode;

// linkedList.remove("");

// 链表遍历方式

// for (LinkedList.Node<E> x = first; x != null; x = x.next) {

// if (o.equals(x.item)) {

// unlink(x);

// return true;

// }

// }

// final LinkedList.Node<E> next = x.next;

// final LinkedList.Node<E> prev = x.prev;

//

// if (prev == null) {

// first = next;

// } else {

// prev.next = next;

// x.prev = null;

// }

// (3)HashMap数组结构 + 链表结构 + 红黑树结构

// HashMap初始化大小是16

// static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

// 之后每次扩容是原来的2倍

// newThr = oldThr << 1;

// 链表阈值超过8则会转换为红黑树

// static final int TREEIFY_THRESHOLD = 8;

// 数组、如果链表长度超过8、先扩容数组、如果数值长度超过64、转换为红黑树

// static final int MIN_TREEIFY_CAPACITY = 64;

HashMap hashMap = new HashMap();

// this.loadFactor = DEFAULT_LOAD_FACTOR;

// 扩容的阈值：0.75 超过3/4才会扩容

// static final float DEFAULT_LOAD_FACTOR = 0.75f;

hashMap.put(1, "张三");

}

}