嘟嘟程序猿Java学习笔记JavaSE

Java集合类

2019-05-08  本文已影响52人  与搬砖有关的日子

1、集合框架 image.png

2、HashMap的数据结构 image.png

2.1 put过程

public V put(K key, V value) {
    // 当插入第一个元素的时候，需要先初始化数组大小
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 如果 key 为 null，感兴趣的可以往里看，最终会将这个 entry 放到 table[0] 中
    if (key == null)
        return putForNullKey(value);
    // 1. 求 key 的 hash 值
    int hash = hash(key);
    // 2. 找到对应的数组下标
    int i = indexFor(hash, table.length);
    // 3. 遍历一下对应下标处的链表，看是否有重复的 key 已经存在，
    //    如果有，直接覆盖，put 方法返回旧值就结束了
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
 
    modCount++;
    // 4. 不存在重复的 key，将此 entry 添加到链表中，细节后面说
    addEntry(hash, key, value, i);
    return null;
}

步骤：
（1）判断当前桶是否为空，空的就需要初始化（resize 中会判断是否进行初始化）。
（2）根据 hash(key.hashcode)%len 定位到具体的桶中并判断是否为空，为空表明没有 Hash 冲突就直接在当前位置创建一个新桶即可。
（3）如果当前桶有值（ Hash 冲突），那么就要比较当前桶中的 key与写入的 key 是否相等（equals方法），相等就赋值给 e,在第 8 步的时候会统一进行赋值及返回。
（4）如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
（5）如果是个链表，就需要将当前的 key、value 封装成一个新节点写入到当前桶的后面（形成链表）。
（6）接着判断当前链表的大小是否大于预设的阈值，大于时就要转换为红黑树。
（7）如果在遍历过程中找到 key 相同时直接退出遍历。
（8）如果 e != null 就相当于存在相同的 key,那就需要将值覆盖。
（9）最后判断是否需要进行扩容。

2.2 HashMap何时扩容

2.3 HashMap为啥初始化容量为2的次幂

static final int hash(Object key) {
  if (key == null){
    return 0;
  }
  int h;
  h = key.hashCode()；返回散列值也就是hashcode
  return (n-1)&(h ^ (h >>> 16));
}
image.png

高16 bit 不变，低16 bit 和高16 bit 做了一个异或（得到的 hashcode 转化为32位二进制，前16位和后16位低16 bit和高16 bit做了一个异或）(n·1) & hash = -> 得到下标
H为插入元素的hashcode,length为map的容量大小。如果length为2的次幂，则length-1转化为二进制为11111…的形式，在与h的二进制与操作效率会非常快，而且不浪费空间；如果length不是2的次幂比如length为15，则length-1为14，对应的二进制为1110在与h与操作最后一位都为0，而0001,0011这样的位置都永远不会存放元素了，造成空间的浪费，更糟的是数组使用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率。

2.4 HashMap在高并发下如果没有处理线程安全会有怎样的安全隐患？

2.5 image.png

JDK8中，当同一个hash值的节点数不小于8时，将不再以单链表的形式存储了，会被调整成一颗红黑树（上图中null节点没画）。

3、ConcurrentHashmap image.png

ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承重入锁 ReentrantLock来进行加锁，所以每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。 这里根据 initialCapacity 计算 Segment 数组中每个位置可以分到的大小,如 initialCapacity 为 64，那么每个 Segment 或称之为"槽"可以分到 4 个.

4、Map遍历

for (Map.Entry<String, Object> m : map.entrySet()) {}

Iterator<Entry<String, Object>> it = map.entrySet().iterator();
while(it.hasNext()){
    Entry<String, Object> entry = it.next();
}

for (String key : map.keySet()) {
  map.get(key); 
}

5、有什么方法可以减少哈希冲突

6、拉链法导致的链表过深，为什么不用二叉查找树代替而选择红黑树？为什么不一直使用红黑树？

之所以选择红黑树是为了解决二叉查找树的缺陷：二叉查找树在特殊情况下会变成一条线性结构（这就跟原来使用链表结构一样了，造成层次很深的问题），遍历查找会非常慢。而红黑树在插入新数据后可能需要通过左旋、右旋、变色这些操作来保持平衡。引入红黑树就是为了查找数据快，解决链表查询深度的问题。我们知道红黑树属于平衡二叉树，为了保持“平衡”是需要付出代价的，但是该代价所损耗的资源要比遍历线性链表要少。所以当长度大于8的时候，会使用红黑树；如果链表长度很短的话，根本不需要引入红黑树，引入反而会慢。

7、Stream API

Java 8 中的 Stream 是对集合（Collection）对象功能的增强，它专注于对集合对象进行各种非常便利、高效的聚合操作（aggregate operation），或者大批量数据操作 (bulk data operation)。Stream API 借助于同样新出现的 Lambda 表达式，极大的提高编程效率和程序可读性。同时它提供串行和并行两种模式进行汇聚操作，并发模式能够充分利用多核处理器的优势，使用 fork/join 并行方式来拆分任务和加速处理过程。通常编写并行代码很难而且容易出错, 但使用 Stream API 无需编写一行多线程的代码，就可以很方便地写出高性能的并发程序。
当我们使用一个流的时候，通常包括三个基本步骤：
获取一个数据源（source）→ 数据转换→执行操作获取想要的结果，每次转换原有 Stream 对象不改变，返回一个新的 Stream 对象（可以有多次转换），这就允许对其操作可以像链条一样排列，变成一个管道。
流的操作类型：

上一篇 下一篇

猜你喜欢

热点阅读