Map简单解析

1.Map的使用以及效率问题

在使用map.entryset时可以知道这是一个导出Map所有键值对的函数集合，其中entry指的是键值对基本单位条目，其实在map接口就已经定义并且有simpleentry,ImmutableEntry(不可更改)两个实现，在实现MAP接口的类中也是使用entry为单位，以数组的形式存储

主要围绕几种典型的实现HashMap，concurrentHashMap,linkedHashMap

当我们使用hashmap时，其实内部已经给我们制定了数组大小，16kb（可以指定，所以当我们使用时尽量估计其可能大小，因为扩容是一件复制过程），阀值threshold 0.75f（超过就会以2进行扩容）

 this(initialCapacity, DEFAULT_LOAD_FACTOR);//默认大小

 void addEntry(int hash, K key, V value, int bucketIndex) {

        if ((size >= threshold) && (null != table[bucketIndex])) {

            resize(2 * table.length);//2倍扩容

            hash = (null != key) ? hash(key) : 0;

            bucketIndex = indexFor(hash, table.length);

        }

        createEntry(hash, key, value, bucketIndex);

    }

当我们put加入entry时，存放在entry[]中，大致过程是，计算其key的hash值，然后将hash与entry.size容量进行位运算，计算出其在entry[]中位置，其中我们都知道的同一key值会进行覆盖，不会增加真实存放容量大小，会返回原value值，代码如下

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

    }

扩容过程中是对key的一次hash计算，和重新在新数组中进行定位，所以除了复制复制之后的消耗至少还有每个entry的indexfor()损耗

  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;

            }

        }

    }

至于hashmap具有高效率的读取操作，从put()就应该能够得出，不管是增加或是读取，在entry数组中是根据key与size进行位运算后直接得出在数组中的位置，代码如下

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();

        // 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);

    }

位运算

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

    }

 

HashMap的移除操作，有点不是很不明白，但是把自己的认为写下来

hashmap内部是对entry进行了扩展的，其中增加了了一个Entry next属性，在createEntry方法内

  void createEntry(int hash, K key, V value, int bucketIndex) {

        Entry<K,V> e = table[bucketIndex];//获取entry初始的数组，这里面的entry应该是在#1构造过程中entry没

//有任何值

        table[bucketIndex] = new Entry<>(hash, key, value, e);//这里面把初始化的entry放进去，就相当每

//个entry都含有一个初始化的entry，#2这就相当于remove操作就是使用这个entry来替代原来的entry 

        size++;

    }

#1

 private void inflateTable(int toSize) {

        // Find a power of 2 >= toSize

        int capacity = roundUpToPowerOf2(toSize);

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);

        table = new Entry[capacity];

        initHashSeedAsNeeded(capacity);//初始化

    }

 

#2

 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;

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

            //替代(没有使用比如标志清除位来进行逻辑判断，或者采用其他方式，使用空间换时间，而且没有其他过多的操作，直接调用方法来进行替换，就又使entry恢初

//始状态，个人认为，其实这里没有怎么看明白，)

                if (prev == e)

                    table[i] = next;

                else

                    prev.next = next;

                e.recordRemoval(this);

                return e;

            }

            prev = e;

            e = next;

        }

        return e;

    }

 

 

至于hashmap的其他操作，containkey,putall，clear等基本是在上面实现的

 

对于map的并发控制，已经做出控制的concurrenthashmap，继承AbstractMap(内部重写了HashEntry<K,V>，并没有继承Hashmap),实现ConCurrentMap接口，内部进行同步控制是使用Reentrantlock()锁机制,Segment

 static final class Segment<K,V> extends ReentrantLock implements Serializable 

 

  final V put(K key, int hash, V value, boolean onlyIfAbsent) {

            HashEntry<K,V> node = tryLock() ? null :

                scanAndLockForPut(key, hash, value);//获取锁

            V oldValue;

            try {

                HashEntry<K,V>[] tab = table;

                int index = (tab.length - 1) & hash;

                HashEntry<K,V> first = entryAt(tab, index);

                for (HashEntry<K,V> e = first;;) {

                    if (e != null) {

                        K k;

                        if ((k = e.key) == key ||

                            (e.hash == hash && key.equals(k))) {

                            oldValue = e.value;

                            if (!onlyIfAbsent) {

                                e.value = value;

                                ++modCount;

                            }

                            break;

                        }

                        e = e.next;

                    }

                    else {

                        if (node != null)

                            node.setNext(first);

                        else

                            node = new HashEntry<K,V>(hash, key, value, first);

                        int c = count + 1;

                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)

                            rehash(node);

                        else

                            setEntryAt(tab, index, node);

                        ++modCount;

                        count = c;

                        oldValue = null;

                        break;

                    }

                }

            } finally {

                unlock();//释放锁

            }

            return oldValue;

        }

 

 

