手撕Map系列源码分析

刺骨的言语ヽ痛彻心扉 2024-04-20 11:19 90阅读 0赞

## Map源码分析 ##

### 1、构造函数 ###

无参：
       public HashMap() {
        
            this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
       } 
       static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子
    
        
    带参：
    
     public HashMap(int initialCapacity) {
        //容量
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    //容量和加载因子
    public HashMap(int initialCapacity, float loadFactor) {
        
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
            this.loadFactor = loadFactor;
            //阈值---有何用？
            this.threshold = tableSizeFor(initialCapacity);//todo
    }
    
    static final int tableSizeFor(int cap) {
        
            int n = cap - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
    
    001001010101010101010101010100010101
        
    001001010101010101010101010100010100
      
    001100101010101010101010101010001010
        
    001111001010101010101010101010100010
        
    001111111111111111111111111111111111
    
    010000000000000000000000000000000000

### 2、添加元素-put ###

public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
     }
    
    static final int hash(Object key) {
        
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    
     /**
         * Implements Map.put and related methods.
         *
         * @param hash hash for key--key 
         * @param key the key
         * @param value the value to put
         * @param onlyIfAbsent if true, don't change existing value
         * @param evict if false, the table is in creation mode.
         * @return previous value, or null if none
         */
    //put放元素
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
        
                   
            Node<K,V>[] tab;//暂存hash桶
            Node<K,V> p; //暂存链表---节点
            int n, i;
            //判断hash桶为空
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;//hash桶扩容--返回这个新的桶的长度
            //找我现在要放到这个key在hash桶的位置
            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)//树
                    //遍历这个红黑树--如果找到了相同的key,就把这个节点的值去替换掉这个节点,
                    //返回的e就记录了这个节点，如果没找到，那么按照红黑树的规则去加入这个节点
                    //如果没找到相同的key,返回null
                    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) // 7
                                // static final int TREEIFY_THRESHOLD = 8;
                                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;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
    }
    
    //扩容的方法
    final Node<K,V>[] resize() {
        
            Node<K,V>[] oldTab = table;//暂存hash桶
            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;
                }
                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;//16
                //static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
                //默认阈值--16*0.75=12
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
            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) {
        
                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;
        }
    
    hashMap：写代码测试扩容过程，打断点看扩容

#### 总结： ####

1、hashmap底层实现：
        1.8 使用的是数组+链表+红黑树
    2、HashMap第一次扩容的容量是多大？
        容量是16，加载因子是0.75，阈值是12---控制下次hash桶扩容的
    3、位置如何确定？为什么hash桶的长度必须是2的多少次方？
        p = tab[i = (n - 1) & hash]:用桶的长度-1去位与hash值
        10101011101010101010101010101110011
        00000000000000000000000000000001000
        那如果我构造的时候给了一个长度不是2的次方？---变成2的次方
    4、链表什么时候转红黑树？
        链表长度大于8，并且hash桶的长度达到64
    5、扩容机制是什么？扩容后元素会不会打乱重排？
        每次扩成2倍，每次扩容元素都会打乱重排--rehash

//LinkedList<String> list = new LinkedList<String>();
    		//list.set(0, "888");
    		
    //		HashMap<String, String> map = new HashMap<String, String>();
    //		for(int i=1;i<=11;i++) {
        
    //			map.put("key"+i, i+"");
    //		}
    //		map.put("kkk","aaa");
    //		map.put("aa","aaaaa");
    		
    		HashMap<Student, String> map = new HashMap<>();
    		for(int i=1;i<=10;i++) {
        //0010100  ---5 --> 21
    			map.put(new Student(), i+"");
    		}
    		map.put(new Student(),"aaa");

### 3、LinkedHashMap ###

特点：有序

双向链表
    static class Entry<K,V> extends HashMap.Node<K,V> {
        
            Entry<K,V> before, after;
            Entry(int hash, K key, V value, Node<K,V> next) {
        
                super(hash, key, value, next);
            }
     }
    
    
    onlyIfAbsent:是否替换老元素
        
    evict:是否是创建模式

void afterNodeInsertion(boolean evict) {
         // possibly remove eldest
            LinkedHashMap.Entry<K,V> first;
            if (evict && (first = head) != null && removeEldestEntry(first)) {
        
                K key = first.key;
                removeNode(hash(key), key, null, false, true);
            }
    }
    LRU:
    
     protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        
            return false;
    }

### 4、Hashtable ###

键和值都不允许为空
    线程安全但是效率低---Properties

### 5、TreeMap ###

