数据结构

定义

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

研究对象

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

集合结构
线性结构：一对一
树形结构：一对多
图形结构：多对多

研究对象2：数据的存储结构

顺序结构
链式结构
索引结构
散列结构

开发中，更习惯于如下的方式理解存储结构

线性表（一对一）：一维数组、单向链表、双向链表、栈、队列
树（一对多）：各种树。二叉树、B+树
图（多对多）：
哈希表：HashMap、HashSet

研究对象3：相关算法操作

分配资源、建立结构、释放资源
插入和删除
获取和遍历
修改和排序

存储结构

数组

链表

单向链表

class Node{

	Object data;

	Node next;
    
    public Node(Object data){
        this.data = data;
    }
}

Node node1 = new Node("AA");
Node node2 = new Node("BB");
node1.next = node2;

双向链表

class Node{
	Node prev;
	Object data;
	Node next;
    
    public Node(Object data){
        this.data = data;
    }
    
    public Node(Node prev, Object data, Node next){
        this.prev = prev;
        this.data = data;
        this.next = next;
    }
}


Node node1 = new Node(null, "aa", null);
Node node2 = new Node(node1, "bb", null);
Node node3 = new Node(node2,"cc", null);

node1.next = node2;
node2.next = node3;

二叉树

class TreeNode{
	TreeNode parent; 
	TreeNode left;
	Object data;
	TreeNode right;
	
	public TreeNode(Object data){
		this.data = data;
	}
	public TreeNode(TreeNode left, Object data, TreeNode right){
		this.left =left;
		this.data = data;
		this.right=right;
	}
}

TreeNode node1 = new TreeNode(null, null,"AA", null);
TreeNode leftNode = new TreeNode(node1, null,"bb", null);
TreeNode rightNode = new TreeNode(node1, null,"cc", null);
node1.right = rightNode;
node1.left = leftNode;

栈FILO

属于抽象数据类型（ADT）
可以使用数组或链表来构建

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;

    }
}

队列FIFO

属于抽象数据类型（ADT）
可以使用数组或链表来构建

class Stack{
//数组实现栈
Object[] values
int size;

class Queue{
    Object[] values;
    int size;
    
    public Queue(int lenght){
        values = new Object[length];
    }
    
    public void add(Object ele){
        if(size>= values.length){
            throw new RuntimeException("队列已满，添加失败");
        }
        values[size] = ele;
        size ++;
    }
    
    public Object get(){
        if(size<=0){
            throw new RuntimeException("队列已空，获取失败");
        }
        
        Object obj = values[0];
        for(int i= 0;i<size-1;i++){
            values[i] = values[i+1];
        }
        values[size - 1] = null;
        size --;
        return obj;
    }
}

List源码

ArrayList

ArrayList特点

实现了List接口，存储有序、可以重复的数据
底层使用Object[]数组存储
线程不安全

ArrayList源码解析

jdk7: 如下代码执行：底层会初始化数组，数组的长度为10。Object[] elementData = new Object[10]

ArrayList list = new ArrayList<>()

list.add(“AA”);//elementData[0] = “AA”;

list.add(“BB”); //elementData[1] = “BB”;

…..

当添加第11个元素时，底层elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素赋值到新的数组中

**jdk8:**底层会初始化数组，即：Object[] elementData= new Object[]{};

ArrayList list = new ArrayList<>();

list.add(“AA”);//首次添加元素，会初始化数组 elementData = new Object[10]; elementData[0] = “AA”;

list.add(“BB”);//elementData[1] = “BB”;

当添加第11个元素时，底层elementData数组已满，则需要扩容。默认扩容为原来长度的1.5倍。并将原有数组中的元素赋值到新的数组中

小结

jdk7中类似于饿汉式

jdk8中类似于懒汉式

Vector

特点

实现了List接口，存储有序、可以重复的数据
底层使用了Object[]数组存储
线程安全

源码

Vector v = new Vector();//底层初始化数组，长度为10 Object[] element = new Object[10];

v.add(“aa”);

v.add(“bb”);

当前添加第11个元素时，扩容2倍

LinkedList

特点

实现List接口，存储有序、可以重复的数据
底层使用了双向链表存储
线程不安全

源码

LinkedList list = new LinkedList<>(); //底层也没做啥

list.add(“AA”);//将“AA”封装到一个Node对象中，list对象的属性first、last都指向次node对象。

list.add(“BB”);//将“BB”封装到一个Node对象2中，对象1和对象2构成一个双向链表，同时last指向此Node对象2

…..

因为linkedList使用的是双向链表，不需要考虑扩容问题。

启示

1.Vector不使用了

2.ArrayList底层使用数组结构，查找和添加（尾部添加）操作效率高，时间复杂度为O（1）

删除和插入操作效率低，时间复杂度为O（n)

