Java数据结构源码分析-HashMap

落日映苍穹つ 2022-08-23 00:52 157阅读 0赞

## 1.HashMap ##

### 1.1 Map接口 ###

在开始介绍HashMap的源码前，我们先来了解下HashMap的在内存的数据组织方式：  
整个结构分为两部分，第一部分是一个Entry\[\]数组，其数组的索引就是hash之后的slot位置。 第二部分是一个链表，每个Entry对象都会有一个Entry next的引用指向下一个Entry对象，如此当出现冲突时，只需要将冲突的数据加入到链表中就行了  
![这里写图片描述][u_2905135965_2708170433_fm_21_gp_0.jpg]  
接下来，我们来看看Map的接口形式，其定义了构造Map最关键的两个核心接口和方法，Map和Entry，不同类型的Map会使用不同的Entry来实现。

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

### 1.2 HashMap源码分析 ###

在开始HashMap具体方法之前我们先来看看，其中几个比较重要的内部类的作用

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> { 
            final K key;
            V value;
            Entry<K,V> next;
            int 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
        }
    }
    类：Entry
    该类是用于构造HaspMap数据结构的核心类。其主要用于保存数据
    类：HashIterator
    该类用于遍历HashMap的Entry,按照列的顺序，从数组的第一列的所有Entry到最后一列的Entry

接下来我们分析HashMap的使用过程：

1.HashMap的内存分配过程
    Map map1=new HashMap(10,0.8);
    上述过程中并不会立即对Map进行分配内存，即table任然是EMPTY_TABLE;
    transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
    static final Entry<?,?>[] EMPTY_TABLE = {};
    其内存的分配是第一次调用put方法向容器中插入数据的时候。内存分配的大小是大于initialCapacity的最小2的幂级数。例如此处为2^4>=10
    2.threshold为threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); 即其是table分配大小*loadFactor
    该Threshold和HashMap中table的重新分配大小有关，当table中原始大于threshold，并且该次插入数据的位置产生了冲突，那么将会按照现有Map的大小的2倍进行重新分配，并进行新的hashseed的重新计算和现存元素的重新hash.
    3.HashMap在插入数据时遇到冲突，会将冲突的数据插入到链表的表头位置，对于key为null的数据对，会别插入到table[0]的位置
    4.modCount表示HashMap被修改的次数，在每次调用put、remove、clear等方法时，都会加一

### 1.3 插入操作 ###

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            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;
        }
    
    private V putForNullKey(V value) {
            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;
        }
    
    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];
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
        }

对于put方法：首先会通过hash(key)和indexFor方法去获取key在table中slot的位置，然后通for循环去遍历链表，如果存在现有key则替换，返回旧值。否则addEntry去插入数据。  
在addEntry方法中会首先判断HashMap的load是否超过阈值threshold，如果是扩大一倍内存，并rehash原有数据，并重新计算slot的位置。然后通过设置Entry的hash、key、value、next几个字段，并使用链表的表头插入方法插入数据。

### 1.3 删除操作 ###

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;
            }
            int hash = (key == null) ? 0 : hash(key);
            int i = indexFor(hash, table.length);
            Entry<K,V> prev = table[i];
            Entry<K,V> e = prev;
            //循环更新prev和e，根据删除的数据是否在表头分开考虑
            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;
        }
    //如果找到要删除的key，则返回value，否则返回为null
    
    //清空方法，只需要把table的各个位置引用赋值为空，则gc负责回收栈上的对象空间
    public void clear() {
            modCount++;
            Arrays.fill(table, null);
            size = 0;
     }

### 1.4 其他操作 ###

