java常用集合类 Set Map

有序性:

ArrayList、LinkedList、Vector都是有序的。 Map是无序的,LinkedHashMap是有序的,通过链表链接顺序。Set是无序的,并且set中的元素不能重复,set的底层实现其实是Map,它是计算key的哈希值来确定元素在数组中的存放位置,所以是无序的,应为在Map中key的值不能重复,所以set中的元素不能重复,有HashSet、TreeSet。LinkedHashSet是有序的,其中HashSet用来保证数据唯一,List用来保证有序,就是多种数据结构组合使用,保证查找元素与插入元素的时间复杂度都是O(1)。

set是一种关联式容器,其特性如下:

  • set以RedBlackTree作为底层容器
  • 所得元素的只有key没有value,value就是key
  • 不允许出现键值重复
  • 所有的元素都会被自动排序
  • 不能通过迭代器来改变set的值,因为set的值就是键

map和set一样是关联式容器,它们的底层容器都是红黑树,区别就在于map的值不作为键,键和值是分开的。它的特性如下:

  • map以RedBlackTree作为底层容器
  • 所有元素都是键+值存在
  • 不允许键重复
  • 所有元素是通过键进行自动排序的
  • map的键是不能修改的,但是其键对应的值是可以修改的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
HashMap<Integer, Integer> m = new LinkedHashMap<Integer, Integer>(10, 0.75f, true);//10:初始大小,0.75装载因子,true获取的时候排序(false存储的时候排序会把获取过的元素链接到链表尾,获取的时候不改变顺序)
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);

m.put(3, 26);
m.get(5);

for(Map.Entry e : m.entrySet()) {
System.out.println(e.getKey() + "-" + e.getValue().toString());
}
}

HashMap

JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。JDK 1.8中如果链表长度超过阈值(static final int TREEIFY_THRESHOLD = 8;), 就把链表转成红黑树以实现时间复杂度从O(n)下降为O(logn)时间复杂度内查询。装载因子默认0.75。扩容JDK8 和 JDK7 稍微有点不一样的地方就是,Java7 是先扩容后插入新值的,Java8 先插值再扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
...
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
...
}
...
}

扩容

resize() 方法用于初始化数组或数组扩容,每次扩容后,容量为原来的 2 倍,并进行数据迁移。

并发问题分析

put
get
remove

ConcurrentHashMap

使用java.util.HashTable,效率最低。 建议使用java.util.concurrent.ConcurrentHashMap效率高。Hashtable低效主要是因为所有访问Hashtable的线程都争夺一把锁。如果容器有很多把锁,每一把锁控制容器中的一部分数据,那么当多个线程访问容器里的不同部分的数据时,线程之前就不会存在锁的竞争,这样就可以有效的提高并发的访问效率。这也正是ConcurrentHashMap使用的分段锁技术。将ConcurrentHashMap容器的数据分段存储,每一段数据分配一个Segment(锁),当线程占用其中一个Segment时,其他线程可正常访问其他段数据。

1.7

数据结构

jdk1.7中采用Segment + HashEntry的方式进行实现

ConcurrentHashMap初始化时,计算出Segment数组的大小ssize和每个Segment中HashEntry数组的大小cap,并初始化Segment数组的第一个元素;其中ssize大小为2的幂次方,默认为16,cap大小也是2的幂次方,最小值为2,最终结果根据根据初始化容量initialCapacity进行计算,其中Segment在实现上继承了ReentrantLock,这样就自带了锁的功能

整个 ConcurrentHashMap 由一个个 Segment 组成,Segment 代表”部分“或”一段“的意思,所以很多地方都会将其描述为分段锁。简单理解就是,ConcurrentHashMap 是一个 Segment 数组,Segment 通过继承 ReentrantLock 来进行加锁,所以每次需要加锁的操作锁住的是一个 segment,这样只要保证每个 Segment 是线程安全的,也就实现了全局的线程安全。
concurrencyLevel:默认是 16,也就是说 ConcurrentHashMap 有 16 个 Segments

put实现

