关于java:Java3集合框架

一、思维导图

Java 汇合框架.xmind

二、知识点及实际

2.1、Collection

1. List

列表（元素有序并且能够反复的汇合，被称为序列）

  1. ArrayList

• 排列有序，可反复
• 底层应用数组
• 查问快，增删慢
• 线程不平安
• 当容量不够时，ArrayList 是以后容量 *1.5+1

  2. LinkedList

• 排列有序，可反复
• 底层应用双向循环链接数据结构
• 查问慢，增删快
• 线程不平安

  3. Vector

• 排列有序，可反复
• 底层应用数组
• 查问快，增删慢
• 线程平安，效率低

• 当容量不够时，Vector 是以后容量 1

  4. Stack
• 栈是 Vector 的一个子类，它实现了一个规范的后进先出的栈

2. Set

汇合（不能退出反复元素，无序）

  1. HashSet

• 排列无序，不可反复
• 底层应用 Hash 表实现
• 存取速度快
• 外部是 HashMap

public class SetData {public static void main(String[] args) {List<String> list = List.of("a", "b", "c", "a");
        Set<String> stringSet = new HashSet<>();
        stringSet.addAll(list);

        // 输入 Set 汇合
        stringSet.forEach(System.out::println);


        SortedSet<String> strings = new TreeSet<>(Set.of("a", "b", "c", "d", "e", "f"));
        SortedSet<String> subSet = strings.subSet("aa", "d");
        System.out.println("sub set =" + subSet);


        List<String> strings1 = new ArrayList<>(Arrays.asList("0", "1", "2", "3", "4"));
        List<String> immutableStrings = Collections.unmodifiableList(strings1);
        System.out.println(immutableStrings);
        strings.add("5");
        System.out.println(immutableStrings);

    }
}

  2. TreeSet

• 排列无序，不可反复
• 底层应用二叉树实现
• 排序存储
• 外部是 TreeMap 的 SortedSet

  3. LinkedHashSet

• 采纳 hash 表存储，并用双向链表记录插入程序
• 外部是 LinkedHashMap

3. Queue

在两端出入的 List，所以也能够用数组或链表来实现

2.2、Map

1. HashMap

• Map 提供了一种映射关系，其中的元素是以键值对（key-value）的模式存储的，可能实现依据 key 疾速查找 value
• Map 中的键值对以 Entry 类型的对象实例模式存在
• 键（key 值）不可反复，value 值能够
• 每个建最多只能映射到一个值
• Map 接口提供了别离返回 key 值汇合、value 值汇合以及 Entry（键值对）汇合的办法
• Map 反对泛型，模式如：Map<K,V>

Map<Integer, String> map = new HashMap<>();

map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
map.put(4, "four");
map.put(5, "five");
map.put(6, "six");

Set<Integer> keys = map.keySet();
System.out.println("keys =" + keys);

Collection<String> values = map.values();
System.out.println("values =" + values);

Set<Map.Entry<Integer, String>> entries = map.entrySet();
System.out.println("entries =" + entries);

// lambda 表达式写法
map.forEach((k, v)-> System.out.println("key =" + k + ", value =" + v));

map.replaceAll((k,v)->v.toUpperCase());
map.forEach((k, v)-> System.out.println("key =" + k + ", value =" + v));

2. HashTable

• 键不可反复，值可反复
• 底层哈希表
• 线程平安
• key、value 都不容许

3. TreeMap

• 键不可反复，值能够反复
• 底层二叉树

2.3、工具类

1. Iterator 迭代器
2. Enumeration 枚举类
3. Arrays
4. Collections

三、相干扩大

3.1、HashMap 工作原理及实现

3.1.1、概述

什么时候会应用 HashMap？他有什么特点？你晓得 HashMap 的工作原理吗？你晓得 get 和 put 的原理吗？equals()和 hashCode()的都有什么作用？你晓得 hash 的实现吗？为什么要这样实现？如果 HashMap 的大小超过了负载因子 (load factor) 定义的容量，怎么办？

