集合 - 嗨吖呀
View Post
-
Collection 和 Collections
- Collection是集合类的上级接口，继承他的接口主要有Set 和List.
- Collections是针对集合类的一个帮助类，他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。
-
常用的集合
Collection 接口的接口对象的集合（单列集合）
├——List 接口：元素按进入先后有序保存，可重复
│ ├ LinkedList 接口实现类，链表，插入删除，线程不安全
│ ├ ArrayList 接口实现类，数组， 随机访问，线程不安全 （Collections.synchronizedList(new ArrayList<>())；copyOnWriteArrayList是线程安全的）
│ └ Vector 接口实现类 数组，同步，线程安全，数据增长默认一倍
│ └ Stack 是Vector类的实现类
└——Set 接口：仅接收一次，不可重复，并做内部排序
│ └HashSet 使用hash表（数组）存储元素
│ └ LinkedHashSet 链表维护元素的插入次序
└ —————TreeSet 底层实现为二叉树，元素排好序
Map 接口键值对的集合 （双列集合）
├———Hashtable 接口实现类，线程安全
├———HashMap 接口实现类，线程不安全
│ ├ LinkedHashMap 双向链表和哈希表实现
│ └ WeakHashMap
├ ——–TreeMap 红黑树对所有的key进行排序
└———IdentifyHashMap
-
ArrayList扩容机制
- 创建ArrayList对象时，若未指定集合容量，集合默认容量为0；
- 当集合对象调用add方法存储数据时，进行初始化容量为10
- 集合初始化后，再次调用add方法，先将集合扩大1.5倍，如果仍然不够，新长度为传入集合大小。并调用Arrays.copyOf方法将elementData数组指向新的长度为扩容后长度的内存空间
- 若使用addAll方法添加元素，则初始化大小为10和添加集合长度的较大值
-
数组(Array)和列表(ArrayList)的区别
- Array可以包含基本类型和对象类型，ArrayList只能包含对象类型。
- Array大小是固定的，ArrayList的大小是动态变化的。
- ArrayList提供了更多的方法和特性，比如：addAll()，removeAll()，iterator()等等。
-
ArrayList和linkedList区别
ArrayList可以看作是能够自动增长容量的数组，LinkList是一个双链表，在添加和删除元素时具有比ArrayList更好的性能。但在get方面弱于ArrayList。当然，这些对比都是指数据量很大或者操作很频繁。
- 查找时间复杂度都是O(N), 但是数组要比链表快，因为数组的连续内存, 会有一部分或者全部数据一起进入到CPU缓存, 而链表还需要在去内存中根据上下游标查找， CPU缓存比内存快太多
- 数组大小固定, 不适合动态存储、动态添加, 内存连续的地址, 可随机访问, 查询速度快
- 链表大小可变, 扩展性强, 只能顺着指针的方向查询,
速度较慢
- 使用场景：
- 如果应用程序对数据有较多的随机访问，ArrayList对象要优于LinkedList对象；
- 如果应用程序有更多的插入或者删除操作，较少的随机访问，LinkedList对象要优于ArrayList对象；
- 不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。
-
为什么重写equals还要重写hashcode？
equals()方法来自object对象，默认比较的是对象的引用是否指向同一块内存地址，重写的目的是为了比较两个对象的value值是否相等。在Object中，HashCode的计算方法是根据对象的地址进行计算的。
如果我们对一个对象重写了euqals，意思是只要对象的成员变量值都相等那么euqals就等于true，但不重写hashcode，那么我们再new一个新的对象，当原对象.equals（新对象）等于true时，两者的hashcode却是不一样的，由此将产生理解的不一致，如在存储散列集合时（如Set类），将会存储了两个值一样的对象，导致混淆，因此，就也需要重写hashcode。
为了保证这种一致性，必须满足以下两个条件：
- 当obj1.equals(obj2)为true时，obj1.hashCode() == obj2.hashCode()必须为true
- 当obj1.hashCode() == obj2.hashCode()为false时，obj1.equals(obj2)必须为false
-
HashSet如何保证元素唯一性
HashSet集合的底层数据结构是哈希表。哈希表的存储依赖两个方法：hashCode()和equals()。
- 首先判断对象的hashCode()哈希值是否相同：
- 如果不同，就直接添加到集合中。
-
如果相同，就继续执行equals()方法。
- 如果equals()方法返回true，说明元素重复，就不添加。
- 如果equals()方法返回false，说明元素没有重复，就添加到集合中。
- 如果equals()方法返回true，说明元素重复，就不添加。
-
map的分类和常见的情况
java.util.Map：它有四个实现类，分别是HashMap、Hashtable、LinkedHashMap 和TreeMap.
- Hashmap 是一个最常用的Map，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序是完全随机的。HashMap最多只允许一条记录的键为Null，允许多条记录的值为Null；HashMap不支持线程的同步，即任一时刻如果有多个线程同时写HashMap，可能会导致数据的不一致。如果需要同步，可以用 Collections.synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
- Hashtable与 HashMap类似，它继承自Dictionary类，不同的是：它不允许记录的键或者值为空；它支持线程的同步，即任一时刻只有一个线程能写Hashtable，因此也导致了 Hashtable在写入时会比较慢。
- LinkedHashMap 是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。也可以在构造时用带参数，按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度和他的容量有关。
- TreeMap实现SortMap接口，能够把它保存的记录根据键大小排序，默认是按键值的升序排序，也可以指定排序的比较器，当用Iterator 遍历TreeMap时，得到的记录是排过序的。
小结：一般情况下，我们用的最多的是HashMap，在Map中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。如果需要输出的顺序和输入的相同，那么用LinkedHashMap可以实现，它还可以按读取顺序来排列。
-
HashMap
- 哈希表：根据关键码值（key value）而直接进行访问的数据结构。也就是说，它通过关键码值映射到表中一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
- 哈希：把任意长度的输入通过哈希算法映射成固定长度的输出。
- 哈希冲突（无法避免）：计算得到的哈希值相同。
解决方法：
- 开放定址法
- 再哈希法：双哈希法计算，计算出不同的哈希值为止
- 链址法：HashMap实现方式，next指针连接Node
- 建立公共溢出区：建立基本表和溢出表，哈希值相同的直接放到溢出表
哈希算法要求：
- 高效，能够处理长文本
- 不能逆推原文
- 尽量分散，减少哈希冲突
-
HashMap
- JDK1.7：数组+链表；JDK1.8：数组+链表+红黑树（链表长度大于8且table大于64转为红黑树，红黑树节点个数小于6转为链表）
- 每个数据单元为一个Node结构，包含key，value，hash，next四个字段
- 初始长度为16，默认负载因子为0.75，当HashMap的长度达到16*0.75=12时，就会触发扩容流程，每次扩容为原来的2倍（碰撞的概率低）。
- 采用懒加载机制，即在进行put操作时才真正构建table数组。
- 允许第一个位置的key为空，允许value为空
- 线程不安全，导致cpu100%：jdk7链表成环，jdk8红黑树父子节点成环
- JDK1.7：数组+链表；JDK1.8：数组+链表+红黑树（链表长度大于8且table大于64转为红黑树，红黑树节点个数小于6转为链表）
- 红黑树（自平衡二叉查找树）特性：
- 每个结点是黑色或者红色。
- 根结点是黑色。
- 每个叶子结点（NIL）是黑色。 [注意：这里叶子结点，是指为空(NIL或NULL)的叶子结点！]
- 如果一个结点是红色的，则它的子结点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。
- HashMap的get流程：
- 首先会判断数组是否不等于null，或者数组的长度是否大于0，如果不满足，就说明HashMap里没有数据，直接返回null。
- 通过 hash & (table.length – 1)获取该key对应的数据节点的hash槽；
- 判断首节点是否为空，为空则直接返回空；
- 再判断首节点key是否和目标值相同，相同则直接返回(首节点不用区分链表还是红黑树)；如果不同，且首节点next为空，则直接返回空；
- 首节点是树形节点，则进入红黑树数的取值流程，并返回结果；
- 否则就会进入一个do while循环进行查询链表，并返回结果；
- HashMap的put流程：
- 如果table数组为空数组，进行数组填充（为table分配实际内存空间），入参为threshold
- 如果key为null时被放在了tab下标为0的位置。
- 根据hash & (table.length – 1)来确认存放的位置，如果当前位置是空直接添加到table中。
- 如果在首结点与我们待插入的元素有相同的hash和key值，则先记录。
- 如果首结点的类型是红黑树类型，则按照红黑树方法添加该元素。
- 如果首结点类型为链表类型，遍历到末尾时，先在尾部追加该元素结点。当遍历的结点数目大于8时，则采取树化结构。
- modCount++；如果集合在被遍历期间如果内容发生变化则++modCount，只能检测并发修改的bug，不能保证线程安全（ABA，祥见CAS）
- 当结点数+1大于threshold时，则进行扩容
e.hash & oldCap，就是用于计算位置b到底是0还是1用的，只要其结果是0，则新散列下标就等于原散列下标，否则新散列坐标要在原散列坐标的基础上加上原table长度。
- 当new完HashMap之后，第一次往HashMap进行put操作的时候，首先会进行扩容。
- 当HashMap的使用的桶数达到总桶数*加载因子的时候会触发扩容；
- 当某个桶中的链表长度达到8进行链表扭转为红黑树的时候，会检查总桶数是否小于64，如果总桶数小于64也会进行扩容；
- JDK1.7 先扩容后插入新节点：头插法不需要遍历扩容后的数组或者链表。
- JDK1.8 先插入后扩容：jdk8如果要先扩容，由于是尾插法，扩容之后还要再遍历一遍，找到尾部的位置，然后插入到尾部。在Node插入之后，如果当前数组位置上节点数量达到了8，先树化，然后再计算需不需要扩容，否则前面的树化可能被浪费了。
红黑树本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。能够加快检索速率。
桶中元素的插入只会在hash冲突时发生，而hash冲突发生的概率较小，一直维护一个红黑树比链表耗费资源更多，在桶中元素量较小时没有这个必要。
- HashEntry中value，以及next(链表)都是 volatile 修饰的，保证了获取时的可见性。
- 原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于
ReentrantLock。不会像HashTable那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量，默认为16)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
|
//外部类方法 public V put(K key, V value) { if (value == null) throw new NullPointerException(); int hash = hash(key.hashCode()); return segmentFor(hash).put(key, hash, value, false); //先确定段的位置 }
// Segment类中的方法 V put(K key, int hash, V value, boolean onlyIfAbsent) {
try { int c = count; // 如果当个数超过阈值，就重新hash当前段的元素 if (c++ > threshold) rehash(); HashEntry<K,V>[] tab = table; int index = hash & (tab.length – 1); HashEntry<K,V> first = tab[index]; HashEntry<K,V> e = first; while (e != null && (e.hash != hash || !key.equals(e.key))) e = e.next;
V oldValue; if (e != null) { oldValue = e.value; if (!onlyIfAbsent) e.value = value; } else { oldValue = null; ++modCount; tab[index] = new HashEntry<K,V>(key, hash, first, value); count = c; // write-volatile } return oldValue; } finally {
} } |
|
public V put(K key, V value) { return putVal(key, value, false); } final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode());// 得到 hash 值 int binCount = 0; // 用于记录相应链表的长度 for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; // 如果数组”空”，进行数组初始化 if (tab == null || (n = tab.length) == 0) // 初始化数组 tab = initTable(); // 找该 hash 值对应的数组下标，得到第一个节点 f else if ((f = tabAt(tab, i = (n – 1) & hash)) == null) { // 如果数组该位置为空，用一次 CAS 操作将新new出来的 Node节点放入数组i下标位置；如果 CAS 失败，那就是有并发操作，进到下一个循环 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } // hash 居然可以等于 MOVED==-1，这个需要到后面才能看明白，不过从名字上也能猜到，肯定是因为在扩容 else if ((fh = f.hash) == MOVED) // 帮助数据迁移，这个等到看完数据迁移部分的介绍后，再理解这个就很简单了 tab = helpTransfer(tab, f); // 到这里就是说，f 是该位置的头结点，而且不为空 else { V oldVal = null; // 获取链表头结点监视器对象
if (tabAt(tab, i) == f) { if (fh >= 0) { // 头结点的 hash 值大于 0，说明是链表 // 用于累加，记录链表的长度 binCount = 1; // 遍历链表 for (Node<K,V> e = f;; ++binCount) { K ek; // 如果发现了”相等”的 key，判断是否要进行值覆盖，然后也就可以 break 了 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } // 到了链表的最末端，将这个新值放到链表的最后面 Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { // 红黑树 Node<K,V> p; binCount = 2; // 调用红黑树的插值方法插入新节点 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } // binCount != 0 说明上面在做链表操作 if (binCount != 0) { // 判断是否要将链表转换为红黑树，临界值： 8 if (binCount >= TREEIFY_THRESHOLD) // 如果当前数组的长度小于 64，那么会进行数组扩容，而不是转换为红黑树 treeifyBin(tab, i); // 如果超过64，会转成红黑树 if (oldVal != null) return oldVal; break; } } } // addCount(1L, binCount); return null; } |
- Java 7 中，每个 Segment 独立加锁，最大并发个数就是 Segment 的个数，默认是
16。
- Java 8 中，锁粒度更细，理想情况下
table 数组元素的个数（也就是数组长度）就是其支持并发的最大个数，并发度比之前有提高。
- Java 7 采用 Segment 分段锁来保证安全，而 Segment 是继承自 ReentrantLock。
- Java 8 中放弃了Segment 的设计，采用 Node + CAS + synchronized+volatile 保证线程安全。
- HashTable
- SynchronizedMap：加了一个对象锁，每次操作hashmap都需要先获取这个对象锁
- ConcurrentHashMap：线程安全是通过cas+synchronized+volatile来实现的
- ConcurrentSkipListMap：
通过跳表来实现的高并发容器并且这个Map是有序排序的，根据key来排序，对应TreeMap
JDK 1.8 中 HashMap 和 Hashtable 主要区别如下：
- 父类不同。HashMap继承自AbstractMap；Hashtable继承自Dictionary。
- 线程安全性不同。HashMap线程不安全；Hashtable 中的方法是Synchronized的。
- HashMap最多只允许一条记录的键为Null，允许多条记录的值为 Null；Hashtable键和值都不允许为空。
- 默认初始大小和扩容方式不同。HashMap默认初始大小16，容量必须是2的整数次幂，扩容时将容量变为原来的2倍；Hashtable默认初始大小11，扩容时将容量变为原来的2倍加1。
- 迭代器不同。HashMap的Iterator是fail-fast迭代器；Hashtable还使用了enumerator迭代器。
- hash的计算方式不同。HashMap计算了hash值；Hashtable使用了key的hashCode方法。
- TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证快速检索指定节点。
- 红黑树的插入、删除、遍历时间复杂度都为O(lgN)，所以性能上低于哈希表。但是哈希表无法提供键值对的有序输出，红黑树因为是根据键值大小排序插入的，可以按照键的值的大小有序输出。
- HashMap基于散列桶（数组和链表）实现；TreeMap基于红黑树实现。
- HashMap不支持排序；TreeMap默认是按照Key值升序排序的，可指定排序的比较器，主要用于存入元素时对元素进行自动排序。
- HashMap大多数情况下有更好的性能，尤其是读数据。在没有排序要求的情况下，使用HashMap。
- 都是非线程安全。
- Iterator可用来遍历Set和List集合，但是ListIterator只能用来遍历List。
- Iterator对集合只能是前向遍历，ListIterator既可以前向也可以后向。
- ListIterator实现了Iterator接口，并包含其他的功能，比如：增加元素，替换元素，获取前一个和后一个元素的索引等等。
在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出ConcurrentModificationException。如HashMap
- 原理：迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。
- 注意：这里异常的抛出条件是检测到
modCount！=expectedmodCount
这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值（ABA问题），则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。
- 场景：java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）。
采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
- 原理：由于迭代时是对原集合的拷贝进行遍历，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发Concurrent Modification Exception。
- 缺点：基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。
- 场景：java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。
克隆(cloning)或者是序列化(serialization)的语义和含义是跟具体的实现相关的。因此，应该由集合类的具体实现来决定如何被克隆或者是序列化。