集合知识汇总答赵二狗问

作者: ElevenKing | 来源:发表于2019-07-16 18:29 被阅读0次

集合知识汇总答赵二狗问
集合知识汇总
禅是月下箫(6)
一次真实的HashMap面试之问
JAVA集合知识点汇总<二> Set集合
白狗波符13问
随感
马二狗和赵二斗（十）
童言无忌
《长夏》第三十三章—誓约

Collection

Map

热心读者赵二狗提出的疑问@!#$%^&(

$\color{red}{Q:}$ 说说常见的集合有哪些吧？
$\color{red}{A:}$ Map接口和Collection接口是所有集合框架的父接口：
1.Collection接口的子接口包括：Set接口和List接口
2.Map接口的实现类主要有：HashMap、TreeMap、Hashtable、ConcurrentHashMap以及Properties等
3.Set接口的实现类主要有：HashSet、TreeSet、LinkedHashSet等
4.List接口的实现类主要有：ArrayList、LinkedList、Stack以及Vector等

$\color{red}{Q:}$ 对比 Vector、ArrayList、LinkedList 有何区别？
$\color{red}{A:}$ 这三个都是实现集合框架中的List，也就是所谓的有序集合，因此具体功能都比较类似，比如都按照位置进行定位、添加、或者删除的操作，都提供迭代器遍历其内容等。但因具体的设计区别，在行为、性能、线程安全等方面，表现又有很大不同。
要根据实际场景针对性的做出选择。

对比项	是否线程安全	数据结构	扩容	性能分析
Verctor	线程安全	数组	提高一倍	数组存储，适合随机访问。除了头部和尾部插入元素，性能相对较差
ArrayList	线程不安全	数组	增加百分之50	同上
LinkedList	线程不安全	双向链表	数组	节点插入、删除要高效很多，但是随机访问性能要比动态数组慢

$\color{red}{Q:}$ 数据迁移完成之后，就能够切到新库提供服务了么？
$\color{red}{A:}$ 答案是肯定的，因为前置步骤进行了双写，所以理论上数据迁移完之后，新库与旧库的数据应该完全一致。

$\color{red}{Q:}$ 对比HashSet、TreeSet、LinkedHashSet区别
$\color{red}{A:}$ set是不允许重复元素的，这是和List最明显的区别。

对比项	数据结构	性能分析
HashSet	TreeMap,以对象“PRESENT”作为 value,插入的元素都作为key放进TreeMap	支持自然顺序访问，但是添加、删除、包含等操作要相对低效（log(n) 时间）
TreeSet	HashMap,以对象“PRESENT”作为 value,插入的元素都作为key放进HashMap	是利用哈希算法，理想情况下，如果哈希散列正常，可以提供常数时间的添加、删除、包含等操作，但是它不保证有序。
LinkedHashSet	内部构建了一个记录插入顺序的双向链表	提供了按照插入顺序遍历的能力，与此同时，也保证了常数时间的添加、删除、包含等操作，这些操作性能略低于HashSet，因为需要维护链表的开销。

$\color{red}{Q:}$ 如何让线程不安全的集合变成线程安全的集合？
$\color{red}{A:}$ Collectons工具类中的synchronized 方法，将每个基本方法 get、set、add等都通过 synchronizd 添加基本的同步支持，非常简单粗暴。

List list = Collections.synchronizedList(new ArrayList());

$\color{red}{Q:}$ HashMap与HashTable的区别？
$\color{red}{A:}$ 1.HashMap没有考虑同步，是线程不安全的；Hashtable使用了synchronized关键字，是线程安全的
2.HashMap允许K/V都为null；后者K/V都不允许为null
3.HashMap继承自AbstractMap类；而Hashtable继承自Dictionary类

$\color{red}{Q:}$ HashMap的put方法的具体流程？
$\color{red}{A:}$ 一遍文章单独写
hashMap put方法

$\color{red}{Q:}$ HashMap的扩容操作是怎么实现的？
$\color{red}{A:}$ HashMap通过resize()方法进行扩容或者初始化的操作

/**
 * 该函数有2中使用情况：1.初始化哈希表；2.当前数组容量过小，需要扩容
 */
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) {
        // 针对情况2：若扩容前的数组容量超过最大值，则不再扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 针对情况2：若没有超过最大值，就扩容为原来的2倍（左移1位）
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }

    // 针对情况1：初始化哈希表（采用指定或者使用默认值的方式）
    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都移动到新的bucket中去
        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;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}