public static void main(String[] args) {HashMap<String, Integer> map = new HashMap<String, Integer>();
    map.put("语文", 1);
    map.put("数学", 2);
    map.put("英语", 3);
    map.put("历史", 4);
    map.put("政治", 5);
    map.put("天文", 6);
    map.put("生物", 7);
    map.put("化学", 8);
    for (Entry<String, Integer> entry : map.entrySet()) {System.out.println(entry.getKey() + ":" + entry.getValue());
    }

}

3.1.2、两个重要的参数

在 HashMap 中有两个很重要的参数，容量 (Capacity) 和负载因子 (Load factor)
简略的说，Capacity 就是 bucket 的大小，Load factor 就是 bucket 填满水平的最大比例。如果对迭代性能要求很高的话不要把 capacity 设置过大，也不要把 load factor 设置过小。当 bucket 中的 entries 的数目大于 capacity*load factor 时就须要调整 bucket 的大小为以后的 2 倍。
Initial capacity The capacity is the number of buckets in the hash table, The initial capacity is simply the capacity at the time the hash table is created.Load factor The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.

3.1.3、put 函数的实现

put 函数大抵的思路为：对 key 的 hashCode()做 hash，而后再计算 index; 如果没碰撞间接放到 bucket 里；
如果碰撞了，以链表的模式存在 buckets 后；如果碰撞导致链表过长 (大于等于 TREEIFY_THRESHOLD)，就把链表转换成红黑树；
如果节点曾经存在就替换 old value(保障 key 的唯一性)如果 bucket 满了(超过 load factor*current capacity)，就要 resize。

