行业知识
Day17
2026-11-02 06:40:48
来源：互联网转载
文章目录
- Day17 集合与数据结构
- 学习目标
- 1 数据结构
- 2 动态数组
- 2.1 动态数组的特点
- 2.2 自定义动态数组
- 2.3 ArrayList与Vector的区别？
- 2.4 ArrayList部分源码分析
- 1、JDK1.6构造器
- 2、JDK1.7构造器
- 3、JDK1.8构造器
- 4、添加与扩容
- 5、删除元素
- 6、get/set元素
- 7、查询元素
- 8、迭代器Itr
- 2.5 Vector部分源码分析
- 1、构造器
- 2、添加与扩容
- 3 链表
- 3.1 链表的特点
- 3.2 自定义双链表（选讲）
- 3.3 核心类库中LinkedList源码分析
- 1、结点类型
- 2、添加结点
- 3、删除结点
- 4、查询结点
- 3.4 自定义单链表（选讲）
- 3.5 链表与动态数组的区别
- 4 栈和队列
- 4.1 栈
- 4.2 队列
- 5 Map
- 5.1 概述
- 5.2 Map常用方法
- 5.3 Map集合的遍历
- 5.4 Map的实现类们
- **1、HashMap和Hashtable**
- **2、LinkedHashMap**
- **3、TreeMap**
- **4、Properties**
- 5.5 Set集合与Map集合的关系
- 6 集合框架
- 7 Collections工具类
- 8 二叉树了解
- 8.1 二叉树的遍历
- 8.2 经典二叉树
- 8.3 二叉树及其结点的表示
- 9 哈希表
- **9.1 hashCode值**
- **9.2 哈希表的物理结构**
- **1、数组元素类型：Map.Entry**
- 2、数组的长度始终是2的n次幂
- 3、那么HashMap是如何决定某个映射关系存在哪个桶的呢？
- 4、hash是hashCode的再运算
- 5、解决[index]冲突问题
- 6、为什么JDK1.8会出现红黑树和链表共存呢？
- 7、什么时候树化？什么时候反树化？
- 8、数组扩容相关问题
- 9.3 JDK1.7的put方法源码分析
- 1、构造器
- 2、put方法
- 9.4 JDK1.8的put方法源码分析
- 1、几个常量和变量
- 2、构造器
- 3、put方法
- 9.5 关于���射关系的key是否可以修改？
Day17 集合与数据结构
学习目标
- 能够说出List接口的常用实现类集合的区别
- 能够说出Set接口的常用实现类集合的区别
- 能够说出Map接口的常用实现类集合的区别
- 能够说出Set系列与Map系列集合的关系
- 能够说出Collection系列与Map系列集合的区别
- 能够画出Collection和Map等所有常用集合的关系图
- 掌握Collections集合工具类的使用
- 对常见数据结构有初步了解
- 掌握动态数组的实现方式
- 理解单链表与双链表的实现方式
- 理解哈希表的实现方式
1 数据结构
数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
（1）数据的逻辑结构指反映数据元素之间的逻辑关系，而与他们在计算机中的存储位置无关：
- 散列结构：元素之间除了“同属一个集合” 的相互关系外，别无其他关系；例如：同一个班级的学生信息
- 线性结构：元素存在一对一的相互关系；例如：队列（先进先出）、栈（先进后出）等
- 树形结构：元素存在一对多的相互关系；例如：直系族谱
- 图形结构：元素存在多对多的相互关系；例如：好友关系图
（2）数据的物理结构/存储结构：是描述数据具体在内存中的存储（如：数组结构、链式结构、索引结构、哈希结构）等，一种数据逻辑结构可表示成一种或多种物理存储结构。
- 数组结构：元素在内存中是连续存储的，即元素存储在一整块连续的存储空间中，此时根据索引的查询效率是非常高的，因为可以根据下标索引直接一步到位找到元素位置，如果在数组末尾添加和删除元素效率也非常高。缺点是，如果事先申请足够大的内存空间，可能造成空间浪费，如果事先申请较小的内存空间，可能造成频繁扩容导致元素频繁搬家。另外，在数组中间添加、删除元素操作，就需要移动元素，此时效率也要打折。
- 链式结构：元素在内存中是不要求连续存储的，但是元素是封装在结点当中的，结点中需要存储元素数据，以及相关结点对象的引用地址。结点与结点之间可以是一对一的关系，也可以一对多的关系，比如：链表、树等。遍历链式结构只能从头遍历，对于较长的链表来说查询效率不高，对于树结构来说，查询效率比链表要高一点，因为每次可以确定一个分支，从而排除其他分支，但是相对于数组来说，还是数组[下标]的方式更快。树的实现方式有很多种，无非就是在添加/删除效率 与 查询效率之间权衡。
- 索引结构：元素在内存中是不要求连续存储的，但是需要有单独的一个索引表来记录每一个元素的地址，这种结构根据索引的查询效率很高，但是需要额外存储和维护索引表。
- 哈希结构：元素的存储位置需要通过其hashCode值来计算，查询效率也很高，但是要考虑和解决好哈希冲突问题。
数据结构和算法是一门完整并且复杂的课程。
Java的核心类库中提供很多数据结构对应的集合类型，例如动态数组、双向链表、顺序栈、链式栈、队列、双端队列、红黑树、哈希表等等。
2 动态数组
2.1 动态数组的特点
逻辑结构特点：线性结构
物理结构特点：
-
申请内存：一次申请一大段连续的空间，一旦申请到了，内存就固定了。
-
存储特点：所有数据存储在这个连续的空间中，数组中的每一个元素都是一个具体的数据（或对象），所有数据都紧密排布，不能有间隔。
例如：整型数组
例如：对象数组
2.2 自定义动态数组
package com.atguigu.array;import java.util.Arrays;import java.util.Iterator;import java.util.NoSuchElementException;public class MyArrayList implements Iterable{ private Object[] all; private int total; public MyArrayList(){ all = new Object[10]; } public void add(E e) { ensureCapacityEnough(); all[total++] = e; } private void ensureCapacityEnough() { if(total >= all.length){ all = Arrays.copyOf(all, all.length + (all.length>>1)); } } public void insert(int index, E value) { //添加元素的下标检查 addCheckIndex(index); //是否需要扩容 ensureCapacityEnough(); //是否需要移动元素 if(total-index > 0) { System.arraycopy(all, index, all, index+1, total-index); } all[index]=value; total++; } private void addCheckIndex(int index) { if(indextotal){ throw new IndexOutOfBoundsException(index+"越界"); } } public void delete(E e) { int index = indexOf(e); if(index==-1){ throw new NoSuchElementException(e+"不存在"); } delete(index); } public void delete(int index) { //删除元素的下标检查 checkIndex(index); //是否需要移动元素 if(total-index-1 > 0) { System.arraycopy(all, index+1, all, index, total-index-1); } all[--total] = null; } private void checkIndex(int index) { if(indextotal){ throw new IndexOutOfBoundsException(index+"越界"); } } public void update(int index, E value) { //更新修改元素的下标检查 checkIndex(index); all[index] = value; } public void update(E old, E value) { int index = indexOf(old); if(index!=-1){ update(index, value); } } public boolean contains(E e) { return indexOf(e) != -1; } public int indexOf(E e) { int index = -1; if(e==null){ for (int i = 0; i = 0; i--) { if(e == all[i]){ index = i; break; } } }else{ for (int i = total-1; i >= 0; i--) { if(e.equals(all[i])){ index = i; break; } } } return index; } public E get(int index) { //获取元素的下标检查 checkIndex(index); return (E) all[index]; } public int size() { return total; } public Iterator iterator() { return new Itr(); } private class Itr implements Iterator{ private int cursor; @Override public boolean hasNext() { return cursor测试类：
package com.atguigu.list;import java.util.Iterator;public class TestMyArrayList { public static void main(String[] args) { MyArrayList my = new MyArrayList(); my.add("hello"); my.add("java"); my.add("java"); my.add("world"); my.add(null); my.add(null); my.add("atguigu"); my.add("list"); my.add("data"); System.out.println("元素个数：" + my.size()); for (String s : my) { System.out.println(s); } System.out.println("-------------------------"); System.out.println("在[1]插入尚硅谷后："); my.insert(1, "尚硅谷"); System.out.println("元素个数：" + my.size()); for (String s : my) { System.out.println(s); } System.out.println("--------------------------"); System.out.println("删除[1]位置的元素后："); my.delete(1); System.out.println("元素个数：" + my.size()); for (String s : my) { System.out.println(s); } System.out.println("删除atguigu元素后："); my.delete("atguigu"); System.out.println("元素个数：" + my.size()); for (String s : my) { System.out.println(s); } System.out.println("删除null元素后："); my.delete(null); System.out.println("元素个数：" + my.size()); for (String s : my) { System.out.println(s); } System.out.println("------------------------------"); System.out.println("替换[3]位置的元素为尚硅谷后："); my.update(3, "尚硅谷"); System.out.println("元素个数：" + my.size()); for (String s : my) { System.out.println(s); } System.out.println("替换java为JAVA后："); my.update("java", "JAVA"); System.out.println("元素个数：" + my.size()); for (String s : my) { System.out.println(s); } System.out.println("------------------------------------"); System.out.println("是否包含java：" +my.contains("java")); System.out.println("java的位置：" + my.indexOf("java")); System.out.println("haha的位置：" + my.indexOf("haha")); System.out.println("[0]位置元素是：" + my.get(0)); System.out.println("------------------------------------"); System.out.println("删除字符串长度>4的元素后："); Iterator iterator = my.iterator(); while(iterator.hasNext()) { String next = iterator.next(); if(next != null && next.length()>4) { iterator.remove(); } } System.out.println("元素个数：" + my.size()); for (String string : my) { System.out.println(string); } }}2.3 ArrayList与Vector的区别？
核心类库中List接口有两个实现类：Vector和ArrayList。它们的底层物理结构都是数组，我们称为动态数组。
（1）ArrayList是新版的动态数组，线程不安全，效率高，Vector是旧版的动态数组，线程安全，效率低。
（2）动态数组的扩容机制不同，ArrayList扩容为原来的1.5倍，Vector扩容增加为原来的2倍。
（3）数组的初始化容量，如果在构建ArrayList与Vector的集合对象时，没有显式指定初始化容量，那么Vector的内部数组的初始容量默认为10，而ArrayList在JDK1.6及之前的版本也是10，JDK1.7之后的版本ArrayList初始化为长度为0的空数组，之后在添加第一个元素时，再创建长度为10的数组。
ArrayList在第1次添加时再创建数组是为了避免浪费。因为很多方法的返回值是ArrayList类型，需要返回一个ArrayList的对象，例如：后期从数据库查询对象的方法，返回值很多就是ArrayList。有可能你要查询的数据不存在，要么返回null，要么返回一个没有元素的ArrayList对象。
（4）Vector因为版本古老，支持Enumeration 迭代器。但是该迭代器不支持快速失败。而Iterator和ListIterator迭代器支持快速失败。如果在迭代器创建后的任意时间从结构上修改了向量（通过迭代器自身的 remove 或 add 方法之外的任何其他方式），则迭代器将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就完全失败，而不是冒着在将来不确定的时间任意发生不确定行为的风险。
2.4 ArrayList部分源码分析
1、JDK1.6构造器
public ArrayList() {this(10);//指定初始容量为10 } public ArrayList(int initialCapacity) {super(); //检查初始容量的合法性 if (initialCapacity2、JDK1.7构造器
private static final int DEFAULT_CAPACITY = 10;//默认初始容量10private static final Object[] EMPTY_ELEMENTDATA = {};public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA;//数组初始化为一个空数组 } public boolean add(E e) { //查看当前数组是否够多存一个元素 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) {//如果当前数组还是空数组 //minCapacity按照 默认初始容量和minCapacity中的的最大值处理 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }//看是否需要扩容处理 ensureExplicitCapacity(minCapacity); }//...3、JDK1.8构造器
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//初始化为空数组 }4、添加与扩容
private static final int DEFAULT_CAPACITY = 10;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; public boolean add(E e) { //查看当前数组是否够多存一个元素 ensureCapacityInternal(size + 1); // Increments modCount!! //存入新元素到[size]位置，然后size自增1 elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { //如果当前数组还是空数组 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //那么minCapacity取DEFAULT_CAPACITY与minCapacity的最大值 minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }//查看是否需要扩容 ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++;//修改次数加1 // 如果需要的最小容量 比 当前数组的长度 大，即当前数组不够存，就扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length;//当前数组容量 int newCapacity = oldCapacity + (oldCapacity >> 1);//新数组容量是旧数组容量的1.5倍 //看旧数组的1.5倍是否够 if (newCapacity - minCapacity 0) newCapacity = hugeCapacity(minCapacity); //复制一个新数组 elementData = Arrays.copyOf(elementData, newCapacity); }public void add(int index, E element) { rangeCheckForAdd(index);//看是否需要扩容 ensureCapacityInternal(size + 1); // Increments modCount!!//将[index]以及后面的元素往右移动 System.arraycopy(elementData, index, elementData, index + 1,size - index);//将新元素添加到 elementData[index] elementData[index] = element;//元素个数增加 size++; }private void rangeCheckForAdd(int index) {//elementData实际已经存储[0,size-1]//可插入的位置[0,size] if (index > size || index5、删除元素
public boolean remove(Object o) { //先找到o在当前ArrayList的数组中的下标 //分o是否为空两种情况讨论 if (o == null) { for (int index = 0; index 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //将elementData[size-1]位置置空，让GC回收空间，元素个数减少 elementData[--size] = null; // clear to let GC do its work }public E remove(int index) { rangeCheck(index);//检验index是否合法 modCount++;//修改次数加1 //取出[index]位置的元素，[index]位置的元素就是要被删除的元素，用于最后返回被删除的元素 E oldValue = elementData(index); //需要移动的元素个数 int numMoved = size - index - 1; //如果需要移动元素，就用System.arraycopy移动元素 if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); //将elementData[size-1]位置置空，让GC回收空间，元素个数减少 elementData[--size] = null; // clear to let GC do its work return oldValue; }private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }@Override public boolean removeIf(Predicate list)反转指定列表List中元素的顺序。
- public static void shuffle(List list) List 集合元素进行随机排序，类似洗牌
- public static
-
上一篇：怎么更换服务器风扇驱动?
