jdk1.7中的HashMap

àì夳堔傛蜴生んèń 2022-12-16 09:20 132阅读 0赞

jdk1.7底层使用的数组+链表实现

HashMap类继承了AbstractHashMap类，实现类Map<K,V>接口，Cloneable，Serializable接口

public class HashMap<K,V> extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable { 
    
       /** * The default initial capacity - MUST be a power of two. */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认初始容量2^4
    
        /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
        static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量2^30
    
        /** * The load factor used when none specified in constructor. */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认负载因子0.75f，当构造方法未指定负载因子时
    
        /** * An empty table instance to share when the table is not inflated. */
        static final Entry<?,?>[] EMPTY_TABLE = { };
    
        /** * The table, resized as necessary. Length MUST Always be a power of two. */
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
        /** * The number of key-value mappings contained in this map. */
        transient int size;//当前key-vlue键值对的数目
    
        /** * The next size value at which to resize (capacity * load factor). * @serial */
        // If table == EMPTY_TABLE then this is the initial capacity at which the
        // table will be created when inflated.
        int threshold;//要调整大小的下一个大小值（容量*负载系数），如果table==EMPTY_table，则这时table将在扩容时侯被创建
    
    
    
        /** * The load factor for the hash table. * * @serial */
        final float loadFactor;//负载因子
    
        /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */
        transient int modCount;//HashMap被修改的次数
    
        /** * The default threshold of map capacity above which alternative hashing is * used for String keys. Alternative hashing reduces the incidence of * collisions due to weak hash code calculation for String keys. * <p/> * This value may be overridden by defining the system property * {@code jdk.map.althashing.threshold}. A property value of {@code 1} * forces alternative hashing to be used at all times whereas * {@code -1} value ensures that alternative hashing is never used. */
        static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;    
        transient int hashSeed = 0;//hash种子

以下为Entry对象，存储key-value

static class Entry<K,V> implements Map.Entry<K,V> { 
            final K key//key
            V value;//value
            Entry<K,V> next;//下一个结点
            int hash;//hash值
    
            /** * Creates new entry. */
            Entry(int h, K k, V v, Entry<K,V> n) { //创建一个Entry对象(key,value,hash)，指明下一个结点next
                value = v;
                next = n;
                key = k;
                hash = h;
            }

然后看构造方法

public HashMap(int initialCapacity, float loadFactor) { 
            if (initialCapacity < 0)//如果初始容量小于0，抛出不合法的初始容量异常
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)//如果初始容量大于最大容量，设置最大容量为初始容量，最大容量为2^30
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))//负载因子<=0，或者负载一直不是合法浮点数，抛出不合法负载因子异常，因子负载因子要大于0
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            this.loadFactor = loadFactor;//设置
            threshold = initialCapacity;
            init();
        }
            /** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). * * @param initialCapacity the initial capacity. * @throws IllegalArgumentException if the initial capacity is negative. */
        public HashMap(int initialCapacity) { 
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /** * Constructs an empty <tt>HashMap</tt> with the default initial capacity * (16) and the default load factor (0.75). */
        public HashMap() { 
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);//默认初始容量未16，默认负载因子为0.75f
        }

然后看put方法

public V put(K key, V value) { 
            if (table == EMPTY_TABLE) { //table为EMPTY_TABLE（{}），也就是刚开始new HashMap<>()时候
                inflateTable(threshold);//为数组分配空间
            }
            if (key == null)//put null key时候
                return putForNullKey(value);//put null key方法
            int hash = hash(key);//计算hash值
            int i = indexFor(hash, table.length);//根据hash值和数组长度计算出一个下标
            for (Entry<K,V> e = table[i]; e != null; e = e.next) { //遍历以table[i]为头结点的链表
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果要当前结点的hash值等于hash且当前结点的key等于key
                    V oldValue = e.value;//记录当前节点value
                    e.value = value;//设置当前结点value为value
                    e.recordAccess(this);
                    return oldValue;//返回旧value
                }
            }
    
           //如果当前要插入的key不存在
            modCount++;
            addEntry(hash, key, value, i);//添加新的结点
            return null;
        }

然后看inflateTable方法