public V put(K key, V value) {// 对 key 的 hashCode()做 hash
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;
    // tab 为空则创立
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算 index，并对 null 做解决
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 节点存在
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
            // 该链为树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 该链为链表
        else {for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 写入
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 超过 load factor*current capacity，resize
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3.1.4、get 函数的实现

在了解了 put 之后，get 就很简略了。大抵思路如下：bucket 里的第一个节点，间接命中；如果有抵触，则通过 key.equals(k)去查找对应的 entry 若为树，则在树中通过 key.equals(k)查找，O(logn)；若为链表，则在链表中通过 key.equals(k)查找，O(n)。具体代码的实现如下

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) {Node<K, V>[] tab;
    Node<K, V> first, e;
    int n;
    K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 间接命中
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 未命中
        if ((e = first.next) != null) {
            // 在树中 get
            if (first instanceof TreeNode)
                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
            // 在链表中 get
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

3.1.5、hash 函数的实现

在 get 和 put 的过程中，计算下标时，先对 hashCode 进行 hash 操作，而后再通过 hash 值进一步计算下标，如下图所示在对 hashCode()计算 hash 时具体实现是这样的：

static final int hash(Object key) {
    int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

之前曾经提过，在获取 HashMap 的元素时，根本分两步：首先依据 hashCode()做 hash，而后确定 bucket 的 index；如果 bucket 的节点的 key 不是咱们须要的，则通过 keys.equals()在链中找。在 Java 8 之前的实现中是用链表解决抵触的，在产生碰撞的状况下，进行 get 时，两步的工夫复杂度是 O(1)+O(n)。因而，当碰撞很厉害的时候 n 很大，O(n)的速度显然是影响速度的。因而在 Java 8 中，利用红黑树替换链表，这样复杂度就变成了 O(1)+O(logn)了，这样在 n 很大的时候，可能比拟现实的解决这个问题

3.1.6、resize 的实现

当 put 时，如果发现目前的 bucket 占用水平曾经超过了 Load Factor 所心愿的比例，那么就会产生 resize。在 resize 的过程，简略的说就是把 bucket 裁减为 2 倍，之后从新计算 index，把节点再放到新的 bucket 中。resize 的正文是这样形容的：
大抵意思就是说，当超过限度的时候会 resize，然而又因为咱们应用的是 2 次幂的扩大 (指长度扩为原来 2 倍)，所以，元素的地位要么是在原地位，要么是在原地位再挪动 2 次幂的地位。怎么了解呢？例如咱们从 16 扩大为 32 时，具体的变动如下所示：
因而元素在从新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的 mask 范畴在高位多 1bit(红色)，因而新的 index 就会产生这样的变动：
因而，咱们在裁减 HashMap 的时候，不须要从新计算 hash，只须要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”。能够看看下图为 16 裁减为 32 的 resize 示意图：
这个设计的确十分的奇妙，既省去了从新计算 hash 值的工夫，而且同时，因为新增的 1bit 是 0 还是 1 能够认为是随机的，因而 resize 的过程，平均的把之前的抵触的节点扩散到新的 bucket 了。上面是代码的具体实现：

final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // 超过最大值就不再裁减了，就只好随你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
            // 没超过最大值，就裁减为原来的 2 倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else { // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 计算新的 resize 下限
    if (newThr == 0) {float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 把每个 bucket 都挪动到新的 buckets 中
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                            // 原索引 +oldCap
                        else {if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到 bucket 里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                        // 原索引 +oldCap 放到 bucket 里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

3.1.7、总结

咱们当初能够答复开始的几个问题，加深对 HashMap 的了解：
1. 什么时候会应用 HashMap？他有什么特点？
是基于 Map 接口的实现，存储键值对时，它能够接管 null 的键值，是非同步的，HashMap 存储着 Entry(hash, key, value, next)对象。
2. 你晓得 HashMap 的工作原理吗？
通过 hash 的办法，通过 put 和 get 存储和获取对象。存储对象时，咱们将 K / V 传给 put 办法时，它调用 hashCode 计算 hash 从而失去 bucket 地位，进一步存储，HashMap 会依据以后 bucket 的占用状况主动调整容量 (超过 Load Facotr 则 resize 为原来的 2 倍)。获取对象时，咱们将 K 传给 get，它调用 hashCode 计算 hash 从而失去 bucket 地位，并进一步调用 equals() 办法确定键值对。如果产生碰撞的时候，Hashmap 通过链表将产生碰撞抵触的元素组织起来，在 Java 8 中，如果一个 bucket 中碰撞抵触的元素超过某个限度 (默认是 8)，则应用红黑树来替换链表，从而进步速度。
3. 你晓得 get 和 put 的原理吗？equals() 和 hashCode()的都有什么作用？

通过对 key 的 hashCode()进行 hashing，并计算下标 ( n-1 & hash)，从而取得 buckets 的地位。如果产生碰撞，则利用 key.equals() 办法去链表或树中去查找对应的节点

4. 你晓得 hash 的实现吗？为什么要这样实现？
在 Java 1.8 的实现中，是通过 hashCode()的高 16 位异或低 16 位实现的：(h = k.hashCode()) ^ (h >>> 16)，次要是从速度、效用、品质来思考的，这么做能够在 bucket 的 n 比拟小的时候，也能保障思考到高下 bit 都参加到 hash 的计算中，同时不会有太大的开销。
5. 如果 HashMap 的大小超过了负载因子 (load factor) 定义的容量，怎么办？如果超过了负载因子 (默认 0.75)，则会从新 resize 一个原来长度两倍的 HashMap，并且从新调用 hash 办法。
以 Entry[]数组实现的哈希桶数组，用 Key 的哈希值取模桶数组的大小可失去数组下标。插入元素时，如果两条 Key 落在同一个桶 (比方哈希值 1 和 17 取模 16 后都属于第一个哈希桶)，Entry 用一个 next 属性实现多个 Entry 以单向链表寄存，后入桶的 Entry 将 next 指向桶以后的 Entry。查找哈希值为 17 的 key 时，先定位到第一个哈希桶，而后以链表遍历桶里所有元素，一一比拟其 key 值。当 Entry 数量达到桶数量的 75% 时(很多文章说应用的桶数量达到了 75%，但看代码不是)，会成倍扩容桶数组，并重新分配所有原来的 Entry，所以这里也最好有个预估值。取模用位运算(hash & (arrayLength-1)) 会比拟快，所以数组的大小永远是 2 的 N 次方，你轻易给一个初始值比方 17 会转为 32。默认第一次放入元素时的初始值是 16。iterator()时顺着哈希桶数组来遍历，看起来是个乱序。在 JDK8 里，新增默认为 8 的閥值，当一个桶里的 Entry 超过閥值，就不以单向链表而以红黑树来寄存以放慢 Key 的查找速度。

四、参考资料

https://dev.java/learn/api/collections-framework/

本文由博客一文多发平台 OpenWrite 公布！