首页 > 代码库 > java之Map源代码浅析

java之Map源代码浅析

Map是键值对。也是经常使用的数据结构。

Map接口定义了map的基本行为。包含最核心的get和put操作,此接口的定义的方法见下图:

技术分享

JDK中有不同的的map实现,分别适用于不同的应用场景。如线程安全的hashTable和非线程安全的hashMap.

例如以下图是JDK中map接口的子类UML类图,当中有个特例Dictionary已经不建议使用:

技术分享

Map接口中的方法我们须要关注的就是get、put 和迭代器相关的方法如entrySet()、keySet()、values()方法。

Entry

在開始分析map之前,首先了解map中元素的存储。我们知道map能够觉得是键值对的集合,java中map使用Entry存储键值对,这是一个接口,其定义例如以下,简单明了。接口方法主要是对键和值进行操作。

interface Entry<K,V> {
   
    K getKey();
 
    V getValue();
 
   V setValue(V value);
 
    boolean equals(Object o);
 
    int hashCode();
    }

AbstractMap

Map接口的抽象实现。见下面演示样例实现代码:

Map<String,String> a = /**
        *
        *抽象map实现示意,依据文档说。和list接口及其相似。
        *
        *map分为可变和不可变两种。不可变仅仅需实现 entrySet方法就可以,且返回的 set的迭代器不能支持改动操作。
        *
        *可变map,须要实现put方法,然后 entrySet的迭代器也须要支持改动操作
        *
        *
        *AbstractMap 里面实现了map的梗概,可是其效率难说,比方其get方法中时採用方法entrySet实现的。

* *通常子类用更有效率的方法覆盖之。

如hashMap中覆盖了keySet 、values 、get方法等 */ new AbstractMap<String,String>(){ /* * 返回map中的元素集合,返回的集合通常继承AbstractSet 就可以。 */ @Override public Set<Map.Entry<String, String>> entrySet() { return new AbstractSet<Map.Entry<String,String>>() { @Override public Iterator<java.util.Map.Entry<String, String>> iterator() { return null; } @Override public int size() { return 0; } }; } /* * 默认实现抛出异常,可变map须要实现此方法 */ @Override public String put(String key, String value) { return null; } };

HashMap

hashMap继承abstractMap,是相当经常使用的数据结构,採用hash散列的思想。能够在O(1)的时间复杂度内插入和获取数据。其基本实现能够分析上个小节中的抽象方法,文章

浅析HashMap的实现和性能分析 已经对hashMap的实现、put和get操作进行了较具体的说明。

这里不再赘述。关键看他的迭代器实现,这里仅仅分析下entrySet()方法,而keySet()和values()方法实现与之中的一个脉相承。

关于迭代器。见以下摘出的部分源代码和相关凝视:

/**
         * 返回map中全部的键值对集合,用于遍历
         */
        public Set<Map.Entry<K,V>> entrySet() {
       return entrySet0();
        }
 
        /**
         * 延迟初始化,仅仅有使用的时候才构建。
         *
         * values()和 keySet()方法也使用了相似的机制
         */
        private Set<Map.Entry<K,V>> entrySet0() {
            Set<Map.Entry<K,V>> es = entrySet;
            return es != null ? es : (entrySet = new EntrySet());
        }
       
       
 
        /**
         * 真正的 enterySet,是一个内部类,其关键实现是迭代器实现。
         *
         * values()和 keySet()方法也相应了相应的内部类。
         * 相应的自己的迭代器实现。关键在于这个迭代器
         *
         */
        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();
            }
        }
       
       
        /**
         * entrySet迭代器,继承HashIterator,实现next方法。
         * values()和 keySet()方法,也是继承HashIterator。仅仅是实现next 的方法不同。
         *
         * 能够对照下。
         *
         * 关键在于HashIterator
         *
         *
         */
        private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
            public Map.Entry<K,V> next() {
                return nextEntry();
            }
        }
       
        /**
         *
         *keySet()相应的迭代器
         */
        private final class KeyIterator extends HashIterator<K> {
            public K next() {
                return nextEntry().getKey();
            }
        }
       
       
        /**
         *
         * hashmap entrySet() keySet() values()的通用迭代器
         */
        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;
                    //构造时候,在数组中查找第一个不为null的数组元素,即Entry链表,关于hashmap的实现请看
                    //本人前面的博文
                    while (index < t.length && (next = t[index++]) == null)
                        ;
                }
            }
 
            public final boolean hasNext() {
                return next != null;
            }
 
            /**
             * 关键实现,非常easy看懂。查找next的时候,和构造迭代器的时候一样
             */
            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;
            }
 
        }

HashTable

实现和hashMap基本一致,仅仅是在方法上加上了同步操作。

多线程环境能够使用它。只是如今有ConcurrentHashMap了,在高并发的时候,能够用它替换hashtable.

LinkedHashMap

hashMap可能在某些场景下不符合要求,由于放入到当中的元素是无序的。而LinkedHashMap则在一定程度上解决问题。

其在实现上继承了HashMap,在存储上扩展haspMap.enteySet,增加了before、after字段。把hashMap的元素用双向链表连接了起来。这个双向链表决定了它的遍历顺序。

其顺序一般是插入map中的顺序,可是它有一个字段accessOrder当为true时,遍历顺序将是LRU的效果。

研究它的有序性。我们能够从put方法、get方法和遍历的方法入手。首先看get方法:

/**
         * 直接调用父类的getEntry方法。

关键在于 * e.recordAccess(this) 这句代码 */ public V get(Object key) { Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; e.recordAccess(this); return e.value; } /** * Entry.recordAccess 方法 * * 假设是訪问顺序(accessOrder=true),那么就把它放到头结点的下一个位置 * 否则什么也不做。 * 这样就能够依据初始 accessOrder 属性,来决定遍历的顺序。 */ void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } }



Put方法:

/**
         * put方法调用此方法,覆盖了父类中的实现,
         */
        void addEntry(int hash,K key, V value, int bucketIndex) {
            createEntry(hash, key, value, bucketIndex);
 
            // Remove eldest entry if instructed, else grow capacity if appropriate
            Entry<K,V> eldest = header.after;
            //回调。假设有必要移除在老的元素。最新的元素在链表尾部。
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            } else {
                if (size >= threshold)
                    resize(2 * table.length);
            }
        }
 
        /**
         *
         */
        void createEntry(int hash,K key, V value, int bucketIndex) {
            HashMap.Entry<K,V> old = table[bucketIndex];
       Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
            table[bucketIndex] = e;
            //本质是插入双向链表的末尾
            e.addBefore(header);
            size++;
        }
       
       
        /**
         * 插入到 existingEntry的前面,由于是双向链表。当existingEntry是 header时。
         * 相当于插入到链表最后。

* */ private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }



遍历迭代直接使用双向链表进行迭代接口,这里不赘述。能够看源代码非常easy理解。

注意的是实现上市覆盖了父类中相关的生成迭代器的方法。

TreeMap和CurrentHashMap都能够单独开一篇文章来分析了。这里简单说下。TreeMap是基于b树map,依据key排序。CurrentHashMap是并发包中的一个强大的类,适合多线程高并发时数据读写。

 

 

java之Map源代码浅析