当执行put方法插入数据时,根据key的hash值,在Segment数组中找到相应的位置,如果相应位置的Segment还未初始化,则通过CAS进行赋值,接着执行Segment对象的put方法通过加锁机制插入数据
场景:线程A和线程B同时执行相同Segment对象的put方法

1、线程A执行tryLock()方法成功获取锁,则把HashEntry对象插入到相应的位置;
2、线程B获取锁失败,则执行scanAndLockForPut()方法,在scanAndLockForPut方法中,会通过重复执行tryLock()方法尝试获取锁,在多处理器环境下,重复次数为64,单处理器重复次数为1,当执行tryLock()方法的次数超过上限时,则执行lock()方法挂起线程B;
3、当线程A执行完插入操作时,会通过unlock()方法释放锁,接着唤醒线程B继续执行;

size实现

因为ConcurrentHashMap是可以并发插入数据的,所以在准确计算元素时存在一定的难度,一般的思路是统计每个Segment对象中的元素个数,然后进行累加,但是这种方式计算出来的结果并不一样的准确的,因为在计算后面几个Segment的元素个数时,已经计算过的Segment同时可能有数据的插入或则删除先采用不加锁的方式,连续计算元素的个数,最多计算3次:
1、如果前后两次计算结果相同,则说明计算出来的元素个数是准确的;
2、如果前后两次计算结果都不同,则给每个Segment进行加锁,再计算一次元素的个数;

扩容

rehash跟HashMap的resize类似

1.8

数据结构

1.8中放弃了Segment的设计,取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现,又增加了很多辅助的类,例如TreeBin,Traverser等对象内部类。Doug Lea大神,1.8的ConcurrentHashMap有6313行代码,之前大概是1000多行。

put实现

当执行put方法插入数据时,根据key的hash值,在Node数组中找到相应的位置
1、如果相应位置的Node还未初始化,则通过CAS插入相应的数据;
2、如果相应位置的Node不为空,且当前该节点不处于移动状态,则对该节点加synchronized锁,如果该节点的hash不小于0,则遍历链表更新节点或插入新节点;
3、如果该节点是TreeBin类型的节点,说明是红黑树结构,则通过putTreeVal方法往红黑树中插入节点;
4、如果binCount不为0,说明put操作对数据产生了影响,如果当前链表的个数达到8个,则通过treeifyBin方法转化为红黑树,如果oldVal不为空,说明是一次更新操作,没有对元素个数产生影响,则直接返回旧值;
5、如果插入的是一个新节点,则执行addCount()方法尝试更新元素个数baseCount;

size实现

1.8中使用一个volatile类型的变量baseCount记录元素的个数,当插入新数据或则删除数据时,会通过addCount()方法更新baseCount
1、初始化时counterCells为空,在并发量很高时,如果存在两个线程同时执行CAS修改baseCount值,则失败的线程会继续执行方法体中的逻辑,使用CounterCell记录元素个数的变化;
2、如果CounterCell数组counterCells为空,调用fullAddCount()方法进行初始化,并插入对应的记录数,通过CAS设置cellsBusy字段,只有设置成功的线程才能初始化CounterCell数组
3、如果通过CAS设置cellsBusy字段失败的话,则继续尝试通过CAS修改baseCount字段,如果修改baseCount字段成功的话,就退出循环,否则继续循环插入CounterCell对象;
4、通过累加baseCount和CounterCell数组中的数量,即可得到元素的总个数;

扩容

tryPresize
transfer

LinkedHashSet

LinkedHashSet是有序的,其中HashSet用来保证数据唯一,List用来保证有序,就是多种数据结构组合使用,保证查找元素与插入元素的时间复杂度都是O(1)
线程安全实现:Collections.synchronizedSet(new LinkedHashSet());

TreeSet

  • TreeSet底层是二叉树
  • TreeSet中的元素必须实现Comparable接口并重写compareTo()方法,TreeSet判断元素是否重复 、以及确定元素的顺序靠的都是这个方法。如String,Integer等已经实现了Comparable接口
  • 依赖TreeMap
  • 相对HashSet,TreeSet的优势是有序,劣势是相对读取慢。根据不同的场景选择不同的集合