【JAVA】六 JAVA Map 一 HashMap

缺乏、安全感 2022-08-22 04:56 168阅读 0赞

# **【JAVA】六 JAVA Map 一 HashMap** #

![这里写图片描述][20160529232032016]

# **JDK API** #

java.util  
Interface Map

Type Parameters:
    K - the type of keys maintained by this map
    V - the type of mapped values

## **All Known Subinterfaces:** ##

Bindings, ConcurrentMap<K,V>, ConcurrentNavigableMap<K,V>, LogicalMessageContext, 
    MessageContext, NavigableMap<K,V>, SOAPMessageContext, SortedMap<K,V>

## **All Known Implementing Classes:** ##

AbstractMap, Attributes, AuthProvider, ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, 
    HashMap, Hashtable, IdentityHashMap, LinkedHashMap, PrinterStateReasons, Properties, 
    Provider, RenderingHints, SimpleBindings, TabularDataSupport, TreeMap, UIDefaults, 
    WeakHashMap

--------------------

# **Map** #

先来看看 interface Map 的定义  
interface Map 定义了整体的数据结构  
下面我们一一介绍具体的实现类来说明

package java.util;
    
    public interface Map<K,V> {
        
        int size();
        boolean isEmpty();
        boolean containsKey(Object key);
        boolean containsValue(Object value);
        V get(Object key);
        V put(K key, V value);
        V remove(Object key);
        void putAll(Map<? extends K, ? extends V> m);
        void clear();
        Set<K> keySet();
        Collection<V> values();
        Set<Map.Entry<K, V>> entrySet();
    
        interface Entry<K,V> { // 子接口
            K getKey();
            V getValue();
            V setValue(V value);
            boolean equals(Object o);
            int hashCode();
        }
    
        boolean equals(Object o);
        int hashCode();
    
    }

--------------------

# **HashMap属性** #

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable
    {
        
    
        /**
         * 默认初始容量,必须是2的倍数 .
         * 为什么是2的倍数后面介绍到 .
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
        /**
         * 最大容量 1<<30.
         * 必须是2的倍数
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        /**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        /**
         * 一个空表实例,是一个Entry类型数组 . 
         */
        static final Entry<?,?>[] EMPTY_TABLE = {};
    
        /**
         * 表根据需要调整大小。长度必须是2的幂
         */
        transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    
        /**
         * map的当前长度.
         */
        transient int size;
    
        /**
         * 要调整大小的极限值（容量*默认计算阀值参数因子） 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;
    
        /**
         * 哈希表的负载系数.
         *
         * @serial
         */
        final float loadFactor;
    
        /**
         * 
         * 这个HashMap结构修改的次数
         * 结构修改是那些改变的映射
         * HashMap或修改其内部结构(例如重复)。
         * 这个字段是用来使迭代器的集合视图 HashMap很快失败。
         * (见ConcurrentModificationException)。
         * 
         */
        transient int modCount;
    }

--------------------

# **HashMap 构造方法** #

/**
         * 构造一个HashMap 
         * 初始容量 
         * 负载系数
         */
        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 = initialCapacity;
            init();
        }
    
        public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         *  默认初始大小 16 
         *  默认计算阀值参数因子 0.75
         */
        public HashMap() {
            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
        }
    
        /**
         * 接受map子集 , 将map子集转换为HashMap类型数据 . 
         * 默认计算阀值参数因子 .75
         * @param   m the map whose mappings are to be placed in this map
         * @throws  NullPointerException if the specified map is null
         */
        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);
        }

--------------------

# **HashMap添加值** #

**通过源码分析,明确清楚程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value。**