linkedHashMap继承了HashMap，实现Map接口，从字面意思上看，就是在原来具有HashMap的基础上添加了链表的特性，以维护一个双向链表来对map映射关系进行排序（规则为map.key先后顺序），那么具体表现和内部的一些知识点：

双向链表的构造具体还是对map.entry进行重构，就像hashmap中entry增加了.next通过保存初始化entry进行清除原来的entry(key)，具体为像链表一样增加一个前驱节点指向和一个后驱节点指向，after,before,而保存前驱和后驱节点的当前节点用header来保存，这个做法在map的具体实现类里面（重写entry）很常见且非常有用，具体的整个实现尚未完全弄懂，有待研究

entry一部分 

private static class Entry<K,V> extends HashMap.Entry<K,V> {

        // These fields comprise the doubly linked list used for iteration.

        Entry<K,V> before, after;//前驱和后驱

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {

            super(hash, key, value, next);//next 在remove() entry使用

        }

        /**

         * Removes this entry from the linked list.

         */

        private void remove() {

            before.after = after;

            after.before = before;

        }

        /**

         * Inserts this entry before the specified existing entry in the list.

         */

        private void addBefore(Entry<K,V> existingEntry) {

            after  = existingEntry;

            before = existingEntry.before;

            before.after = this;

            after.before = this;

        }

 

}

具体构建链表代码

 void addEntry(int hash, K key, V value, int bucketIndex) {

        super.addEntry(hash, key, value, bucketIndex);

        // Remove eldest entry if instructed

        Entry<K,V> eldest = header.after;

        if (removeEldestEntry(eldest)) {

            removeEntryForKey(eldest.key);

        }

    }

    /**

     * This override differs from addEntry in that it doesn't resize the

     * table or remove the eldest entry.

     */

    void createEntry(int hash, K key, V value, int bucketIndex) {

        HashMap.Entry<K,V> old = table[bucketIndex];

        Entry<K,V> e = new Entry<>(hash, key, value, old);

        table[bucketIndex] = e;

        e.addBefore(header);

        size++;

    }

至于HashTable直接实现map接口，不允许key,value=null，是线程安全的，使用synchronized同步机制，又实现了dictionary，顾名思义具有类似词典的映射功能，只是其key，value规定object对象，即为对象集合（jdk注：此类已过时。新的实现应该实现 Map 接口，而不是扩展此类），虽然map中k-v需要进行装箱和拆箱，而且类型检查，类型擦除，损耗性能，但是更为灵活，我想这可能是尽管hashtable与hashmap（保证线程安全之后）比较效率有较小差异，而且步骤少，但是大家却喜欢使用hashmap的原因。

TreeMap是一种二叉树结构的存储方式，并没有使用数组形式，可以看出查询效率应该没有以hashmap高，但是因为在存储过程中。可以进行key的compare所以treemap是可以理解为有序的结构，其中remove操作，应该是将关联节点置为null，添加即创建entry，关联节点，这种方式在设计模式上可以理解为组合模式，使用数组的确不合适，处理麻烦，我试过实现。在lucene为例的索引中倒排列表里面的单词的有一种方式是采用这种形式进行存储的。具体如何实现，详细的东西，源码神马的看了都非常清晰和透彻

以上总结为对map的数据类型的一些认知，个人学习总结使用，虽然大部分以源代码形式，而且可能有些还不正确，讲个大概的数据类型的实现思路，但是这个对于使用数据类型的不同场景的选取有一些帮助，了解这些数据类型之间的关系和性能问题的出现与解决有一定提升。

附1：

线程安全一般3重办法，具体网上资料比较多：

1.信号量semaphore

2.锁机制lock（同步synchronized，在jvm中也是锁机制，只是具体指令不一样）

3.CAS（比较和交换算法，jdk有提供一些此算法的实现类型在java.util.concurrent.atomic中，或者使用第三方AMINO框架提供的数据类型）
附2：
查看源码可以下载open-jdk，如果找不到可以使用jd-gui反编译class,非常好用，或者直接在krugle里面搜索，基本可以找到相关的类和扩展信息。