你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

HashMap详解

2021-11-9 4:05:29

一.什么是HashMap

一·特性
HashMap基于Map接口实现,元素以键值对的方式存储,允许键和值为null,因为key不允许重复,因此只能有一个键为null。它是无序的。HashMap是线程不安全的。
在这里插入图片描述

二.jdk1.7

一.数据结构

jdk1.7hashmap是一个“链表散列”的数据结构,数组+单向链表。
在这里插入图片描述
Entry类是一个HashMap的静态内部类。

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//存储指向下一个Entry的引用,单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算

        /**
         * 创建一个新Entry,并用新的节点指向链表的头结点。
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

二.属性

//默认初始化化容量16,1左移4位即16。可以通过构造方法进行自定义。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 

//最大容量,即2的30次方  
static final int MAXIMUM_CAPACITY = 1 << 30;  

//默认装载因子0.75,作用在于,当存储的容量超过阈值(存储容量和加载因子的乘积)时,要对哈希表进行扩展操作。
static final float DEFAULT_LOAD_FACTOR = 0.75f;  

//HashMap内部的存储结构是一个数组,此处数组为空,即没有初始化之前的状态  
static final Entry<?,?>[] EMPTY_TABLE = {};  

//空的存储实体  
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  

//实际存储的键值对的个数
transient int size;

//实际数组容量 也叫扩容的阈值,size超过了threshold就会扩容,当table == {}时,该值为初始容量(初始容量默认为16)。
//阈值=容量*负载因子
int threshold;

//负载因子,代表了table的填充度有多少,默认是0.75
final float loadFactor;

//map结构修改次数,用于迭代器
transient int modCount;

//默认阈值 
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//哈希种子(hashSeed)用于优化哈希函数,默认为0是不使用替代哈希算法
transient int hashSeed = 0;

//定义Map.Entry<K,V>集合。
private transient Set<Map.Entry<K,V>> entrySet = null;

1.为什么负载载因子是0.75 ?
源码分析:数组下标 = hash & (length-1), 所以:
加载因子越大,内存利用率越高,index下标冲突概率也就越大;
加载因子越小,内存利用率越低,index下标冲突概率也就越小;

三.构造方法


//这个构造方法用于传入初始容量和扩容因子
public HashMap(int initialCapacity, float loadFactor) {
	//传入的初始容量小于0,抛异常
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
                                           
      //当初始容量大于最大容量时,使用最大容量                                   
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
        //判断加载因子必须是大于0,而且必须是数字
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    // 设置实际负载因子
    this.loadFactor = loadFactor;
     //设置扩容阀值=初始容量,但是在put()方法初始化数组时, 其实际值=容量*负载因子
    threshold = initialCapacity;
    init();
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//用于将一个Map存入这个map中
public HashMap(Map<? extends K, ? extends V> m) {
    this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                  DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
    inflateTable(threshold);

    putAllForCreate(m);
}

小结:
1.当调运有参构造,赋予的初始容量传入的初始容量小于0,抛异常。
2.若赋予的初始容量大于最大容量时,使用最大容量 。

四.put()方法

public V put(K key, V value) {
        // 判断数组是否为空
        if (table == EMPTY_TABLE) {
        // 初始化数组方法
            inflateTable(threshold);  
        }
        // 判断添加的key是否null 
        if (key == null)
            return putForNullKey(value); // 如果为null, 则对应的value存放到table[0]
     // 根据key计算哈希值
        int hash = hash(key);
     // 计算数组下标  i= hash & (length - 1)
        int i = indexFor(hash, table.length);
         // 获取相同hashCode对应下标的table[i]数据, 并遍历
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
      // 判断hashcode相同并且key值相同
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                // 如果为true,表示key一同,覆盖
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
 
        modCount++;  //实际修改次数加1
        // 如果hash不同 或者 hansh相同对象不同, 则添加元素
        addEntry(hash, key, value, i);  
        return null;
    }
    
 //key为null的值,默认hashcode为0,放在哈希桶的第一个位置	    
  private V putForNullKey(V value) {
  		//如果多次put key为null的键值对,新值会覆盖原来的值
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //这里默认位置为第一个
        addEntry(0, null, value, 0);
        return null;
    }
 
 // 初始化hash表
 private void inflateTable(int toSize) {
 		// Find a power of 2 >= toSize
 		//就是找到一个数,数是2的幂次方并且大于等于toSize,比如传入的数是13,14或15,那么初始容量就是16
        int capacity = roundUpToPowerOf2(toSize);
        // 重新记录阈值,阈值=容量* 扩容因子
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
  }
 
  
    // 添加entry对象
    void addEntry(int hash, K key, V value, int bucketIndex) { // bucketIndex数组下标
     // 判断的数组的大小是否大于等于阀值
        if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容后数组长度为之前的2倍
            resize(2 * table.length);
            // 扩容后重新计算下标
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length); 
        }
    //若容量足够,则创建1个新的数组元素(Entry) 并放入到数组中
        createEntry(hash, key, value, bucketIndex);
    }
 
 
  // 创建Entry对象
    void createEntry(int hash, K key, V value, int bucketIndex) {
        // 获取原来的oldEntry对象, 如果!=null表示发生hash冲突
        Entry<K,V> e = table[bucketIndex]; 
        // 创建新的newEntry对象 并且将新对象作为链表的头结点
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
    
    // 扩容数组  
    void resize(int newCapacity) {
     // 保存旧数组
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
     // 如果数组达到最大容量,return
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
     // 创建一个新的数组,newCapacity=2 * table.length
        Entry[] newTable = new Entry[newCapacity];
     // 将旧数组的内容转换到新的数组中
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
     // 重新计算阀值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
	//使我们的hash算法变得更复杂一些,也就是更散列一些,均匀分布,减少hash冲突
	final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

	
	//将旧表转移到新表中
    void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //变量旧table
    for (Entry<K,V> e : table) {
    		//按旧链表的正序遍历链表
        while(null != e) {
            //保存旧的哈希表对应的链表头的下一个结点
            Entry<K,V> next = e.next;
            //重新计算hash值
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //重新计算索引
            int i = indexFor(e.hash, newCapacity);
            //将newTable[i]上的Entry对象(第一次循环null),赋值给当前结点的下一个元素,妙!
            e.next = newTable[i];
            //将结点赋值到新的哈希表
            newTable[i] = e;
            e = next;
        }
    }
 }
   private static int roundUpToPowerOf2(int number) {
        return number >= MAXIMUM_CAPACITY
                ? MAXIMUM_CAPACITY
                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
  }

	//计算key的hash值
 final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }

    h ^= k.hashCode();

	//一般的hashcode高位都是0,为尽量避免hash冲突,进行扰动处理。
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
} 

//对table数组长度取模,计算索引   
 static int indexFor(int h, int length) {
        return h & (length-1);
    }   
 

小结:
1.hash表是第一次调用put时初始化的,默认容量是16。如果自定义了,也一定是2的n次方,因为要进行容量与hash值取模,获取索引。
2.添加元素,是通过元素hashcode与数组容量取模获取索引的。
3.为均分分布和尽量避免hash冲突,取索引时采用了动扰函数处理。
4.当key为null时,在hash表索引0处。
5.当key重复,新值会覆盖旧值。
6.当传入的初始容量不是2的幂,会取这个值最近的2的幂的值,如传入13,容量会是16。
7.当数组容量到达阈值,会进行扩容,是原来的2倍。
8.扩容会进行rehash,重新计算索引,并进行hash复杂化,使之分布更均匀。
9.如果产生hash冲突,采用链表的方法。
10.hash表中的链表是采用头插的方式。

五.get()方法

    public V get(Object key) {
    // 判断key是否为null 
        if (key == null) {
            return getForNullKey(); //去table[0]取值
        }
        //不为null,通过key获取获取对应下标的数组    
        Entry<K,V> entry = getEntry(key);
        
        return null == entry ? null : entry.getValue();
    }
 
 
    final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }
     // 根据key获取hashcode值
        int hash = (key == null) ? 0 : hash(key);
     // 通过indexFor()计算下标,然后在这个位置上循环单向链表。
        for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
            Object k;
        //取得table中hash值一样且key一样的Entity
            if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

小结:
1.通过key的hash值与容量取模计算出索引,取出元素。

六.remove()方法

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

final Entry<K,V> removeEntryForKey(Object key) {
		//如果数组为空,直接返回。
        if (size == 0) {
            return null;
        }
        //根据key删除元素,然后再通过indexFor得到要删除的元素所在的位置。
        //然后循环,找到要删除元素的key,这里删除使用的是链表出队的方式。
        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;
            }
             //指向下一个节点,继续循环查找
            prev = e;
            e = next;
        }

        return e;
    }

七.迭代器

EntrySet 是HashMap中的一个内部类,以Set类型用于保存hash表键值对。

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public Iterator<Map.Entry<K,V>> iterator() {
            return newEntryIterator();  // 创建迭代器
        }
        public boolean contains(Object o) {
            if (!(o instanceof Map.Entry)) // 比较类型
                return false;
            Map.Entry<K,V> e = (Map.Entry<K,V>) o;
            Entry<K,V> candidate = getEntry(e.getKey());
            return candidate != null && candidate.equals(e);
        }
        public boolean remove(Object o) {
            return removeMapping(o) != null;
        }
        public int size() {
            return size;
        }
        public void clear() {
            HashMap.this.clear();
        }
    }

public Set<Map.Entry<K,V>> entrySet() {
        return entrySet0();
    }

private Set<Map.Entry<K,V>> entrySet0() {
        Set<Map.Entry<K,V>> es = entrySet;
        return es != null ? es : (entrySet = new EntrySet()); // entrySet为空时创建一个EntrySet对象
    }

HashMap内部有三种迭代器

    private final class ValueIterator extends HashIterator<V> {
        public V next() {
            return nextEntry().value;
        }
    }

    private final class KeyIterator extends HashIterator<K> {
        public K next() {
            return nextEntry().getKey();
        }
    }

    private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() {
            return nextEntry();
        }
    }

真正的迭代器

// hash迭代器
private abstract class HashIterator<E> implements Iterator<E> {
        Entry<K,V> next;        // next entry to return
        int expectedModCount;   // For fast-fail
        int index;              // current slot
        Entry<K,V> current;     // current entry

        HashIterator() {
            expectedModCount = modCount; // 临时存储
            if (size > 0) { // advance to first entry
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        // 每次迭代都会调用次函数得到下一个Entry对象
        final Entry<K,V> nextEntry() {
        	//如果实际修改次数和预期修改次数不一致,抛异常。
            if (modCount != expectedModCount) 
                throw new ConcurrentModificationException();
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
            current = e;
            return e;
        }

        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount) // 判断
                throw new ConcurrentModificationException();
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }
    }

获取方法,见名知意,分别可以迭代不同的东西。

    Iterator<K> newKeyIterator()   { 
        return new KeyIterator();
    }
    Iterator<V> newValueIterator()   {
        return new ValueIterator();
    }
    Iterator<Map.Entry<K,V>> newEntryIterator()   {
        return new EntryIterator();
    }

八.jdk1.7头插造成死循环

一.死循环
死循环是多线程情况下数组扩容链表头插,引起的单链表循环指向。扩容会rehash重新定位元素的下标,并采用头插法迁移到新数组中。因为是头插,所以会将链表顺序反转,这是造成死循环的根本原因。

二.情景再现
在这里插入图片描述

正常扩容后
在这里插入图片描述

三.多线程下扩容
现在有线程A和线程B进行扩容,先看扩容关键方法
1.线程A在该处挂起
在这里插入图片描述
此时线程A:
新数组索引0处为E,此时e=D,next=A。在元素D即将插入索引2处时,cup执行权被线程B抢。
在这里插入图片描述

2.线程B抢到cpu执行权,并正常扩容,并将新数组赋值给table。
在这里插入图片描述
由于线程B完成扩容并将自己线程的工作空间内的新数组刷回到主空间HashMap中。此时的主空间HashMap就是B线程扩容后的HashMap。

3.随后线程A获取到了cpu执行权,继续执行newTable[i] = e。此时线程A继续完成该轮循环。

继续执行该轮循环将D完成迁移。但由于e=D,next=A。
在这里插入图片描述
4.然后线程A执行,此时e=A,next=B。
线程A继续执行:
在这里插入图片描述
5.由于线程B已经将扩容好的新数组刷回了主空间,然后e=B,next=A。
在这里插入图片描述
最后线程A刷回主空间,将线程B赋予的值覆盖。

三.jdk1.8

待续。。。