Java 1.7 HashMap源码阅读

1. 构造方法

// 默认Hash 
	// The default initial capacity - MUST be a power of two.
	// 默认容量即hash可放置的元素数量
	static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
	// The load factor used when none specified in constructor.
	// 未指定时的默认扩容因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
 	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;
        // threshold 的注释
        // If table == EMPTY_TABLE then this is the initial capacity at which the
    	// table will be created when inflated.
    	// 如果表为空表则threshold将在inflated时被创建
        threshold = initialCapacity;
        // init 为空方法 即当真正向hashmap中put时使用inflateTable方法初始化Entry数组
        init();
    }

2. put方法

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old value is replaced.
     * 
     * 
     */
 public V put(K key, V value) {
 		
        if (table == EMPTY_TABLE) {
       		 // 真正的初始化方法
        	// 代码比较简单 
        	// threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 
        	// threshold 初始时为12
            // table = new Entry[capacity];
            //  最后单独说initHashSeedAsNeeded(capacity);
            inflateTable(threshold); // 这里传的是初始时 的 16 
        }
        // 为null值 指定位置
        // table[0]的链表  并返回旧值或null
        if (key == null)
            return putForNullKey(value);
            // 计算hash值
        int hash = hash(key);
        // 为利用hash找到 key应该放到table的某个数组的链下
        int i = indexFor(hash, table.length);
        // 遍历 table[i]链表 找到与当前key相同的替换并返回旧值
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
		// 若table[i]下没有相同的key 则 modCount+1,并执行addEntry将key,value放到map中
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

执行addEntry方法将key,value存入map中。

此方法先计算是否需要扩容后真正放值。

//size : The number of key-value mappings contained in this map.
 void addEntry(int hash, K key, V value, int bucketIndex) {
 		// add之前会判断当前map中的数量是否大于等于阈值
 		// 扩容条件 当前size超过阈值 并且 table[bucketIndex] 不为空
        if ((size >= threshold) && (null != table[bucketIndex])) {
        	// 扩容原先的两倍 
            resize(2 * table.length);
            // 重新计算hash值
            hash = (null != key) ? hash(key) : 0;
            // 计算当前key所属的 table数组位置
            bucketIndex = indexFor(hash, table.length);
        }
        createEntry(hash, key, value, bucketIndex);
    }

真正的放值方法，

使用的是头插法即将table[bucketIndex]替换为我们的key，并将原先的Entry当作当前Entry的next节点

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

3. resize扩容方法

扩容方法是创建一个新的Entry数组（容量为原先的两倍）

并将原先数组中的值转移到新数组中

// 此处使用了一个全局变量MAXIMUM_CAPACITY 
static final int MAXIMUM_CAPACITY = 1 << 30;//1073741824 即2的30次方
 void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        // 如果当前table容量已经等于最大容量值则将阈值设定为整数最大值并返回
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;//2<sup>31</sup>-1
            return;
        }
		
        Entry[] newTable = new Entry[newCapacity];
        // 转移值 initHashSeedAsNeeded用于返回是否需要重新计算hash
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        // 转移值之后 更改table的引用 
        table = newTable;
        // 更新阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

转移数组方法

遍历table 并循环遍历每个链表为链表中每个元素计算隶属与数组哪个位置然后转移

注意：HashMap是非线程安全的转移是会有机会造成循环引用，后面会演示怎样造成循环引用

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

4. remove

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    /**
     * Removes and returns the entry associated with the specified key
     * in the HashMap.  Returns null if the HashMap contains no mapping
     * for this key.
     */
    final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                // 若为链表 头直接修改头的引用
                if (prev == e)
                    table[i] = next;
                else //修改引用 前一个结点的下个结点指向当前的下个结点 从而抛弃当前节点
                    prev.next = next;
                
                e.recordRemoval(this);//
                return e;
            }
            // 修改引用 遍历下一个Entry
            prev = e;
            e = next;
        }

        return e;
    }

5. initHashSeedAsNeeded 和 hash

返回是否需要重新计算hash

transient int hashSeed = 0;
final boolean initHashSeedAsNeeded(int capacity) {
        boolean currentAltHashing = hashSeed != 0;// 初始时 false
        
        boolean useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);// 容量是否超过 默认时Integer最大值
        // 默认为false 但是通过打印可以得知为true 没有查看怎么修改的但从字面意思时虚拟机是否启动
        //private static volatile boolean booted = false;
   		// public static boolean isBooted() {
    	//    return booted;
    	//}

		// 默认 false ^ false 
        boolean switching = currentAltHashing ^ useAltHashing;// 异或预算 不相同时返回true
        if (switching) {// true 时 hashSeed hash 种子
            hashSeed = useAltHashing//false
                ? sun.misc.Hashing.randomHashSeed(this)
                : 0;
        }
        return switching;
    }

static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    /**
     * holds values which can't be initialized until after VM is booted.
     */
    private static class Holder {

        /**
         * Table capacity above which to switch to use alternative hashing.
         */
        static final int ALTERNATIVE_HASHING_THRESHOLD;

        static {
        // 判断是否有此参数
        // 	-Djdk.map.althashing.threshold=-1:表示不做优化（不配置这个值作用一样）
		// -Djdk.map.althashing.threshold<0:报错

		// -Djdk.map.althashing.threshold=1:表示总是启用随机HashSeed
		// -Djdk.map.althashing.threshold>=0:便是hashMap内部的数组长度超过该值了就使用随机HashSeed，降低碰撞
            String altThreshold = java.security.AccessController.doPrivileged(
                new sun.security.action.GetPropertyAction(
                    "jdk.map.althashing.threshold"));
            int threshold;
            try {
                threshold = (null != altThreshold)
                        ? Integer.parseInt(altThreshold)
                        : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;// 默认Integer最大值

                // disable alternative hashing if -1
                if (threshold == -1) {
                    threshold = Integer.MAX_VALUE;
                }

                if (threshold < 0) {
                    throw new IllegalArgumentException("value must be positive integer.");
                }
            } catch(IllegalArgumentException failed) {
                throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
            }
			
            ALTERNATIVE_HASHING_THRESHOLD = threshold;
        }
    }

final int hash(Object k) {
        int h = hashSeed;// hashSeed 默认为0
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
		// 异或 
        h ^= k.hashCode();
		
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

6. 多线程 resize 线程不安全演示

转移Entry会造成链表翻转
线程1执行完转移 线程二开始转移

int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }

假定条件：两个线程同时执行到，第一次while next = e.next时，线程一继续执行，线程二等待线程一执行完后再执行。

e = table[i];

next = 1;

Java 1.7 HashMap源码阅读

Java 1.7 HashMap源码阅读

目录

1. 构造方法

2. put方法

3. resize扩容方法

4. remove

5. initHashSeedAsNeeded 和 hash

6. 多线程 resize 线程不安全演示

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method