集合

作者: 吃火锅只蘸麻酱 | 来源:发表于2021-05-12 19:08 被阅读0次

我的Swift的学习总结 -->第二周
markdown 测试
kotlin学习第五天:集合,高阶函数,Lambda表达式
kotlin练习 ---- 集合练习
集合总结
映射、元组、集合
16.Collection集合
集合与有序集合
python入坑第八天|集合
集合框架

hashmap

构造函数（四种）

        //1.无参构造,初始化填充因子=0.75,此时table=null,threshold=0,size=0
        HashMap<String, Integer> map = new HashMap<>();
        //2.采用此构造函数,初始化填充=0.75(默认),计算threshold为最小的2^n=1,table=null,size=0
        HashMap<String, Integer> map1 = new HashMap<>(1);
        //3.采用此构造函数,初始化填充=0.75(默认),计算threshold为最小的2^n=2,table=null,size=0
        // Note:此处的threshold是虚假阈值，因为在第一次加元素的时候，会经历
        // 一.table = threshold = 2   二.threshold=(int)2*0.75=1
        HashMap<String, Integer> map2 = new HashMap<>(2);
        //4.采用此构造函数,初始化填充=0.75,计算threshold为最小的2^n=8,table=null,size=0
        // Note:此处的threshold是虚假阈值，因为在第一次加元素的时候，会经历
        // 一.table = threshold = 8   二.threshold=(int)8*0.75=6   构造以此类推
        HashMap<String, Integer> map3 = new HashMap<>(5,0.75f);
        //5.采用此构造函数,传入(实际长度)size>0才进行下一步操作,计算threshold=0,table=null,size=0
        HashMap<String, Integer> map4 = new HashMap<>(map);
        //6.无参构造的map会在第一次添加元素的时候进行扩容,table=16(默认),threshold=12(16*0.75),size=1(实际个数)
        map.put("zzh", 66);
        //7.此时size=1>0,
        // 初始threshold = map.size() / 0.75 + 1 = 2,table=0,size=0
        // 然后添加map中的元素，这里是一个元素，需要扩容一次
        // 计算一、table = threshold = 2, 二、计算threshold = (int)2 *0.75 = 1,size=1
        HashMap<String, Integer> map5 = new HashMap<>(map);
        map.put("ghh", 66);
        //8.此时size=1>0,计算threshold为最小的2^n=3,table=4,size=2
        //经历 一.ft = map.size() / 0.75 + 1 = 3 ,threshold = tableSizeFor(ft) = 4, table=0,size=0
        //    二.扩容table=4 threshold=3
        HashMap<String, Integer> map6 = new HashMap<>(map);
        //9.此时加入一个元素,进行实际的扩容操作,threshold=1,table=2,size=1
        map1.put("ghh",66);
        //10.此时加入一个元素,进行实际的扩容操作,threshold=1,table=2,size=1
        map2.put("ghh",66);
        //11.此时加入一个元素,进行实际的扩容操作,threshold=6,table=8,size=1
        map3.put("ghh",66);

        //利用反射进行验证threshold
        Field f = HashMap.class.getDeclaredField("threshold");
        f.setAccessible(true);
        Object m = f.get(map);
        System.out.println("1.threshold: " + m);
        System.out.println("1.size: " + map.size());

put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
      ---
      ---
}

putVal操作

get

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
      ---
      ---
}

getNode操作

resize
进行扩容，会伴随着一次重新 hash 分配，并且会遍历 hash 表中所有的元素，是非常耗时的。在编写程序中，要尽量避免 resize。

resize操作

Note:
1. resize（）函数在size　> threshold时被调用。
        oldCap大于 0 代表原来的 table 表非空， oldCap 为原表的大小，
        oldThr（threshold） 为 oldCap × load_factor

2. resize（）函数在table为空被调用。
        oldCap 小于等于 0 且 oldThr 大于0，代表用户创建了一个 HashMap，但是使用的构造函数为
        HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)
        或 HashMap(Map<? extends K, ? extends V> m)，导致 oldTab 为 null，oldCap 为0，
        oldThr 为用户指定的 HashMap的初始容量。

3. resize（）函数在table为空被调用。
        oldCap 小于等于 0 且 oldThr 等于0，用户调用 HashMap()构造函数创建的　HashMap，所有值均采用默认值，
        oldTab（Table）表为空，oldCap为0，oldThr等于0

4. 通过((e.hash & oldCap) == 0)来判断新链表位置
        这个地方很巧妙，直接通过e.hash & oldCap得出e在newTab中的位置；
        因为table是2倍扩容，所以只需要看hash值与oldCap进行与操作，结果为0，
        那么还是原来的index；否则index = index + oldCap
        通过与元素的hash值进行与操作，能够快速定位到数组下标
        相对于取模运算，直接进行与操作能提高计算效率。
        在CPU中，所有的加减乘除都是通过加法实现的，而与操作时CPU直接支持的。扩容时简化计算数组下标的计算量
        因为数组每次扩容都是原来的两倍，所以每一个元素在新数组中的位置要么是原来的index，要么index = index + oldCap
        最后把生成的链表添加到newTab对应位置上

5. 扩容的时候某一桶中节点数大于等于8，然后进行判断链表长度是否小于64，如果大于等于64则转换成红黑树
6. 红黑树退化有两种情况会触发：
    resize()时：红黑树拆分成的 lo 和 hi 两颗红黑树，每一颗树的结点数小于等于临界值 6 时退化成链表。
    remove( )时 ：在removeTreeNode( ) 方法会检查红黑树是否满足退化条件，与结点数无关。如果红黑树根 
                 root 为空，或者 root 的左子树/右子树为空，root.left.left 根的左子树的左子树为空，
                 都会发生红黑树退化成链表。