hashMap源码阅读笔记1.7

╰+攻爆jí腚メ 2022-04-05 11:56 244阅读 0赞

### *这几天一直在看hashMap的源码，也借鉴了很多大佬的文章以便更好的理解，也从大佬文章中借鉴了很多的内容，如果侵权，请告知，我将立刻删除*。 ###

hashMap继承AbstractMap，实现了map接口。

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable

初始容量：哈希表创建时的容量，实际上就是Entry<k,v>\[\] table的容量  
static final int DEFAULT\_INITIAL\_CAPACITY = 16;  
最大容量  
static final int MAXIMUM\_CAPACITY = 1 << 30;  
加载因子  
static final float DEFAULT\_LOAD\_FACTOR = 0.75f;  
哈希表  
transient Entry<K,V>\[\] table;  
存在映射关系的条数  
transient int size;  
阈值  
int threshold;  
修改计数  
transient int modCount;

hashMap的几个默认构造方法：
    (1):构造了一个映射关系与指定map相同的hashMap，类似拷贝
    public HashMap(Map<? extends K, ? extends V> m)
    (2):指定初始容量和加载因子
    public HashMap(int initialCapacity, float loadFactor)
    (3):指定初始容量
    public HashMap(int initialCapacity)
    (4):默认构造方法
    public HashMap()

计算hash值

final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

返回索引下标

//1：h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效
    //2：capacity 必须为2的n次幂,则length-1肯定为奇数，在位运算h & (length -1)唯一性更高，
    //减少collision的发生，也就是保证bucketIndex低重复性
    static int indexFor(int h, int length) {        
        return h & (length-1);
    }

当前map的映射关系数目

public int size() {
        return size;
    }

判断map是否为空，即映射条数是否为0

public boolean isEmpty() {
        return size == 0;
    }

### 0.单项链表的实现  ###

// 实现了单向链表
        static class Entry<K, V> implements Map.Entry<K, V> {
            final K key;
            V value;
            Entry<K, V> next;
            int hash;
            //Map.Entry保存一个键值对 和这个键值对持有指向下一个键值对的引用，如此就构成了链表了。
            Entry(int h, K k, V v, Entry<K, V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
        }

### 1.get方法 ###

当调用get方法，会首先判断key值是否为null，如果为null，调用getForNullKey()方法，这也是hashMap允许key值为null的原因

public V get(Object key) {
        if (key == null){
            return getForNullKey();
        }
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }

当get(null)调用该方法，如果存在key为null情况，就返回key为null的value值，否则，直接返回null

private V getForNullKey() {
        for (Entry<K, V> e = table[0]; e != null; e = e.next) {
            if (e.key == null){
                return e.value;
            }
        }
        return null;
    }

当get(!=null)调用此方法

final Entry<K,V> getEntry(Object key) {
        1.根据key计算hash值
        int hash = (key == null) ? 0 : hash(key);
        2.通过hash值找出entry
        // 1 indexFor(hash, table.length):获取bucketIndex
        // 2 遍历具体bucket[indexFor(hash, table.length)]下的单向链表
        // 3 如果这个key的hashCode一样同时key值一样，或者key对象相同，则返回
        for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {
            Object k;
            if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        3.哈希表中不存在key的时候返回null：例如：containsKey方法
        return null;
    }

### 2.put方法 ###

public V put(K key, V value) {
            if (key == null)
                //当key为null时，调用putForNullKey方法
                return putForNullKey(value);
            //计算hash值
            int hash = hash(key);
            //获取
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                //如果执行put操作的时候发现key已存在，就更新value
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            //增加修改次数
            //1：如果多个线程访问，当发现modCount不一致，就会导致ConcurrentModificationException
            //2：遍历的时候执行remove操作也会导致ConcurrentModificationException
            //可以使用iterator解决2问题，1问题也说明hashMap是线程不安全
            //使hashMap线程安全：Map map = Collections.synchronizeMap(hashMap);
            modCount++;
            //不存在就新增
            addEntry(hash, key, value, i);
            return null;
        }
    
            
        void addEntry(int hash, K key, V value, int bucketIndex) {
            //如果映射关系的数量已经超过了阈值，并且table的桶索引的值不为null
            if ((size >= threshold) && (null != table[bucketIndex])) {
               //扩大一倍
                resize(2 * table.length);
                //重新计算hash值：结构已经改变
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
        
    
        void createEntry(int hash, K key, V value, int bucketIndex) {
            //断开链表，add结点，注意总是从链表的表头处插入新结点
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
        }

参数链接：[https://blog.csdn.net/lemon89/article/details/50994691][https_blog.csdn.net_lemon89_article_details_50994691]

[https_blog.csdn.net_lemon89_article_details_50994691]: https://blog.csdn.net/lemon89/article/details/50994691