HashMap源码分析

通读hashMap的源代码之后，发现他的数据结构是这样的。

阅读完源码知道，hashmap是会把indexFor()方法获得的index相同的那些entity放在数组的同一个位置，用一个next引用指向下一个entity，即index相同的entity组成了一个链表。这样来说，如果index的重复越多，链表越长，随机操作的效率就越低。那么jdk是如何计算index的呢？jdk中indexFor()方法的源码是:

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

其中leng是hashmap的大小，而h是key的hashCode经过hash()方法处理的结构，hash()方法源码：

    static int hash(int h) {
        // 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);
    }

都说遍历hashmap的时候不一定是按照元素放入的顺序来迭代的，这是怎么回事呢？来看hashmap迭代的关键代码:

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

通关HashIterator的构造方法和nextEntry方法知:entrySet是按深度优先遍历的，即构造完之后next会指向第一个不为null的元素，迭代的时候nextEntry返回当前元素，在结束的时候 next指向下一个不为空的元素，没有元素，则next为null，依次往下遍历直到next为null。
此外key和value的迭代hashmap都是以此类作为父类，写了自己的实现类。key的迭代类KeyIterator:

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

value的迭代类ValueIterator：

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

由此看，jdk的代码的面向对象设计是相当出色的，以后项目的架构设计可以很好的参考jdk。到此，之前的大部分疑问都解决了。还有几个疑问的是，其中一个就是，我们都知道hashmap在迭代的时候是不能修改的，那我们来看一下代码这是怎么回事呢？
在hashmap的几个修改方法中都会判断modCount != expectedModCount，如果这两个值不等就会抛出ConcurrentModificationException。 HashIterator构造的时候expectedModCount = modCount;迭代的时候不会修改expctedModCount和modCount,但put、remove都会修改modCount，故在迭代的时候会导致抛出 ConcurrentModificationException。看过官方的文档注释，貌似是为了防止hashmap在多线程下被修改，但问题是这样hashmap在单线程下也不能修改了，我认为这是一个不好的设计。我想多线程环境没有人会想到用hashmap不做任何同步处理，那样出问题的风险太大了。所以hashmap本身应该只是针对单线程环境的，那就没必要有这样的设计。

Chin的博客

程序的世界多奇妙

Comments