=单列集合:
----------List
ArrayList的源代码分析(扩容原理)
- 1 使用空参构造的集合,在底层创建一个容量为0的数组。
- 2 添加第一个元素时,底层会扩容创建一个容量为10的数组。
- 3 存满时会扩容1.5倍。
- 4 如果一次添加多个元素,1.5倍还放不下,那么扩容以实际需要的数组大小来扩容。
空参构造-初始化:
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
1 这里的elementData是一个Object数组
transient Object[] elementData; // non-private to simplify nested class access
2 长度为0的一个数组赋值给这里的Object数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
长度初始化
数组长度与与接下来应该添加的元素位置:(默认为0)
private int size;
添加元素-扩容:(代码为逐层调用)
1
public boolean add(E e) {modCount++;add(e, elementData, size);return true;}
e为添加元素的名称
elementData为底层数组名称
size为添加位置/也是未添加前数组长度
2
private void add(E e, Object[] elementData, int s) {if (s == elementData.length)elementData = grow();elementData[s] = e;size = s + 1;}
先有一个判断:如果数组长度已经等于数组中元素的个数,那么数组已经满了
需要实现grow()扩容
然后再实现对s(添加位置)进行赋值,最后再将数组长度加一。
3
private Object[] grow() {return grow(size + 1);}
现有个数加一进行扩容
public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();modCount++;int numNew = a.length;if (numNew == 0)return false;Object[] elementData;final int s;if (numNew > (elementData = this.elementData).length - (s = size))elementData = grow(s + numNew);System.arraycopy(a, 0, elementData, s, numNew);size = s + numNew;return true;}
将添加的集合变成数组,获取长度,如果这个需要添加的数组的长度大于数组还剩下的长度那么调用grow扩容
最后调用System.arraycopy方法进行填充赋值
4
private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1 /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}
这里的MinCapacity未上面传参的size+1
oldCapacity为数组原先的长度
首次扩容oldCapacity为0,执行else这一路径的代码
此时扩容为10 max(10,1)
private static final int DEFAULT_CAPACITY = 10;
之后会执行if中的代码
newCapacity为重新赋值的数据,这里调用的时ArraySupport.newLength方法
传入的三个参数分别是
oldCapacity老容量
MinCapacity-oldCapacity我们理论上应该扩容的容量
oldCapacity<<1默认新增容量的大小(0.5倍)
最后再使用Arrays.copyOf(原先的数组,新数组的长度)
实现扩容并且拷贝
5
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// preconditions not checked because of inlining// assert oldLength >= 0// assert minGrowth > 0int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflowif (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn hugeLength(oldLength, minGrowth);}}
这里的PreLength为
老数组长度加上理论扩容大小(主要是应对addAll方法可能会出现添加多个元素)与
默认扩容大小(0.5倍)的最大值
补充:这里的else是出现数组容量超出范围的情况(一般情况下不会遇到)
最大长度
public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
代码展示
private static int hugeLength(int oldLength, int minGrowth) {int minLength = oldLength + minGrowth;if (minLength < 0) { // overflowthrow new OutOfMemoryError("Required array length " + oldLength + " + " + minGrowth + " is too large");} else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {return SOFT_MAX_ARRAY_LENGTH;} else {return minLength;}}
LinkedList的源代码分析(扩容原理)
原理与双向链表相同------(主要是有序)
成员变量
三个参数,头节点长度尾节点
transient int size = 0;/*** Pointer to first node.*/transient Node<E> first;/*** Pointer to last node.*/transient Node<E> last;
1 节点
private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}}
2
public boolean add(E e) {linkLast(e);return true;}
3
void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}
iterator迭代器的源代码分析
import java.util.ArrayList;
import java.util.Iterator;public class Students {public static void main(String[] args) {ArrayList<Integer> list = new ArrayList<>();list.add(1);Iterator<Integer> iterator = list.iterator();while (iterator.hasNext()) {iterator.remove();System.out.println(iterator.next());}}
}
1
int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;
cursor指向操作位置
lastret指向上一个操作位置
2
public boolean hasNext() {return cursor != size;}
用于判断当前操作位置是否有元素
3
public E next() {checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}
局部变量记录当前指向的位置cursor
如果i>=size抛出异常(没有这个元素)
将集合底层的数组拿过来
ConcurrentModificationException并发修改异常
将指针cursor向后移动一位,获取数组这个位置的元素,并加上一个强转。
泛型<引用数据类型>
- 在原先没有泛型,所有的添加对象默认Object类型(任意数据类型)
- 无法使用其特有的方法(相当于多态,Object类无法调用子类的特有方法)
- 泛型:是JDK5开始出现,可在编译阶段约束操作的数据类型,并进行检查。
- 格式<数据类型>
- 注意:泛型中只能使用引用数据类型
- 优点:把运行出现的问题提前至编译阶段,避免了强制类型转换出现的问题
泛型的原理
java中的范型是伪泛型:在编译过程中会出现泛型的约束但是编译结束,变成.class字节码文件
eg:在实际应用过程中,编译的过程中是与泛型类型相同,但是编译结束是默认数据类型,Object,向外拿出时要进行强转。
(泛型的擦除)
1 泛型类
public class Students<E> {private E id;private String name;}
不确定类的中的数据类型,就可以实现一个泛型类
2 泛型方法
public <K> void method(K nums){System.out.println(nums);
}
public static <T> void method2(T nums){System.out.println(nums);
}
这里的num实际上是一个数组(可以传参多个数据)
public static <T> void method2(ArrayList<T> arr,T...num){Collections.addAll(arr, num);for (int i = 0; i < num.length; i++) {arr.add(num[i]);}}
3 泛型接口
1 实现类给出具体的类型
public class a2 implements Student<Integer> {}
2 实现类延续泛型,实现类创建对象时再给出具体的类型
public class a2<E> implements List<E> {
}
泛型的继承性
泛型本省不具备继承性但是数据具备继承性。
import java.util.ArrayList;public class a2 {public static void main(String[] args) {ArrayList<Ye> arr1 = new ArrayList<>();ArrayList<Fu> arr2 = new ArrayList<>();ArrayList<Zi> arr3 = new ArrayList<>();//arr2与arr3就不符合泛型的约束条件,不符合继承性method(arr1);//method(arr2);//method(arr3);//但是集合当中的数据符合继承性arr1.add(new Ye());arr1.add(new Fu());arr1.add(new Zi());}public static void method(ArrayList<Ye> arr) {}
}
class Ye{}
class Fu extends Ye{}
class Zi extends Fu{}
1 使用泛型方法 - 可以接收任意数据类型,但是无法限制
public static<E> void method(ArrayList<E> arr) {}
2 使用泛型的通配符
方法前面不需要再次定义
public static void method(ArrayList<?> arr) {}
指定类与其所有的子类
public static void method(ArrayList<? extends Ye> arr) {}
指定类与其所有的父类
public static void method(ArrayList<? super Zi> arr) {}
----------Set
HashSet集合
哈希表是一种增删改查性能较好的数据结构
哈希表的组成:
- JDK8之前:数组+链表
- JDK之后:数组+链表+红黑树
哈希值:
- 哈希值是根据HashCode算出的int类型的整数(-2147483648-2147483647)
- 该方法写在OBJect类当中,所有对象均可调用,在大多数创建的类中都要重写hasCode
- Obj类中的比较的是地址值,重写后才会根据属性值进行赋值,便于比较。(特殊情况:哈希碰撞)
添加机制:
- 第一次添加元素,会创建一个默认长度为16的数组,默认的加载因子为0.75,数组名为table。
- 添加一个元素时,会先得到元素的hash值,然后根据hash的值并根据数组的长度运算出需要放入的索引位置。
- 判断是否为null
- 是:放入
- 否:判断是否相同(调用equals方法),相同不添加,不相同以链表形式,添加在老元素的下面,(老版本是反过来),
扩容机制:
- 初始数组长度为16,临界值为16*0.75=12
- 如果table数组使用过程中达到了临界值,数组的大小会扩容到原来的两倍-长度变为32,新的临界值为32*0.75=24.以此类推。
- 当一条链表的元素达到8时,并且table数组的大小大于等于64时,存储形式会进行优化,每个存储节点下的链表存储形式会变成红黑树
图解:
- 1:HashSet为什么存取顺序不同?
首先hashSet集合不允许重复元素,重复元素并不会重复添加,其次hashSet存储位置是根据hashCode哈希值计算出的数组固定索引位置,并不是按顺序逐个添加。
- 2:hashSet为什么没有索引?
hashSet并不是按照索引逐个添加,元素的存储位置是由哈希值决定的,而不是固定的索引,因此无法直接使用索引来访问元素。
- 3:hashSet是利用什么机制保证去重的?
使用了两个方法:equals() hashCode()
equals确保了唯一性,hashCode实现了高效的存储与检索,
TreeSet集合
=双列集合
双列集合的特点:
- 双列集合一次需要存取一对数据,分别为键和值
- 键不能重复,值可以重复
- 键和值是一一对应的,每一个键只能找到自己对应的值
- 键+值这个整体我们称之为“键值对”或者“键值对对象”---在Java中称之为“entry对象”
HashMap集合
添加原理:
- hashSet 若hashcode相同比较具体属性值 相同不放 不同放入老元素下面
- hashMap 若hashcode相同比较键的值 相同覆盖 不相同放老元素下面
- 底层原理相同,都是数组+链表+红黑树
- 同时为了保证键的唯一在定义自定义对象时也要重写equals和hashCode方法
HashMap集合的遍历方法:
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.function.Consumer;public class a4 {public static void main(String[] args) {HashMap<String, Integer> hash = new HashMap<>();hash.put("a", 1);hash.put("b", 2);hash.put("c", 3);//使用增强for//使用entrySet方法-获取键值对集合Set<Map.Entry<String, Integer>> entries = hash.entrySet();for (Map.Entry<String, Integer> entry : entries) {System.out.println(entry.getKey() + " " + entry.getValue());}//使用keySet方法--获取键值集合Set<String> strings = hash.keySet();for (String string : strings) {System.out.println(string + " " + hash.get(string));}//使用迭代器iteratorIterator<Map.Entry<String, Integer>> iterator = entries.iterator();while (iterator.hasNext()) {Map.Entry<String, Integer> entry = iterator.next();System.out.println(entry.getKey() + " " + entry.getValue());}//使用lambda表达式entries.forEach(System.out::println);entries.forEach(new Consumer<Map.Entry<String, Integer>>() {@Overridepublic void accept(Map.Entry<String, Integer> entry) {System.out.println(entry.getKey() + " " + entry.getValue());}});entries.forEach((Map.Entry<String, Integer> entry) -> System.out.println(entry.getKey() + " " + entry.getValue()));}}
运行结果:
小案例:
代码实现:
import java.util.*;public class b4 {public static void main(String[] args) {//生成一个投票信息集合ArrayListString[] arr = {"A", "B", "C", "D"};Random rand = new Random();ArrayList<String> list = new ArrayList<>();for (int i = 0; i < 80; i++) {int index = rand.nextInt(arr.length);list.add(arr[index]);}//使用HashMap的值进行计数HashMap<String,Integer> hash = new HashMap<>();for (String s : list) {if (hash.containsKey(s)) {hash.put(s, hash.get(s) + 1);} elsehash.put(s, 1);}System.out.println(hash);//统计出最长并且得到对应的Key值Set<Map.Entry<String, Integer>> entries = hash.entrySet();int max = 0;for (Map.Entry<String, Integer> entry : entries) {//max = Math.max(max, entry.getValue());max = max >entry.getValue() ? max : entry.getValue();}for (Map.Entry<String, Integer> entry : entries) {if (entry.getValue() == max){System.out.println(entry.getKey());}}}
}
运行结果:
LinkedHashMap集合
- 核心注意点就是有序(连接方式类似于双向链表)
- LinkedMap继承了HashMap的所有方法并且多了几个方法(但是性能会有所降低)
- LinkedHashMap 的常用方法:
- put(K key, V value):向哈希表中添加一个键值对,如果键已经存在,则会用新值替换旧值。
- get(Object key):获取指定 key 对应的值,如果 key 不存在,则返回 null。
- remove(Object key):删除指定 key 对应的键值对,如果 key 不存在,则不会有任何影响。
- removeEldestEntry(Map.Entry<K, V> eldest):用于实现 LRU 缓存淘汰算法,可以在子类中重写此方法,控制是否移除最旧的元素。如 果返回 true,则会移除最旧的元素,如果返回 false,则不会有任何影响。
- keySet():获取哈希表中所有键的集合。
- values():获取哈希表中所有值的集合。
- entrySet():获取哈希表中所有键值对的集合。
- clear():清空哈希表,删除所有键值对。
- size():返回哈希表中键值对的数量。
- containsKey(Object key):判断哈希表中是否包含指定的键。
- containsValue(Object value):判断哈希表中是否包含指定的值。
- clone():创建并返回一个哈希表的副本。
- isEmpty():判断哈希表是否为空。
- putAll(Map<? extends K, ? extends V> m):将指定映射中的所有映射复制到此映射中。
- forEach(BiConsumer<? super K, ? super V> action):对哈希表中的每个键值对执行指定操作。
- replaceAll(BiFunction<? super K, ? super V, ? extends V> function):使用指定的函数对哈希表中的每个键值对进行替换。#
- getOrDefault(Object key, V defaultValue):获取指定键对应的值,如果键不存在,则返回默认值。
- merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction):使用指定的函数对哈希表中的指定键的值进行合并。#
TreeMap集合
特点:
- HashMap多了一个对键值的排序功能
默认实现的是升序排序(我们实现降序排序)
这里的两个参数:
- o1是需要添加的元素(键值)
- o2使原本的元素(键值)
import java.util.*;public class c4 {public static void main(String[] args) {TreeMap<Integer,String> hash = new TreeMap<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2.compareTo(o1);}});hash.put(14,"14");hash.put(13,"13");hash.put(16,"16");hash.put(15,"15");hash.put(12,"12");System.out.println(hash);}
}
实际运用:
学生类:
要求需要重写
- equals()-确保唯一性
- hashCode()-实现高效的存储
- compareTo()-键值的比较规则进行重写
import java.util.Objects;public class SSS implements Comparable<SSS> {private String name;private int age;public SSS() {}public SSS(String name, int age) {this.name = name;this.age = age;}/*** 获取** @return name*/public String getName() {return name;}/*** 设置** @param name*/public void setName(String name) {this.name = name;}/*** 获取** @return age*/public int getAge() {return age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;SSS sss = (SSS) o;return age == sss.age && Objects.equals(name, sss.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}/*** 设置** @param age*/public void setAge(int age) {this.age = age;}public String toString() {return "SSS{name = " + name + ", age = " + age + "}";}@Overridepublic int compareTo(SSS o) {int i = this.age - o.age;i = i == 0 ? this.name.compareTo(o.name) : i;return i;}
}
测试类实现:
import java.util.Comparator;
import java.util.TreeMap;public class Tt {public static void main(String[] args) {TreeMap<SSS,String> hash = new TreeMap<>();hash.put(new SSS("anxian",19),"山东");hash.put(new SSS("anxiana",20),"山东");hash.put(new SSS("anxianb",20),"山东");hash.put(new SSS("anxianb",19),"山东");System.out.println(hash);}
}
运行结果: