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)时间复杂度内查询，有效避免Hash Collision DoS攻击。装载因子默认0.75。扩容JDK8 和 JDK7 稍微有点不一样的地方就是，Java7 是先扩容后插入新值的，Java8 先插值再扩容。
解决Hash冲突，HashMap 就是使用链地址法来解决冲突的（jdk8中采用平衡树(红黑树)来替代链表存储冲突的元素，但hash() 方法原理相同）。当两个对象的hashcode相同时，它们的bucket位置相同，碰撞就会发生。此时，可以将 put 进来的 K-V 对象插入到链表的尾部。对于储存在同一个bucket位置的链表对象，可通过键对象的equals()方法用来找到键值对。

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的优势是有序，劣势是相对读取慢。根据不同的场景选择不同的集合