//双层循环查找是否存在value
    public boolean containsValue(Object value) {
            if (value == null)
                return containsNullValue();
    
            Entry[] tab = table;
            for (int i = 0; i < tab.length ; i++)
                for (Entry e = tab[i] ; e != null ; e = e.next)
                    if (value.equals(e.value))
                        return true;
            return false;
        }
    
    public Object clone() {
            HashMap<K,V> result = null;
            try {
                result = (HashMap<K,V>)super.clone();
            } catch (CloneNotSupportedException e) {
                // assert false;
            }
            if (result.table != EMPTY_TABLE) {
                result.inflateTable(Math.min(
                    (int) Math.min(
                        size * Math.min(1 / loadFactor, 4.0f),
                        // we have limits...
                        HashMap.MAXIMUM_CAPACITY),
                   table.length));
            }
            result.entrySet = null;
            result.modCount = 0;
            result.size = 0;
            result.init();
            result.putAllForCreate(this);
    
            return result;
        }
    
    //首先clone HashMap对象本身，然后通过result.inflateTable方法clone HashMap中的table对象，
    //其次putAllForCreate取出HashMap中的Entry对象，并构造新的Entry对象并将Key和Value的引用传递给新的Entry,
    //从而实现元素的浅拷贝。 
    //注意：HashMap的clone只是clone了HashMap的table对象，而table中的元素并没有被拷贝，其拷贝的是对象的引用。因此其是浅层的拷贝，
    //如果想就行深层次拷贝可以通过使用seriablize手段来实现
    public Object clone() {
            HashMap<K,V> result = null;
            try {
                result = (HashMap<K,V>)super.clone();
            } catch (CloneNotSupportedException e) {
                // assert false;
            }
            if (result.table != EMPTY_TABLE) {
                result.inflateTable(Math.min(
                    (int) Math.min(
                        size * Math.min(1 / loadFactor, 4.0f),
                        // we have limits...
                        HashMap.MAXIMUM_CAPACITY),
                   table.length));
            }
            result.entrySet = null;
            result.modCount = 0;
            result.size = 0;
            result.init();
            result.putAllForCreate(this);
    
            return result;
        }
    
    //HashMap的持久化
    //从持久化的对象字段可以看出，其主要分为如下两部分：
    //1、写入table相关的属性包括threshold、size、length用于重建table 
    //2、table中保存的对象的持久化，分别持久化key和value字段，
    //要求改类对象都实现了Seriablizable接口，否则会报错
    private void writeObject(java.io.ObjectOutputStream s)
            throws IOException
        {
            // Write out the threshold, loadfactor, and any hidden stuff
            s.defaultWriteObject();
    
            // Write out number of buckets
            if (table==EMPTY_TABLE) {
                s.writeInt(roundUpToPowerOf2(threshold));
            } else {
               s.writeInt(table.length);
            }
    
            // Write out size (number of Mappings)
            s.writeInt(size);
    
            // Write out keys and values (alternating)
            if (size > 0) {
                for(Map.Entry<K,V> e : entrySet0()) {
                    s.writeObject(e.getKey());
                    s.writeObject(e.getValue());
                }
            }
        }
    private void readObject(java.io.ObjectInputStream s)
             throws IOException, ClassNotFoundException
        {
            // Read in the threshold (ignored), loadfactor, and any hidden stuff
            s.defaultReadObject();
            if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
                throw new InvalidObjectException("Illegal load factor: " +
                                                   loadFactor);
            }
    
            // set other fields that need values
            table = (Entry<K,V>[]) EMPTY_TABLE;
    
            // Read in number of buckets
            s.readInt(); // ignored.
    
            // Read number of mappings
            int mappings = s.readInt();
            if (mappings < 0)
                throw new InvalidObjectException("Illegal mappings count: " +
                                                   mappings);
    
            // capacity chosen by number of mappings and desired load (if >= 0.25)
            int capacity = (int) Math.min(
                        mappings * Math.min(1 / loadFactor, 4.0f),
                        // we have limits...
                        HashMap.MAXIMUM_CAPACITY);
    
            // allocate the bucket array;
            if (mappings > 0) {
                inflateTable(capacity);
            } else {
                threshold = capacity;
            }
    
            init();  // Give subclass a chance to do its thing.
    
            // Read the keys and values, and put the mappings in the HashMap
            for (int i = 0; i < mappings; i++) {
                K key = (K) s.readObject();
                V value = (V) s.readObject();
                putForCreate(key, value);
            }
        }

注意：  
out = new ObjectOutputStream(memoryBuffer);  
out.writeObject(src);  
在调用如上方法进行序列化时，其要求src必须实现serizable接口，并且其字段也必须实现了serizable接口，并且对于每个对象如果实现了writeObject方法，那么在序列化该对象的时候回调用该对象的writeObject方法。writeObject方法主要是用于个性化定制该对象的序列化方法

private void writeSerialData(Object obj, ObjectStreamClass desc)
            throws IOException
        {
            ObjectStreamClass.ClassDataSlot[] slots = desc.getClassDataLayout();
            for (int i = 0; i < slots.length; i++) {
                ObjectStreamClass slotDesc = slots[i].desc;
                //通过反射判断是否有writeObject方法，有则使用该方法序列化对象
                if (slotDesc.hasWriteObjectMethod()) {
                    PutFieldImpl oldPut = curPut;
                    curPut = null;
                    SerialCallbackContext oldContext = curContext;
    
                    if (extendedDebugInfo) {
                        debugInfoStack.push(
                            "custom writeObject data (class \"" +
                            slotDesc.getName() + "\")");
                    }
                    try {
                        curContext = new SerialCallbackContext(obj, slotDesc);
                        bout.setBlockDataMode(true);
                        slotDesc.invokeWriteObject(obj, this);
                        bout.setBlockDataMode(false);
                        bout.writeByte(TC_ENDBLOCKDATA);
                    } finally {
                        curContext.setUsed();
                        curContext = oldContext;
                        if (extendedDebugInfo) {
                            debugInfoStack.pop();
                        }
                    }
    
                    curPut = oldPut;
                } else {
                //否则调用默认方法序列化对象
                    defaultWriteFields(obj, slotDesc);
                }
            }
        }

[u_2905135965_2708170433_fm_21_gp_0.jpg]: http://img4.imgtn.bdimg.com/it/u=2905135965,2708170433&fm=21&gp=0.jpg