特点是数据有序
        自然排序----key自己的比较器来排序
        自定义排序-----根据TreeMap构造的比较器来排序
        
    自定义排序排序的优先级高，先调用
        如果两个比较器都没有-------ClassCastException
    
      public V put(K key, V value) {
        
            Entry<K,V> t = root;//根节点
            if (t == null) {
        //当前节点做根节点
                compare(key, key); // type (and possibly null) check  比较器的非空
    
                root = new Entry<>(key, value, null);
                size = 1;
                modCount++;
                return null;
            }
            int cmp;//记录应该添加到左边还是右边
            Entry<K,V> parent;//记录要挂载的父节点
            // split comparator and comparable paths
            Comparator<? super K> cpr = comparator;
            if (cpr != null) {
        
                do {
        
                    parent = t;
                    cmp = cpr.compare(key, t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            else {
        
                if (key == null)
                    throw new NullPointerException();
                @SuppressWarnings("unchecked")
                    Comparable<? super K> k = (Comparable<? super K>) key;
                do {
        
                    parent = t;
                    cmp = k.compareTo(t.key);
                    if (cmp < 0)
                        t = t.left;
                    else if (cmp > 0)
                        t = t.right;
                    else
                        return t.setValue(value);
                } while (t != null);
            }
            Entry<K,V> e = new Entry<>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            fixAfterInsertion(e);//保证红黑树平衡
            size++;
            modCount++;
            return null;
        }  
        
     final int compare(Object k1, Object k2) {
        
            return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
                : comparator.compare((K)k1, (K)k2);
    }

TreeMap底层数据结构：平衡二叉树

### 扩展： ###

1.JDK1.7版本的HashMap底层数据结果是什么？
        一维数组 + 单向链表
        
    2.什么是Hash桶？
        单向链表
        
    3.什么是hash碰撞？
       多个key的hash值相同，在数组中的下标也是相同的，就会判断两个对象是否相同，这个过程叫做hash碰撞。
        
    4.hash碰撞应该要避免，因为一维数组查询快，而单向链表查询慢，hash碰撞后如果有单向链表的存在，势必会影响HashMap的查询效率
    
    5.HashMap底层一维数组的初始化长度为多少？
        1<<4 --> 16
    
    6.HashMap底层一维数组的长度为什么必须是2的幂？
        计算元素在数组中的下标的代码是：h & (length-1)
        长度不是2的幂，长度-1结果的二进制表示位数上有可能出现0，&的结果位数上就一定是0，导致元素在数组中的分布不均匀
    
    7.HashMap的一维数组的最大长度是什么？
        1 << 30; —> 1073741824
    
    8.HashMap的一维数组的最大长度为什么是1<<30？
        最大长度的类型是int
        1 << 30 是int取值范围里最大的2的幂的数字
    
    9.HashMap默认的负载因子是多少？作用是什么？
        默认的负载因子是0.75f
        作用：数组长度*负载因子得到阈值，元素个数达到阈值后就扩容
    
    10.HashMap默认的负载因子为什么是0.75f？
    取得了时间和空间的平衡
    
        如果负载因子过小，会导致装载一点点数据就扩容，利用时间，牺牲空间
        如果负载因子过大，会导致装载满了才扩容，利用空间，牺牲了时间
    
    11.ashMap存放null键null值的位置？
        hash数组下标为0的位置
    
    12.HashMap的扩容机制？
       元素个数大于等于阈值并且添加元素的下标位置不等于null，才会扩容
       扩容的容量是原来的2倍
    
    13.什么叫做hash回环？
       多线程的情况下
       线程1不断的添加元素，导致扩容
       线程2不断的遍历
       线程1扩容期间，单向链表的下一个节点位置有闭环，线程2遍历有出现hash回环的问题
    
    经验：使用HashMap出现hash回环问题，不是HashMap的错误，是程序员应该背的锅，因为HashMap明确表示该实现不是一个线程安全的集合，你在多线程下使用出现的问题应该是你去负责。多线程下应该使用ConcurrentHashMap
    
    14.HashMap使用的注意事项？
       1.不能在多线程下使用
    
       2.key的hashCode不要写死了，不然会出现hash碰撞
            
    15.JDK1.7和1.8中HashMap的区别？
    
    JDK1.7：
    
     一维数组+单向链表
    
     计算hash值：hashCode() + 散列算法
    
     头插法
    
    JDK1.8：
    
     一维数组+单向链表+平衡二叉树（提高查询效率）
    
     计算hash值：高16 ^ 低16位
    
     尾插法
    
    16.JDK1.8HashMap什么是从一维数组+单向链表 变为 一维数组+平衡二叉树
    
        数组的长度大于64，并且单向链表的长度大于8，就会从一维数组+单向链表 变为 一维数组+平衡二叉树
    
       平衡二叉树小于6时，有会从一维数组+平衡二叉树 变为 一维数组+单向链表
    
    17.JDK1.8HashMap 为什么单向链表大于8后变为平衡二叉树
       因为泊松分布