private void inflateTable(int toSize) { 
            // Find a power of 2 >= toSize
            int capacity = roundUpToPowerOf2(toSize);//capacity的值为>=toSize的2的n次幂，比如toSize为13，则capacity为16，toSize为17，capactiy为32
    
            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//计算threasholld为容量*负载因子
            table = new Entry[capacity];//创建容量为capactity的数组
            initHashSeedAsNeeded(capacity);//为当前容量数组初始化hash种子
        }

查看initHashSeedAsNeeded方法

final boolean initHashSeedAsNeeded(int capacity) { 
            boolean currentAltHashing = hashSeed != 0;//初始化时候hashSeed为0，所以currentAltHashing=false
            boolean useAltHashing = sun.misc.VM.isBooted() &&
                    (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//isBooteded默认返回false(如果jvm不进行赋值)，
            boolean switching = currentAltHashing ^ useAltHashing;//false^false=false
            if (switching) { 
                hashSeed = useAltHashing
                    ? sun.misc.Hashing.randomHashSeed(this)
                    : 0;
            }
            return switching;
        }

查看Holder.ALTERNATIVE\_HASHING\_THRESHOLD部分

private static class Holder { 
    
            /** * Table capacity above which to switch to use alternative hashing. */
            static final int ALTERNATIVE_HASHING_THRESHOLD;
    
            static { 
                String altThreshold = java.security.AccessController.doPrivileged(
                    new sun.security.action.GetPropertyAction(
                        "jdk.map.althashing.threshold"));//根据配置的jvm参数jdk.map.althashing.threshold得到一个altThreshold，doPrivileged底层为native方法
    
                int threshold;
                try { 
                    threshold = (null != altThreshold)
                            ? Integer.parseInt(altThreshold)
                            : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;//计算threshold
    
                    // disable alternative hashing if -1
                    if (threshold == -1) { //threshold=-1
                        threshold = Integer.MAX_VALUE;///MAX_VALUE为0x7fffffff
                    }
    
                    if (threshold < 0) { //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;
            }
        }

因此通过设定一定的jvm参数可以使得useAltHashing的值为false，从而switching为true，从而改变hashSeed的目的

看一下putForNullKey方法

private V putForNullKey(V value) { 
            for (Entry<K,V> e = table[0]; e != null; e = e.next) { //遍历table[0]为头节点的链表
                if (e.key == null) { //找到key为null的结点，把结点的value更改为当前value
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
            modCount++;
            addEntry(0, null, value, 0);//如果不存在null key，那么在添加一个新结点，hash为0，下标为0，key为null，value为value
            return null;
        }

然后看一下hash方法

final int hash(Object k) { //给定一个key计算出一个hash值
            int h = hashSeed;//hash种子，默认为0
            if (0 != h && k instanceof String) { 
                return sun.misc.Hashing.stringHash32((String) k);
            }
    
            h ^= k.hashCode();//hashcode()为Object类的方法，为native方法
    
            // 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);//使得高位参加运算，增加hashcode的散列型
        }

然后提高hash方法得到了一个hash值，  
然后看indexFor方法

static int indexFor(int h, int length) { 
            // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
            return h & (length-1);//得到数组元素下标，这里巧妙运用了数组长度为2的n次幂，比如数组长度为默认长度16，15二进制后五位为1111，假设计算出的hash值二进制表示为10110010，两者相与为00000010，相与后的值始终在0-15之间也就是 0-数组的长度-1，当然也可以做取余运算，但是&运算的速度要远远大于取余
        }

这样旧得到了数组的下标i，然后下面就判断该key是否在以table\[i\]为头结点存在，如果存在替换为新value，如果不存在就在链表添加新的元素

然后看addEntry的代码

void addEntry(int hash, K key, V value, int bucketIndex) { 
            if ((size >= threshold) && (null != table[bucketIndex])) { //当前table长度>=threadshold且当前数组元素不为null
                resize(2 * table.length);//扩容为原来两倍
                hash = (null != key) ? hash(key) : 0;//重新计算hash
                bucketIndex = indexFor(hash, table.length);//重新计算数组下标
            }
    
            createEntry(hash, key, value, bucketIndex);//创建一个Entry对象
        }

然后看一下resize方法，

void resize(int newCapacity) { 
            Entry[] oldTable = table;//记录旧table
            int oldCapacity = oldTable.length;//记录旧table长度
            if (oldCapacity == MAXIMUM_CAPACITY) { //如果旧table长度=2^30
                threshold = Integer.MAX_VALUE;//threadshold为MAX_VALUE(0x7fffffff)
                return;
            }
    
            Entry[] newTable = new Entry[newCapacity];//new一个新Entry数组
            transfer(newTable, initHashSeedAsNeeded(newCapacity));//将旧Entry数组的元素移到新数组
            table = newTable;//将newTable的值赋值给旧table
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//重新计算threadshold
        }

然后看一下transfer方法

/** * Transfers all entries from current table to newTable. */
        void transfer(Entry[] newTable, boolean rehash) { 
            int newCapacity = newTable.length;//计算新Entry数组长度
            for (Entry<K,V> e : table) { //遍历旧 table数组
                while(null != e) { //当当前结点不为null
                    Entry<K,V> next = e.next;//得到当前结点
                    if (rehash) { //得到hash值
                        e.hash = null == e.key ? 0 : hash(e.key);
                    }
                    int i = indexFor(e.hash, newCapacity);//重新计算数组下标
                    //采用头插法插入
                    e.next = newTable[i];//当前结点下一个结点为newTable[i]
                    newTable[i] = e;//当前newTable[i]为当前结点
                    e = next;//e指向下一个结点
                }
            }
        }

进入createEntry方法

void createEntry(int hash, K key, V value, int bucketIndex) { 
            Entry<K,V> e = table[bucketIndex];//记录当前数组元素 table[bucketIndex]
            table[bucketIndex] = new Entry<>(hash, key, value, e);//要插入结点的下一个结点为当前结点，也就是头插法
            size++;//key-value的数量加1
        }

然后看一下get方法

public V get(Object key) { 
            if (key == null)//key为null时候
                return getForNullKey();//获取null key的value
            Entry<K,V> entry = getEntry(key);//指向getEntry方法
    
            return null == entry ? null : entry.getValue();
        }

进入getForNullKey方法

private V getForNullKey() { 
            if (size == 0) { //如果当前key-value数量为0
                return null;
            }
            for (Entry<K,V> e = table[0]; e != null; e = e.next) { 
                if (e.key == null)//查找到key为null的元素
                    return e.value;//返回其value
            }
            return null;
        }

进入getEntry方法

final Entry<K,V> getEntry(Object key) { 
            if (size == 0) { //如果当前key-value 数量为0
                return null;
            }
    
            int hash = (key == null) ? 0 : hash(key);//根据key计算出一个hash值
            for (Entry<K,V> e = table[indexFor(hash, table.length)];//计算出一个数组下标i，遍历table[i]为头节点的链表
                 e != null;
                 e = e.next) { 
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))//如果当前结点hash等于要查找的hash且当前结点key与要查找key相等
                    return e;//返回当前结点
            }
            return null;
        }

然后看一下remove方法

public V remove(Object key) { 
            Entry<K,V> e = removeEntryForKey(key);
            return (e == null ? null : e.value);//返回删除的元素
        }

进入removeEntryForKey方法

final Entry<K,V> removeEntryForKey(Object key) { 
            if (size == 0) { //如果当前key-value 数量为0
                return null;
            }
            int hash = (key == null) ? 0 : hash(key);//根据key计算出一个hash值
            int i = indexFor(hash, table.length);//根据hash值和table长度计算出一个下标
            Entry<K,V> prev = table[i];//记录原数组
            Entry<K,V> e = prev;//记录要遍历的table[i]链表
    
            while (e != null) { //遍历链表
                Entry<K,V> next = e.next;
                Object k;
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) { //如果当前结点key==k要删除的key
                    modCount++;
                    size--;//key-value 数量-1
                    if (prev == e)//如果要删除的结点==第一个结点
                        table[i] = next;//数组table[i]变为e的下一个结点
          
                    else
                        prev.next = next;//比如有1 2 3，意思就是1直接指向3
                    e.recordRemoval(this);
                    return e;
                }
                prev = e;//当前prv为e
                e = next;//当前e为next
            }
    
            return e;//返回删除的结点
        }