> hash 方法是位运算的过程.  
> HashMap 会在取模哈希前先做一次哈希,增大散列度.  
> 关于位运算可以移步到我的另一篇文章  
> [http://blog.csdn.net/maguochao\_mark/article/details/51010289][http_blog.csdn.net_maguochao_mark_article_details_51010289]

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

indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。

/**
         * 当 length 总是 2 的倍数时，h & (length-1)
         * 将是一个非常巧妙的设计：假设 h=5,length=16, 那么 h & length - 1 将得到 5；
         * 如果 h=6, length=16, 那么 h & length - 1 将得到 6  ; 
         * 如果 h=15,length=16, 那么 h & length - 1 将得到 15 ;
         * 但是当 h=16 时 , length=16 时，那么 h & length - 1 将得到 0 了；当 h=17 时 ,
         * length=16 时，那么 h & length - 1 将得到 1 了
         * 这样保证计算得到的索引值总是位于 table 数组的索引之内。 
         */
        static int indexFor(int h, int length) {
            return h & (length-1);
        }

--------------------

# **HashMap添加值 hashCode 相同** #

由于hash算法是取hashCode在进行位运算,那么难免会有hashCode相同的情况发生.  
那么这个时候HashMap是怎么添加值的呢?我们来通过一段代码来说明 .

package com.cn.mark.java.util;
    
    import java.util.HashMap;
    
    class Student {
    
        public Student(String name) {
            this.setName(name);
        }
    
        private String name;
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public int hashCode() {
            return 9999; // 测试 使得 hashCode 相同 
        }
    
        public boolean equals(Object obj) {
            Student student = (Student) obj;
            if (this.getName().equals(student.getName()))
                return true;
            return false;
        }
    }
    
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public class HashMapTest {
        
        public static void main(String[] args) {
            HashMap map = new HashMap();
            map.put(new Student("zhangsan"), "zhangsan");
            map.put(new Student("lisi"), "lisi");
        }
    }

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);//根据key计算hash值
            int i = indexFor(hash, table.length);//计算出索引
            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;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }
        void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);
                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) {
            Entry<K,V> e = table[bucketIndex];//会取出 zhangsan 的 Student 对象
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
        }

**我们看到createEntry时将 zhangsan 的 Student 对象 做为参数传递给了 new Entry<>(hash, key, value, e);方法.**

public class HashMap<K,V>
        extends AbstractMap<K,V>
        implements Map<K,V>, Cloneable, Serializable
    {
        
        static class Entry<K,V> implements Map.Entry<K,V> {
            Entry(int h, K k, V v, Entry<K,V> n) {
                value = v;
                next = n;
                key = k;
                hash = h;
            }
    }

**在new Entry<>(hash, key, value, e); 方法中是将 zhangsan 的 Student 对象 作为了 lisi的next属性关联这.  
也就是说 hash相同时会形成一个 Entry的单项链表,最先加入的Entry会在当前链表的最末端 .**

--------------------

# **HashMap 扩大容量** #

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，这是一个常用的操作，而在HashMap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。  
那么HashMap什么时候进行扩容呢？当HashMap中的元素个数超过 **数组大小\*loadFactor**时，就会进行数组扩容，**loadFactor的默认值为0.75**，这是一个折中的取值。也就是说，默认情况下，数组大小为**16**，那么当HashMap中元素个数超过**16\*0.75=12**的时候，就把数组的大小扩展为 **2\*16=32，即扩大一倍**，然后重新计算每个元素在数组中的位置，而这是一个**非常消耗性能的操作**，所以如果我们已经预知HashMap中元素的个数，那么**预设元素的个数能够有效的提高HashMap的性能**。

void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    
        void resize(int newCapacity) {
            Entry[] oldTable = table;
            int oldCapacity = oldTable.length;
            if (oldCapacity == MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return;
            }
    
            Entry[] newTable = new Entry[newCapacity];
            transfer(newTable, initHashSeedAsNeeded(newCapacity));
            table = newTable;
            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
        }
    
        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;
                }
            }
        }

--------------------

# **Fail-Fast机制** #

我们知道java.util.HashMap是线程不安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。  
这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。  
在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map注意到modCount声明为volatile，保证线程之间修改的可见性。

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;
            }
    
            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;
            }
        }

[20160529232032016]: /images/20220722/fcf1f22a141f4d9286d5d75c2d3cd4c0.png
[http_blog.csdn.net_maguochao_mark_article_details_51010289]: http://blog.csdn.net/maguochao_mark/article/details/51010289