HashMap为什么这么快? ---深入理解HashMap的散列机制

在通过上篇博客了解了 Map 的维持内部的 键-值 对的基本方式之后,----不了解的看这篇(Java集合的基本概括), 我们便会思考, 在 HashMap 内部是如何组织和排列这些封装了 键-值对的 Map.Entry 实体呢? 如何组织才能达到更高的效率呢?

在了解 HashMap 的散列机制之前, 我们不妨来假设一下 HashMap 内部的数据结构的排列方式.

---

• 通过数组来维持内部的 键-值 对.

数组也许是我们最容易想到的一种数据结构, 我们知道, 存储一组数据最快的数据结构便是数组,这也是数组仅存的优点, 同样数组的缺陷也很明显, 比如 需要大量的连续的内存空间, 对元素的插入操作代价高昂,不能随意的扩大容量....等等.

因此,如果在 HashMap 的内部通过数组来维持 键-值 对, 在我们增加元素的时候似乎开销不大, 但是当我们用一个 key 去获取一个 value的时候, 想想我们该怎么去实现, 最常见的方式便是对 key 进行线性的 equals 查询, 从头查到尾, 这样的查询速度如此低下, 效率可想而知, 还有一个缺陷便就是数组与生俱来的, 需要太大的连续的内存空间, 所以通过数组来维持 HashMap 内部的数据缺陷太大,不值得.

• 通过链表来维持

在上面说过数组的那么多缺陷之后, 可能很多同学便会说到用链表, 没错链表似乎是解决了数组一个最致命的缺陷(需要大量的连续的内存空间), 但是链表仍然无法解决当我们用一个 key 去查询一个 value 的时候的低下的效率, 原因仍然是从头到尾的线性遍历.....

---

在上面我们说到用数组或者链表来维护内部的 键-值 对似乎效率都很低下,有没有一种能够结合数组和链表两者各自的优点然后又有着高效的查询速度的数据结构呢?

这便是 HashMap 内部维护数据的方式 --- 数组链表+散列机制

---

为速度而散列:

散列的价值便在于速度, 散列使得查询得以快速进行, 那么什么是数组链表,什么又是散列机制呢?

• 正所谓数组链表, 便是定义一个数组, 然后数组的每一个成员都是一条链表,数组只需要记载这条链表的引用即可, 这样不需要直接在数组内部存储 键-值 对而需要大量的连续的内存空间.
• 散列机制便是所谓的 hashCode 方法返回的 int 数, 他是通过对象的信息(默认是地址),通过某种散列的数学函数生成的一串 int 数字.

在了解了数组链表和散列机制后,我们再来想一想 HashMap 内部的 键-值 对是如何高效的维持的.

• 首先, 仍然会定义一个数组, 这个数组的是一个存储链表的引用数组, 从而解决了数组因存储对象而需要大量的连续的内存空间的缺陷.
• 然后, 我们在 put 一个元素的时候, 会调用 key 的 HashCode 方法生成一个散列码, 然后用这个散列码余上数组的容量,从而得到了一个数组的下标, 然后把这个 键-值 对存储在这个下标下对应的链表内.
• 在理想的情况下, 假设没有散列冲突(不同的对象产生了相同的散列码), 在我们用 key 去查询一个 value 的时候, 仍然用这个散列函数得到数组的下标, 从而直接获取了对应的 value, 这个效率简直了.....提升了多少倍啊.....
• 可是不会产生冲突的散列函数是几乎不存在的, 于是乎便会出现不同的 key 产生了相同的散列码, 在我们查询的时候就得采用 equals 线性遍历这少部分的因冲突而存储在一个链表中的 键-值 对, 但是这和全部的元素进行线性遍历, 效率仍然是提高了很多倍.

---

通过上面的解释, 采用 数组链表和散列机制 来实现的 HashMap为什么效率这么高的原因理解了, 下面来实现一个简单的 HashMap.

   class MyHashMap<k, v> extends AbstractMap<k, v> {

        private static final int SIZE = 16;
        LinkedList<Map.Entry<k, v>>[] buckets = new LinkedList[SIZE];

        @Override
        public v put(k key, v value) {
            int index = key.hashCode() % SIZE;
            if (buckets[index] == null) {
                buckets[index] = new LinkedList<>();
            }

            boolean found = false;
            Map.Entry<k, v> pair = new HashMap.SimpleEntry<>(key, value);
            v oldValue = null;
            // Begin to found whether already have this key and value.
            for (Entry<k, v> kvEntry : buckets[index]) {
                // If already have this key, replace value.
                if (kvEntry.getKey().equals(key)) {
                    oldValue = kvEntry.getValue();
                    found = true;
                    buckets[index].set(buckets[index].indexOf(kvEntry), pair);
                    break;
                }
            }
            // If not found, add the new key-value to the linked end.
            if (!found) {
                buckets[index].add(pair);
            }
            return oldValue;
        }

        @Override
        public v get(Object key) {
            // Use hash code to get index.
            int index = key.hashCode() % SIZE;
            if (buckets[index] == null) {
                return null;
            }
            for (Entry<k, v> kvEntry : buckets[index]) {
                // If have this key, return value.
                if (kvEntry.getKey().equals(key)) {
                    return kvEntry.getValue();
                }
            }
            return null;
        }

        @Override
        public Set<Entry<k, v>> entrySet() {
            HashSet<Entry<k, v>> entryHashSet = new HashSet<>();
            for (LinkedList<Entry<k, v>> bucket : buckets) {
                if (bucket != null) {
                    entryHashSet.addAll(bucket);
                }
            }
            return entryHashSet;
        }
    }

• 看了上面实现一个简单的 HashMap 的原理后, 我们便明白为什么当我们使用自定义的类型作为 键 的时候必须同时覆写 equals 和hashcode 方法了.
• 一个好的散列函数应该要能跟产生均匀的散列码, 并且散列码并不要求唯一, 更加关注的应该是其生成的速度,我们最好使用对象的某些有意义的信息来生成散列码.
• 用来生成散列码的信息应该是不能轻易改变的值,如果你对同一个 key 调用 hashCode 却生成了两个不一样的散列码, 那么你将无法获取到之前的 value.

未完待续......对HashMap源码的解析.....