LinkedList底层使用双向链表，删除和插入操作效率高，时间复杂度O（1）

查找和添加（尾部添加）操作效率低，时间为O（n)（添加可能O(1))

3.在选择了ArrayList的前提下，new ArrayList()：底层创建长度为10的数组。

new ArrayList(int capacity):底层创建指定capacity长度的数组。

Map源码

HashMap源码解析

jdk7:

//创建对象的过程中，底层会初始化数组Entry[] table = new Entry[16];

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

map.put(“AA”, 78); //“AA”和78封装到一个Entry对象总，考虑将此对象添加到table数组中。

…

添加/修改的过程:

将（key1,value1)添加到当前的map中

首先，需要调用key所在类的hashCode()方法，计算key1对应的哈希值1，此哈希值1经过某种算法（hash())之后，得到哈希值2。

哈希值2再经过某种算法（indexFor())之后，就确定了(key1,value1)在数组table中的索引位置i。

如果此索引位置i的数组上没有元素，则（key1,value1)添加成功 —>情况1
如果此缩影位置i的数组上有元素（key2,value2),则需要继续比较key1和key2的哈希值2 —>哈希冲突
- 如果key1的哈希值2与key2的哈希值2不相同，则(key1,value1)添加成功。 —->情况2
- 如果key1的哈希值2与key2的哈哈希值2相同，则需要继续比较key1和key2的equals()。要调用key1所在类的equals(),将key2作为参数传递进去
  - 调用equals()，返回false:则（key1,value1)添加成功 —->情况3
  - 调用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.

默认扩容为原来的两倍

jdk8与jdk7的不同之处

在jdk8中，当我面创建了HashMap实例以后，底层并没有初始化table数组。当首次添加(key,value)时，进行判断，如果发现table尚未初始化，则对数组进行初始化。
在jdk8中，HashMap底层定义类Node内部类，替换了jdk7中的Entry内部类。意味着，我们创建的数组是Node[]
jdk8中，当前的(key,value)经过一系列判断之后，可以添加到当前的数组的角标i中。如果此时角标i位置上有元素。在jdk7中是将新的（key,value)指向已有的旧的元素（头插法）。而在jdk8中旧的元素指向新的（key,value)元素（尾插法）
jdk7：数组+单向链表；jdk8:数组+单向链表+红黑树。

什么时候会使用红黑树：如果数组索引i位置上的元素的个数达到8，并且数组的长度达到64时，我们就将此索引i位置上的多个元素改为使用红黑树的结构进行存储。（为什么修改呢？红黑树进行put()/get()/remove()，操作的时间复杂度为O（logn),比单向链表的时间复杂度O(n)的好。性能高。

什么时候会使用红黑树变为单向链表：当使用红黑树的索引i位置上的元素的个数小于6时，就会将红黑树退化为单向链表。

LinkedHashMap

LinkedHashMap是HashMap的子类

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

重写了增加方法。

HashSet和LinkedHashSet源码分析

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

常见问题

链表和数组的区别？

栈是如何运行的？

ArraList的默认大小是多少，以及扩容机制

ArraList的底层是怎么实现的

数组和ArrayList的区别

ArrayList看作是对数组的常见操作的封装

什么是线程安全的List

HashMap初始值16，临界值12是怎么算的

HashMap长度为什么是2的幂

为了方便计算要添加的元素的底层的索引i

HashMap怎么计算哈是在和索引？扩容机制？解决Hash冲突

HashMap底层为什么加链表？

因为有哈斯冲突。解决方案，使用链表的方式。保证要添加的元素仍然在索引i的位置上

HashMap为什么长度达到一定的长度要转化为红黑树？

HashMap的get()原理？

hashCode()与equals()生产算法，方法怎么重写？

进行equals()判断使用的属性，通常也都会参与到hashCode()的计算中。尽量保证hashCode()的一致性。

Alugg's Blog

java-Day12——HashMap源码