java HashMap 实现原理

在java语言编程中,我们经常会遇到成对出现的数据,比如 姓名和年龄,书籍名称和出版社。这些数据都是key和value的形式组织在一起。
一般我们会使用Map这种数据结构来存储这些数据,你可以看成一个二维的数组。接下来,我会讲讲java中和HashMap相关的几个类和接口,帮助和学习理解HashMap这种结构。

Map.java

Map在java中所有Map实现类的总接口。他定义了所有Map所具备的基本的set put containsKey remove等方法,且存在一个内部的子接口Entry,每一组k-v都是这个Entry的实例,说白了就是put操作,会在Map内部new一个Entry,然后k-v都会塞到这个Entry实例中。

AbstractMap.java

java中还存在了一个Map接口的抽象实现类AbstractMap。

public abstract class AbstractMap<K,V> implements Map<K,V> {...}

如其名是个抽象类,其实现了Map接口中声明的方法,包括containsValue get put等方法,且实现了Map.Entry接口。
AbstractMap类中内部维护了一个set结构用于维护数据,我们都知道set是无序的,所以也导致了大部分map里的数据也是无序的。当然这个set也是抽象的,并没有说明具体的实现。
public abstract Set<Entry<K,V>> entrySet()
举例一下这个AbstractMap的get方法,get方法使用了非常粗暴的迭代循环找到对应的数据,时间复杂度和空闲复杂度都是O(n),如果数据量比较大且查询比较多的情况下,效率比较低下。

public V get(Object key) {
       Iterator> i = entrySet().iterator();
       // map中key可以是null null值用==null判断
       if (key==null) {
           while (i.hasNext()) {
               Entry e = i.next();
               if (e.getKey()==null)
                   return e.getValue();
           }
       } else {
           while (i.hasNext()) {
               Entry e = i.next();
               // 非空的key 用equals判断
               if (key.equals(e.getKey()))
                   return e.getValue();
           }
       }
       return null;
   }

 

HashMap.java

而现在要说的HashMap类继承于AbstractMap,实现了Map接口。AbstractMap已经帮我们实现了大部分map里的操作。

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
}

既然名字都带了Hash,那么这个实现类肯定和Hash值密切相关,那么一般一个对象的hash值都是通过Object.hashcode()方法获取的,当然你也可以重写,然后还有一个很重要的方法equals方法。一般这2个是成对出现的,否则出现2个对象hashcode一致,equals返回false的情况就尴尬了。这到底是不是同一个对象?
之前提到AbstractMap类中的数据都存放到了Set中,因为set的无序性,导致我们找一个value非常麻烦,必须循环遍历。那么有没有什么办法,提高查找效率、回顾一下java的基础知识,论查找效率最基本的数组肯定是最快的,直接通过下标查找,复杂度都是(1)。那么我们能不能把这个Set替换成数组[].HashMap就是这么干的!

  transient Node<K,V>[] table;

Node类是HashMap的子类,对应Map.Entry接口。数据都存到了一个数组里。这样就会有一个问题,我怎么知道key对应的数组下标?我怎么从数组里拿到我想要的数据?
这个时候hash算法就出场了,hashmap里有一套算法通过对key的hash计算获取这个key对应在数组里的坐标。
那么一个get操作就变成了如下步骤

key->hash(key)->index->get(index)

当然简单的hashcode是无法转换成index的。
Object对hashcode方法的方法定义如下

public native int hashCode();

它返回的是一个int,这个int的值肯定大于数组的长度,那么怎么才能让这个int转换成合法的下标呢?

hashcode(key)%array.length

是不是很简单?循环数组就是这么实现的,直接首尾相连。
HashMap中获取hash的实现如下,我们看到获取的hash值不仅仅调用了hashcode还继续执行了位运算。
这样做的好处是,可以将hashcode高位和低位的值进行混合做异或运算,而且混合后,低位的信息中加入了高位的信息,这样高位的信息被变相的保留了下来。掺杂的元素多了,那么生成的hash值的随机性会增大。

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

但这又出现了一个新的问题,一个数组的长度就这么点,hash值可能会不会重复,转换成下标的时候就很有可能了。
相同下标的k-v怎么存?非常简单,我们回顾下HashMap中定义的k-v容器 Node。

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

我们发现node里不仅存放了 key 和value,还存放了对应的hash值,以及一个Node实例,名字叫next。意思很明白了,如果hash出来的下标重复了,出现了冲突,那么当前索引位置的node就会set一下这个next,这个next就是新put的k-v。
也就是说,出现冲突的时候,新put的键值对和原本就存在的键值对构成一个链表。Node中的next存放了下一个node的引用。

另外如果map中存入了非常多的键值对,那么数组中会存在很多的hash冲突(重复的hash值),所以会出现很多很长的链表,用于存放相同索引位置的键值对。
又又所以,hashmap对此,做了优化。数据量比较小的时候,用链表存放这些冲突的数据,数据量大的时候,优化成了红黑树,提高查找效率。这个阈值由变量TREEIFY_THRESHOLD决定,默认值是8;
红黑树的结构定义为hashmap的子类TreeNode

static final class TreeNode=<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    }

这颗红黑树的查找算法定义如下

final TreeNode find(int h, Object k, Class kc) {
    TreeNode p = this;
    do {
         int ph, dir; K pk;
         TreeNode pl = p.left, pr = p.right, q;
         if ((ph = p.hash) > h)
             p = pl;
         else if (ph < h)
             p = pr;
         else if ((pk = p.key) == k || (k != null && k.equals(pk)))
             return p;
         else if (pl == null)
             p = pr;
         else if (pr == null)
             p = pl;
         else if ((kc != null ||
                   (kc = comparableClassFor(k)) != null) &&
                  (dir = compareComparables(kc, k, pk)) != 0)
             p = (dir < 0) ? pl : pr;
         else if ((q = pr.find(h, k, kc)) != null)
             return q;
         else
             p = pl;
     } while (p != null);
     return null;
 }

未完待续。。。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注