技术信息

浅析Java中HashMap实现原理

发布日期:2019-02-15      点击:

在正式进入该话题前,我们先简单了解一下Java中常用集合的分类及层级关系,如图:

这是Java集合较基本的分类图,可以看到我们常用的Map基本是由HashMap及Hashtable来实现,两者最大的区别在于:

1. HashMap是无序的,Hashtable是有序的。

2. Hashtable的方法是同步的,而HashMap的方法不是。这就意味着,虽然你可以不采取 任何特殊的行为就可以在一个多线程的应用中使用一个Hashtable,但你必须同样地为一个HashMap提供外同步。

3. 只有HashMap可以让你将空值作为一个表的条目的key或value,即只有一条记录可以是一个空的key,但任意数量的条目可以是空的value。

当然,除此之外还有其他的实现,例如:LikendHashMap、TreeMap、ConcurrentMap等,这几类Map之间的基本区别体现在:

1. 是否有序

2. 层级结构

3. 是否线程安全,及线程安全细粒度

4. 空值

以上仅用于简单了解JavaMap,下面我们看一下来自JDK的HashMap的基本实现:

HashMap的内部类Node实现:

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

HashMap的hash实现:

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

HashMap的get实现:

final HashMap.Node<K, V> getNode(int hash, Object key) {
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> first, e;
        int n;
        K k;
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof HashMap.TreeNode)
                    return ((HashMap.TreeNode<K, V>) first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

 

HashMap的put实现:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> p;
        int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            HashMap.Node<K, V> e;
            K k;
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof HashMap.TreeNode)
                e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

以上四段代码即是HashMap最基本也是最核心的代码,我们简单看一下,Node这个内部类实现了Map.Entry接口。不难看出Node即是用于存放Map单元数据的实体。

值得注意的是:Node中的next,为什么需要next,那么我们就需要看一下map的检索机制。

图中左侧Bucket相当于我们的Entry或Node,每一个Entry或Node都会有个next指向下一个Entry或Node。例如图中4位置存在三个Node,第一个会指向第二个,第二个会指向第三个,第三个指向空。为什么需要这样设计,那么我们还需要看一下hash的运算原理:

int ELFhash(char*key)
{
    unsigned long h=0;
    while(*key)
    {
        h = (h << 4) + *key++;
        unsigned long g = h & 0xF0000000L;
        if(g)
            h ^= g >> 24;
        h &= ~g;
    }
    return h % MOD;
}

这段代码即是ELFhash算法,不难看出,当给定一个Key时,产生的结果可能会相同。这就导致了Hash碰撞。要实现“快速根据key找到相应value”就必须实现“根据key能快速找到该Node所在位置即下标”。为了保证我们得到的Hash值无论是多少,我们总希望它能分布在我们指定长度的数组中,那么这就需要使用到与运算,下面我们来看一下与运算的原理:

以“5 & 12”为例,与运算即是对二进制做与运算,最后转回相应进制。十进制转二进制比较简单,让十进制不断的除以2,直到商为0,然后依次汇总余数即可。

这里5的二进制是101,12的二进制是1100,我们需要对101和1100做与运算,同为1即为1,否则为0,最后结果是0100,需要将0100转为10进制,二进制转十进制也比较简单,依次从最小位到最大位乘以2的位次数后累加。最后结果是4。那么上面“5 & 12”最终的结果即为4。

也许你会发现A&B运算后的结果总会小于A和B中较小的一个,没错,正是由于这个性质,我们才能实现将min&max 的结果分布在长度为min的数组中。实际操作中我们经常这样做:

int i = nodes.length & hash;

给定一个Key我们计算它的hash值后,将hash值和nodes的数组长度做与运算,这就使得我们任意一个Key都能分布在我们指定的数组中。当出现碰撞时(即两个key做完上述运算结果相同),这时我们通常会将后面的Node加入到最后一个Node的next中。这就产生了链表。

当这种情况发生时,就需要逐个检索指定链表中每个Node的Key是否引用同一个内存地址或是否相等,这主要取决于对象的equles实现,最终找到相应Node进行读取或修改操作。这就是HashMap的基本实现。下面我们根据这几项规则实现一个简单的Map,这里笔者命名为SelfMap,代码如下:

SelfMap实现:

/*
 *
 *  * Copyright 2018 https://www.minsx.com
 *  *
 *  * Licensed under the Apache License, Version 2.0 (the "License");
 *  * you may not use this file except in compliance with the License.
 *  * You may obtain a copy of the License at
 *  *
 *  *     http://www.apache.org/licenses/LICENSE-2.0
 *  *
 *  * Unless required by applicable law or agreed to in writing, software
 *  * distributed under the License is distributed on an "AS IS" BASIS,
 *  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  * See the License for the specific language governing permissions and
 *  * limitations under the License.
 *
 */
package com.goodsave.basic.selfmap;

public class SelfMap<K, V> {

    private K k;
    private V v;
    private Node<K, V>[] nodes = (Node<K, V>[]) new Node[7732345];

    V get(K key) {
        int hash = hash(key);
        int i = nodes.length & hash;
        Node<K, V> node = nodes[i];
        if (node.getKey() == key || (key != null && key.equals(node.getKey()))) {
            return node.getValue();
        } else {
            Node<K, V> nextNode = node.getNext();
            for (int index = 0; ; index++) {
                if (nextNode != null) {
                    if (nextNode.getKey() == key || (key != null && key.equals(nextNode.getKey()))) {
                        return nextNode.getValue();
                    } else {
                        nextNode = nextNode.getNext();
                    }
                } else {
                    break;
                }
            }
            return null;
        }
    }

    void put(K key, V value) {
        Node<K, V> node = null;
        int hash = hash(key);
        int i = nodes.length & hash;
        if ((node = nodes[i]) != null) {
            if (node.getKey() == key || (key != null && key.equals(node.getKey()))) {
                node.setValue(value);
            } else {
                Node<K, V> lastNode = node;
                Node<K, V> nextNode = node.getNext();
                Boolean exist = false;
                for (int index = 0; ; index++) {
                    if (nextNode != null) {
                        if (nextNode.getKey() == key || (key != null && key.equals(nextNode.getKey()))) {
                            nextNode.setValue(value);
                            exist = true;
                            break;
                        } else {
                            lastNode = nextNode;
                            nextNode = nextNode.getNext();
                        }
                    } else {
                        break;
                    }
                }
                if (!exist) {
                    lastNode.setNext(new Node<>(hash, key, value));
                }
            }
        } else {
            nodes[i] = new Node<>(hash, key, value);
        }
    }


    static int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
}

Node实现:

/*
 *
 *  * Copyright 2018 https://www.minsx.com
 *  *
 *  * Licensed under the Apache License, Version 2.0 (the "License");
 *  * you may not use this file except in compliance with the License.
 *  * You may obtain a copy of the License at
 *  *
 *  *     http://www.apache.org/licenses/LICENSE-2.0
 *  *
 *  * Unless required by applicable law or agreed to in writing, software
 *  * distributed under the License is distributed on an "AS IS" BASIS,
 *  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  * See the License for the specific language governing permissions and
 *  * limitations under the License.
 *
 */
package com.goodsave.basic.selfmap;

public class Node<K, V> {

    private int hash;
    private K k;
    private V v;
    private Node<K, V> next;

    public Node() {
    }

    public Node(int hash, K k, V v) {
        this.hash = hash;
        this.k = k;
        this.v = v;
    }

    public int getHash() {
        return hash;
    }

    public void setHash(int hash) {
        this.hash = hash;
    }

    public K getKey() {
        return k;
    }

    public void setKey(K k) {
        this.k = k;
    }

    public V getValue() {
        return v;
    }

    public void setValue(V v) {
        this.v = v;
    }

    public Node<K, V> getNext() {
        return next;
    }

    public void setNext(Node<K, V> next) {
        this.next = next;
    }
}

测试:

public class MainTest {

    @Test
    public void test() {
        SelfMap<String, String> map = new SelfMap<>();
        map.put("1","AAA");
        map.put("2","BBB");
        map.put("3","CCC");
        map.put("10004","DDD");
        System.out.println(map.get("10004"));
    }
}

需要注意的是:此处的1,3实际上已经发生了碰撞,尽管他们的Hash值分别为49、51但做完与运算后他们的位置均为49。

输出:

DDD
Process finished with exit code 0

结论:

Java HashMap的基本原理其实比较简单,不难看出其本质只是基于数组的实现,这种散列表的方式其优点是存取速度比较快,但在碰撞频繁的情况下对性能影响较大,是不建议使用的。值得一提是的不论是JDK的HashMap还是笔者这里的SelfMap都是线程不安全的。另外需要注意的是当每次计算的Hash不同时,这种方式会产生大量的数据而带来性能消耗也是不可取的,当然为了解决这些问题,JDK1.8后的版本中使用红黑树替代了链表,这篇文章暂且只介绍到这里。