详情页模板哪个网站好,行情软件哪个好用,全国文明城市创建标准,百度推广网站吸引力文章目录一 简介二 底层数据结构总结1 List2 Set3 Queue4 Map三 Collection 的子接口 List1 ArrayList 与 Vector2 ArrayList 与 LinkedList3 ArrayList 的 JDK 7/8 差异4 ArrayList 的构造方法与扩容机制*四 Collection 的子接口 Set1 HashSet、LinkedHashSet 和 TreeSet2 Has…
文章目录一 简介二 底层数据结构总结1 List2 Set3 Queue4 Map三 Collection 的子接口 List1 ArrayList 与 Vector2 ArrayList 与 LinkedList3 ArrayList 的 JDK 7/8 差异4 ArrayList 的构造方法与扩容机制*四 Collection 的子接口 Set1 HashSet、LinkedHashSet 和 TreeSet2 HashSet / HashMap 加入实例时查重的方式**五 Collection 的子接口 Queue1 Queue 与 Deque2 PriorityQueue【Java堆实现】3 ArrayDeque 与 LinkedList【Java栈和队列实现】六 Collection 的子接口 Map1 HashMap 和 Hashtable2 HashMap 的长度为什么是 2 的幂次方3 ConcurrentHashMap 和 Hashtable4 为什么JDK1.8的 ConcurrentHashMap 使用 CASSynchronized 代替 Segment*5 CAS (Compare And Swap)6 JDK8 相较于 JDK7 在底层实现方面的不同7 HashMap 底层实现的参数9 JDK 8 HashMap 的扩容七 Iterator1 类与接口2 只读使用方法3 迭代的问题在循环中增加或删除元素八 Collections 工具类1 对传入的容器接口对象进行操作查找/替换/排序/添加/修改2 返回一个容器接口对象一 简介
Java容器可大致分为 List、Queue、Set、Map 四种。
List存储的元素是有序的、可重复的Set存储的元素是无序的、不可重复的Queue按特定的排队规则来确定先后顺序存储的元素是有序的、可重复的Map使用键值对key-value存储类似于数学上的函数 yf(x)“x” 代表 key“y” 代表 valuekey 是无序的、不可重复的value 是无序的、可重复的每个键最多映射到一个值 二 底层数据结构总结
1 List
类数据结构备注ArrayListObject[]VectorObject[]LinkedList双向链表JDK1.6 之前为循环链表JDK1.7 取消了循环常用的Java栈、队列实现
栈采用 LinkedList 或 ArrayDeque 的 Deque双端队列接口队列使用 LinkedList 的 Queue 接口栈和队列都是双端队列的特殊情况
// LinkedList节点被定义为私有的静态内部类
private static class NodeE {E item;NodeE next;NodeE prev;
}2 Set
Set 是 Map 的特殊形式只有 key 有意义其 value 均为相同的固定值
类数据结构备注HashSetHashMap存储的元素无序LinkedHashSetLinkedHashMap存储的元素可以选择按插入顺序或访问顺序排序默认是插入顺序TreeSetTreeMap存储的元素有序
3 Queue
类数据结构备注PriorityQueueObject[] 实现二叉堆存储的元素按照指定的权值和顺序组织首个元素有序其它元素无序常用的Java堆实现ArrayDequeObject[] 双指针
4 Map
类数据结构备注HashMap数组链表/红黑树存储的元素无序LinkedHashMap数组链表/红黑树且 Entry 存在双向的引用存储的元素可以选择按插入顺序或访问顺序排序TreeMap红黑树自平衡的排序二叉树存储的元素有序HashTable数组链表存储的元素无序
HashMap JDK1.8 之前 HashMap 由 数组链表 组成的数组是 HashMap 的主体链表则是主要为了使用拉链法解决哈希冲突而存在的JDK1.8 以后当链表长度大于阈值默认为 8且键值对个数大于64时将链表转化为红黑树以减少搜索时间如果键值对个数小于 64那么会选择先进行数组扩容而不是转换为红黑树相较于 AVL 树红黑树减弱了对平衡的要求降低了保持平衡需要的开销
// HashMap数据结构
class HashMapK, V extends ... {EntryK, V[] table;int size; // 键值对个数int threshold; // 扩容阈值 table.length * loadFactorfloat loadFactor; // 负载因子默认0.75// HashMap Entrystatic class EntryK, V implements Map.EntryK, V {K key;V value;EntryK, V next; // 用于拉链法解决哈希冲突int hash; // key哈希值}
}LinkedHashMap 继承自 HashMap所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成每个 Entry 增加了双向引用构成一条双向链表可以 保持键值对的插入顺序或访问顺序访问顺序指的是对一个 key 执行 put/get 后将键值对移动到链表末尾便于实现 LRU指定按访问顺序组织链表需要调用构造方法 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 并指定 accessOrder true TreeMap 存放的元素必须是全序的构造时元素需要实现 Comparable 接口或者指定 Comparator迭代时输出按键排序
// TreeMap数据结构
class TreeMapK, V extends... {Comparator? super K comparator;EntryK, V root;int size;// TreeMap Entry红黑树节点static final class EntryK, V implements Map.EntryK, V {K key;V value;EntryK, V left;EntryK, V right;EntryK, V parent;boolean color; // 标志节点红或黑}
}*三 Collection 的子接口 List
1 ArrayList 与 Vector
ArrayList 和 Vector 的底层都是 Object[] 存储的即对数组进行封装ArrayList 是 List 的主要实现类适用于频繁的查找工作线程不安全Vector 是 List 的古老实现类线程安全
2 ArrayList 与 LinkedList
都是线程不安全的ArrayList 底层使用 Object[] 存储支持随机访问LinkedList 使用双向链表存储不支持随机访问ArrayList 的空间浪费主要体现在列表的结尾会预留一定的容量空间而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间因为要存放直接后继和直接前驱以及数据获取/插入/删除元素的时间复杂度不同体现在数组与链表的区别
3 ArrayList 的 JDK 7/8 差异
JDK 7ArrayList 的对象的创建类似于单例的饿汉式
ArrayList list new ArrayList();//底层创建了长度是*10*的Object[]数组elementData
list.add(123);//elementData[0] new Integer(123);
list.add(11);//如果此次的添加导致底层elementData数组容量不够则扩容。/*
默认情况下扩容为原来的容量的1.5倍同时需要将原有数组中的数据复制到新的数组中。
结论建议开发中使用带参的构造器ArrayList list new ArrayList(int capacity)
*/JDK 8 ArrayList 的对象的创建类似于单例的懒汉式延迟了数组的创建节省内存
ArrayList list new ArrayList(); // 底层Object[] elementData初始化为{}.并没有创建长度为10的数组
list.add(123); // 第一次调用add()时底层才创建了长度10的数组并将数据123添加elementData[0]
// 后续的添加和扩容操作与jdk 7 无异4 ArrayList 的构造方法与扩容机制*
参考链接
三种构造方法无参、传入指定长度、传入 Collection
// 属性
private static final int DEFAULT_CAPACITY 10; // 默认的容量大小常量
private static final Object[] EMPTY_ELEMENTDATA {}; // 定义的空数组final修饰大小固定为0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {}; // 定义的默认空容量的数组final修饰大小固定为0
transient Object[] elementData; // 定义的不可被序列化的数组实际存储元素的数
private int size; // 数组中元素的个数// 无参的构造方法容量此时是0元素个数size为默认值0public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // 只有调用无参构造器才会获得 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
}// 传容量的构造方法initialCapacity 0时容量为initialCapacity元素个数size为默认值0
initialCapacity 0时容量为0元素个数size为默认值0
initialCapacity 0时抛出异常public ArrayList(int initialCapacity) {if (initialCapacity 0) {this.elementData new Object[initialCapacity];} else if (initialCapacity 0) {this.elementData EMPTY_ELEMENTDATA; // 调用有参构造器传入0获得EMPTY_ELEMENTDATA区别于无参构造器} else {throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}
}// 传入Collection元素列表的构造方法如果传入的Collection不包含元素容量是0元素个数size为0
如果传入的Collection包含元素容量为传入序列的长度元素个数size也为序列长度此时的ArrayList是满的public ArrayList(Collection? extends E c) {// 将列表转化为对应的数组elementData c.toArray();if ((size elementData.length) ! 0) {// 原对象数组的数组类型转化为 Object对象数组的数组类型if (elementData.getClass() ! Object[].class)elementData Arrays.copyOf(elementData, size, Object[].class);} else {// 赋予空数组this.elementData EMPTY_ELEMENTDATA;}
}扩容add grow
// 单参数的add方法用户使用的方法
public boolean add(E e) {modCount;add(e, elementData, size);return true;
}// 重载的多参数add方法
private void add(E e, Object[] elementData, int s) {// 判断元素个数是否等于当前容量如果相等则调用无参的grow方法if (s elementData.length)elementData grow();elementData[s] e;size s 1;
}// 无参的grow方法
private Object[] grow() {return grow(size 1); // 传递参数为需求的最小容量也就是当前容量1
}// 重载的有参grow方法if语句中不会处理 用默认 __无参构造方法__ 创建的数组的 __初始扩容__ 情况其余扩容情况都是由if语句处理ArraysSupport.newLength函数的作用是创建一个大小为oldCapacity max(minimum growth preferred growth)的数组
minCapacity是传入的参数上面显示它的值是当前容量1那么minCapacity - oldCapacity的值就恒为1minimum growth的值也就恒为1
oldCapacity 1 右移一位也就是减半preferred growth的值即为oldCapacity大小的一半当oldCapacity为0时右移后还是0private Object[] grow(int minCapacity) {// 当前容量int oldCapacity elementData.length;// 如果当前容量大于0 或者 数组不是DEFAULTCAPACITY_EMPTY_ELEMENTDATA创建时调用的是无参构造器if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* 最小增长量 */oldCapacity 1 /* 倾向增长量 */);return elementData Arrays.copyOf(elementData, newCapacity);// 如果 数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA容量等于0的话只剩这一种情况了} else {return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}
}容量增加 1 的情况 原来的容量为 0而且是有参构造器创建的 ArrayList传入 0 或者是空 Collection 不能是无参构造器创建 容量变为原来1.5倍的情况 原来的容量大于 0 容量变为 max(DEFAULT_CAPACITY, minCapacity) 的情况 原来的容量为 0而且是无参构造器创建的 ArrayList其中 DEFAULT_CAPACITY 10用默认无参构造方法创建的数组在添加元素前ArrayList 的容量为0添加一个元素后ArrayList 的容量就变为 10 四 Collection 的子接口 Set
1 HashSet、LinkedHashSet 和 TreeSet
HashSet 底层数据结构是 HashMap LinkedHashSet 底层数据结构是 LinkedHashMap元素的插入和取出顺序满足 FIFO 或 LRU是 HashSet 的子类在添加数据的同时每个 Entry 还维护了两个引用记录此数据前一个数据和后一个数据对于频繁的遍历操作LinkedHashSet 效率高于 HashSet TreeSet 底层数据结构是 TreeMap元素是有序的排序的方式有自然排序和定制排序比较两个对象是否相同的标准为compare() 返回 0而不再是 equals()不能放入无法排序的对象 使用场景 都不是线程安全的HashSet 用于不需要保证元素插入和取出顺序的场景LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 或 LUR 的场景TreeSet 用于支持对元素自定义排序规则的场景 // TreeSet的自定排序TreeMap同理public void test2(){Comparator com new Comparator() {Overridepublic int compare(Object o1, Object o2) {// 定制比较方法...} else {// 类型不匹配...}}};TreeSet set new TreeSet(com);}2 HashSet / HashMap 加入实例时查重的方式**
当对象加入 HashSet 时HashSet 会先计算对象的 hashcode值来判断对象加入的位置 如果该位置无对象则 HashSet 中无重复元素加入成功如果该位置有对象下标相同的两个对象 hashcode不一定相同与相同位置的其他的对象的 hashcode 值作比较 如果没有相符的 hashcode则无重复元素加入成功有相同 hashcode 值的对象这时会调用 equals() 方法来检查 hashcode 相等的对象是否真的相同如果两者相同HashSet 就不会让加入操作成功 public void test3(){HashSet set new HashSet();Person p1 new Person(1001,AA);Person p2 new Person(1002,BB);set.add(p1);set.add(p2);System.out.println(set);p1.name CC;set.remove(p1);System.out.println(set); // BB, CCset.add(new Person(1001,CC));System.out.println(set); // BB, CC, CCset.add(new Person(1001,AA));System.out.println(set); // BB, CC, CC, AA}五 Collection 的子接口 Queue
1 Queue 与 Deque Queue 是单端队列只能从一端插入元素另一端删除元素实现上一般遵循 FIFO 规则 Queue 的两套方法 Deque 是双端队列在队列的两端均可以插入或删除元素 Deque 的两套方法
2 PriorityQueue【Java堆实现】
PriorityQueue 利用了二叉堆的数据结构来实现的底层使用可变长的数组来存储数据PriorityQueue 通过堆元素的上浮和下沉实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。PriorityQueue 是非线程安全的且不支持存储无法比较的对象PriorityQueue 同样要求元素实现 Comparable 接口或传入 Comparator 对象遍历输出时只有首个元素是有序的
3 ArrayDeque 与 LinkedList【Java栈和队列实现】
ArrayDeque 和 LinkedList 都实现了 Deque 接口两者都具有双端队列的功能可以实现栈和队列ArrayDeque 是基于可变长的数组和双指针来实现而 LinkedList 则通过链表来实现ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1) 虽然 LinkedList 不需要扩容但是每次插入数据时需要申请空间均摊性能相比更慢从性能的角度上选用 ArrayDeque 来实现队列要比 LinkedList 更好 六 Collection 的子接口 Map
1 HashMap 和 Hashtable
Hashtable 线程安全内部的方法基本都经过 synchronized 修饰不允许有 null 键和 null 值否则会抛出 NullPointerException创建时如果给定了容量初始值会直接使用给定的大小基本被淘汰不要在代码中使用它 HashMap 非线程安全可以存储 null 的 key 和 value但 null 作为键只能有一个null 作为值可以有多个总是使用 2 的整数次幂作为数组长度创建时如果给定了容量初始值会将其扩充为 2 的幂次方大小
2 HashMap 的长度为什么是 2 的幂次方
Hash 值的范围值-2147483648 到 2147483647前后加起来大概 40 亿的映射空间只要哈希函数映射得比较均匀松散一般应用是很难出现碰撞的问题是一个 40 亿长度的数组内存是放不下的用之前还要先做对数组的长度取模运算得到的余数才能用来要存放的位置也就是对应的数组下标位运算比求模更高效hash%length hash(length-1) 的前提是 length 是 2 的整数次幂
3 ConcurrentHashMap 和 Hashtable
均线程安全数据结构
类型数据结构使用的锁ConcurrentHashMap JDK1.7Segment 数组 HashEntry 数组 链表Segment本质是 ReentrantLock每次锁若干 HashEntryConcurrentHashMap JDK1.8Node 数组 链表/红黑树synchronized每次锁一个 NodeHashtable数组链表synchronized每次锁全表
在 JDK1.7 的时候ConcurrentHashMap 采用分段锁机制对整个桶数组进行了分割分段Segment每个 Segment 都是一个可重入锁每一个 Segment 只锁容器其中一部分数据多线程访问容器里不同数据段的数据不会存在锁竞争提高并发访问率
static class SegmentK,V extends ReentrantLock implements Serializable {...}JDK1.8 的时候已经摒弃了 Segment 的概念synchronized 只锁定当前链表或红黑二叉树的首节点并发控制使用 synchronized 和 CAS 来操作 虽然在 JDK1.8 中还能看到 Segment 的数据结构但是已经简化了属性只是为了兼容旧版本 Hashtable(同一把锁) 使用 synchronized 来保证线程安全效率非常低下 当一个线程访问同步方法时其他线程也访问同步方法可能会进入阻塞或轮询状态如使用 put 添加元素另一个线程不能使用 put 添加元素也不能使用 get竞争会越来越激烈效率越低 4 为什么JDK1.8的 ConcurrentHashMap 使用 CASSynchronized 代替 Segment* Segment 数组本质上是 ReentrantLock 的数组其中的每一个 ReentrantLock 锁的是 HashEntry 数组的若干个位置 Synchronized 在优化后有偏向锁、轻量级锁和重量级锁三个等级 如果把每个 ReentrantLock 锁的范围细化为一个位置是否能与 synchronized 锁一个位置的效果相同答案是否定的 锁被细化到一个哈希桶出现并发争抢的可能性就很低了。对于一个哈希桶在没有多线程竞争时使用 Synchronized 的偏向锁机制的效率是最高的出现争抢时Synchronized 轻量级锁具有自旋机制避免线程状态切换引起的开销而 ReentrantLock 倾向于将获取不到锁的线程挂起
5 CAS (Compare And Swap)
V要更新的变量(var) E预期值(expected) N新值(new)
比较并交换的过程判断V是否等于E如果等于将V的值设置为N如果不等说明已经有其它线程更新了V则当前线程放弃更新什么都不做当多个线程同时使用CAS操作一个变量时只有一个会胜出并成功更新其余均会失败但失败的线程并不会被挂起仅是被告知失败并且允许再次尝试当然也允许失败的线程放弃操作
6 JDK8 相较于 JDK7 在底层实现方面的不同
new HashMap()时底层没有创建数组首次调用 put() 方法时底层创建长度为16的数组JDK7 底层结构是 HashEntry 数组链表JDK8 中底层结构Node 数组 链表 / 红黑树数组元素类型的改变是因为支持了链表转红黑树 当数组的某一个索引位置上的元素以链表形式存在的数据个数 8 且当前键值对个数 64时此时此索引位置上的所数据改为使用红黑树存储
7 HashMap 底层实现的参数
DEFAULT_INITIAL_CAPACITY : HashMap的默认容量16DEFAULT_LOAD_FACTORHashMap的默认装载因子0.75是对空间和时间效率的一个平衡选择threshold扩容的临界值数值上等于 容量*填充因子16 * 0.75 12TREEIFY_THRESHOLDBucket中链表长度大于该默认值转化为红黑树默认8MIN_TREEIFY_CAPACITY桶中的Node被树化时最小的hash表容量默认64
9 JDK 8 HashMap 的扩容
HashMap 的数组长度一定是 2 的幂次目的是方便计算哈希值对数组长度取模HashMap 只有在插入元素时才会初始化创建长为16的 Node 数组或者扩容 具体地扩容还要满足两个条件之一 当前存入数据大于阈值存入数据到某一条链表时该链表数据个数大于 8且键值对个数小于 64 扩容的具体操作 将 Node 数组长度变为原来的 2 倍调整原数据在新数组中的索引调用 resize 方法根据原来的 hash 值新增的 bit 是0还是10索引不变1原来的索引 原来哈希表的长度 七 Iterator
1 类与接口
Iterable 接口有方法 iterator() 返回 Iterator 对象使用该对象的方法进行遍历对象实现了 Iterable就可以使用 for each 语法不实现 Iterable 的类也可以创建 Iterator 对象
public interface IterableT {/*** 获取迭代器**/IteratorT iterator();
}public interface Iterator() {/*** 是否有下个元素**/boolean hasNext();/*** 迭代器游标下移并返回指向的元素**/E next();/*** 删除最后返回的元素**/void remove();
}2 只读使用方法 Iterator iterator coll.iterator();while(iterator.hasNext()){// next():①指针下移 ②将下移以后集合位置上的元素返回System.out.println(iterator.next());}3 迭代的问题在循环中增加或删除元素
只能使用 Iterator因为迭代器内部会维护一些索引位置相关的数据迭代过程中容器不能发生结构性变化否则这些数据会失效如果还未调用 next() 或在上一次调用 next() 方法之后已经调用了 remove() 方法再调用 iterator.remove() 都会抛出 IllegalStateExceptioniterator 调用的 remove() 和集合对象的 remove() 不同 // 删除集合中TomIterator iterator coll.iterator();while (iterator.hasNext()){Object obj iterator.next();if(Tom.equals(obj)){iterator.remove();}}八 Collections 工具类
核心思想是面向接口编程Collections 提供了很多针对容器接口的通用算法和功能只要实现了指定接口就能调用其中的功能提供的功能大概分为如下两类
1 对传入的容器接口对象进行操作查找/替换/排序/添加/修改
// 二分查找
public static T int binarySearch(List? extends Comparable? super T list, T key);
public static T int binarySearch(List? extends T list, T key, Comparator? super T c);// 查找元素出现的次数
public static int frequency(Collection? c, Object o);// 最大值/最小值
...2 返回一个容器接口对象
两种情况
适配器将其它类型的数据转换成容器接口对象输入其它类型输出容器
// 1.空容器方法返回静态不可变的空容器接口对象只读用于节省创建新对象的开销
public static final T ListT emptyList();
public static final T SetT emptySet();
public static final K, V MapK, V emptyMap();
public static T IteratorT emptyIterator();// 2.单一对象方法将一个单独的对象转换为不可变的容器接口对象同样只读
public static T SetT singleton(T o);
public static T ListT singletonList(T o);
public static K, V MapK, V singletonMap(K key, V value);装饰器修饰给定的容器接口对象对其增强输入容器输出容器
// 1.写安全将修改容器的方法重写为抛出异常返回只读容器
public static T CollectionT unmodifiableCollection(Collection? extends T c);
public static T ListT unmodifiableList(List? extends T list));
public static T SetT unmodifiableSet(Set? extends T set));
public static K, V MapK, V unmodifiableMap(Map? extends K, ? extends V m);// 2.类型安全在泛型失效的情况下和老版本JDK代码交互时确保容器元素类型正确
public static E ListE checkedList(ListE list, ClassE type);
...// 3.线程安全向方法加锁使容器变成线程安全的不推荐使用
public static T ListT synchronizedList(ListT list));
...
