08 集合总结

港控/mmm° 2022-11-25 00:58 118阅读 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);
        }

![在这里插入图片描述][20191212221033982.png]

*  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

[20191212221033982.png]: /images/20221124/3f36608df6b8405bbdde2aa01b03895b.png