08 集合总结-蒲公英云

08 集合总结

港控/mmm° 2022-11-25 00:58 181阅读 0赞

HashTable
底层是数组+链表，初始容量是11，负载因子0.75，扩容2倍+1，头插法,采用的Entry

int hash = key.hashCode();//object的hashcode方法
// 为啥要把hash值和0x7FFFFFFF做一次按位与操作呢，
```
    // 主要是为了保证得到的index的第一位为0，也就是为了得到一个正数。
    // 因为有符号数第一位0代表正数，1代表负数
```
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap
底层是数组+链表，初始容量16，负载因子0.75，扩容2倍，1.8开始采用尾插法，采用的Node
。

static final int hash(Object key) {

    int h;
    //一般数组长度length都不会很大，如果不对hash值做处理，
    //直接用hash值&（length-1），index仅与hash值的低n位有关，
    //hash值的高位都被与操作置为0，所以将hash值高16位与低16位异或来
    //减少这种影响。
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在这里插入图片描述

TreeMap
底层是红黑树，采用的Entry
LinkedHashMap
- 底层是基于HashMap的，在此基础上Entry节点还保存了指向前后节点的指针before和after。
- LinkedHashMap有head和tail属性，指向双向链表的头和尾。
- 扩容时：HashMap是遍历table，LinkedHashMap是遍历双向链表。
- 从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数）。
- 参考博客：https://www.jianshu.com/p/8f4f58b4b8ab
ArrayList 1.5倍扩容
CopyOnWriteArrayList 没有1.5倍扩容
Vector 2倍扩容使用synchronized加锁
HashSet,底层是HashMap
TreeSet，底层是TreeMap