java集合类深入分析之HashSet, HashMap篇

简介

    Map和Set是比较常用的两种数据结构。我们在平常的编程中经常会用到他们。只是他们的内部实现机制到底是怎么样的呢？了解他们的具体实现对于我们如何有效的去使用他们也是很有帮助的。在这一篇文章里，已经对HashMap, HashSet的实现做了一个详细的讨论。这里主要是针对Map, Set这两种类型的数据结构规约和典型的HashMap,HashSet实现做一个讨论。

Map

    Map是一种典型的名值对类型，它提供一种Key-Value对应保存的数据结构。我们通过Key值来访问对应的Value。和Java集合类里头其他的类不太一样，这个接口并没有继承Collection这接口。而其他的类或者接口不管是List, Set, Stack等都继承了Collection。从这一点来说，它有点像一个异类。

    从前面的这部分讨论，我们可以简单的归类一下Map接口里面定义的常用操作。最常见的两种操作方法是get, put方法。get方法用于根据Key来取得所需要的Value值，而put方法用于根据特定的Key来放置对应的Value。除了这两个方法以外还有判断Key,Value是否存在的containsKey, containsValue方法。

    Map类型的数据结构有一个比较好的地方就是在存取元素的时候都能够有比较高的效率。 因为每次存取元素的时候都是通过计算Key的hash值再通过一定的映射规则来实现，在理想的情况下可以达到一个常量值。

下面这部分是Map里面主要方法的列表：

方法名	方法详细定义	说明
containsKey	boolean containsKey(Object key);	判断名是否存在
containsValue	boolean containsValue(Object value);	判断值是否存在
get	V get(Object key);	读取元素
put	V put(K key, V value);	设置元素
keySet	Set<K> keySet();	所有key值合集
values	Collection<V> values();	所有value的集合
entrySet	Set<Map.Entry<K, V>> entrySet();	键值对集合

    掌握了以上这些主要的方法介绍，对于其他部分也就很好理解。

HashMap

    我们从书本上看到的hash表根据不同的需要可以有不同的实现方式，比如有的直接用线性表，有的用链表数组。在hash值的映射规则上也各不相同。在jdk的实现里，HashMap是采用链表数组形式的结构：

   有了这部分的阐述，我们后面来理解它具体实现步骤就容易了很多。 

内部结构

    我们根据这种链表数组的类型，可以推断它内部肯定是有一个链表的结构。在HashMap内部，有一个transient Entry[] table;这样的结构数组，它保存所有Entry的一个列表。而Entry的定义是一个典型的链表结构，不过由于既要有Key也要有Value，所以包含了Key, Value两个值。他们的定义如下：

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

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
//...
}

    这里省略了其他部分，主要把他们这个链表结构部分突出来。这部分就相当于链表里一个个的Node节点。ok，这样我们至少已经清楚了它里面是怎么组成的了。

数组增长调整

    现在再来看一个地方，我们实际中设计HashMap的时候，这里面数组的长度该多少合适呢？是否需要进行动态调整呢？如果是固定死的话，如果我们需要放置的元素少了，岂不是浪费空间？如果我们要放的元素太多了，这样也会导致更大程度的hash碰撞，会带来性能方面的损失。在HashMap里面保存元素的table是可以动态增长的，它有一个默认的长度16，

static final int DEFAULT_INITIAL_CAPACITY = 16;

static final int MAXIMUM_CAPACITY = 1 << 30;

    在HashMap的构造函数中，可以指定初始数组的长度。通过这个初始长度值，构造一个长度为2的若干次方的数组：

// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
    capacity <<= 1;

    在我们需要调整数组长度的时候，它的过程和前面讨论过的List, Queue有些类似，但是又有不同的地方。相同的地方在于，它每次也是将原来的数组长度翻倍，同时将元素拷贝过去。但是由于HashMap本身的独特性质，它需要重新做一次映射。实现这个过程的方法如下：

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable) {
    Entry[] src = table;
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { //遍历原来的数组table
        Entry<K,V> e = src[j];
        if (e != null) {
            src[j] = null;
            do {  //对该链表元素里面所有链接的<key, value>对做重新的映射
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

    前面这部分的代码看起来比较长，实际上就是将旧的数组的元素挪到新的数组中来。因为新数组的长度不一样了，再映射的时候要对链表里面所有的元素根据新的长度进行重新映射来对应到不同的位置。

    那么，我们可以看出来，元素存放的位置是和数组长度相关的。而这其中具体映射的过程和怎么放置元素的呢？我们在这里就可以找到一个入口点了。就是indexFor方法。

详细映射过程

    我们要把一个<K, V>Entry放到table中间的某个位置，首先是通过计算key的hashCode值，我们都知道。在java里每个对象都有一个hashCode的方法，返回它对应的hash值。HashMap这边通过这个hash值再进行一次hash()方法的计算，得到一个int的结果。再通过indexFor将它映射到数组的某个索引。

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

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

    hash方法就是对传进来的key的hashCode()值再进行一次运算。indexFor方法则是具体映射的方法。因为最后得到的这个值将走为存储Entry的索引。这里采用h & (length - 1)的手法比较有意思。因为我们定义的数组长度为2的若干次方，这意味着如果我们取长度减一的值时，它的二进制数字是最高位以下的所有位为1.经过与运算之后它的结果肯定在0~2**x之间。就算前面hash方法计算出来的结果比数组长度大也没关系，因为这么一与运算，前面长出来的部分都变成0了。它这一步运算的效果相当于h % length;

    有了这部分对数组长度调整和映射关系的理解，我们再来看具体的get, put方法就很容易了。

get

    get方法的定义如下：

public V get(Object key) {
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
    // table[indexFor(hash, table.length)] 就是将indexFor运算得到的值直接映射到数组的索引
         e != null;
         e = e.next) {
         Object k;
         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
        //找到hash值相同的情况下可能出现hash碰撞，所以需要调用equals方法来比较是否相等
            return e.value;
    }
    return null;
}

    它这里就是一个映射，查找的过程。找到映射的点之后再和链表里的元素逐个比较，保证找到目标值。因为是hash表，会存在多个值映射到同一个index里面，所以这里还要和链表里的元素做对比。

put

    put元素就是一个放置元素的过程，首先也是找到对应的索引，然后再把元素放到链表里面去。如果链表里有和元素相同的，则更新对应的value，否则就放到链表头。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        //如果找到相同的值，更新，然后返回。
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    //在前面的循环里面没有找到，则新建一个Entry对象，加入到链表头。
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

    addEntry方法会判断表长度，如果达到一定的阀值则调整数组的长度，将其翻倍：

void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

 

Set

    Set接口里面主要定义了常用的集合操作方法，包括添加元素，判断元素是否在里面和对元素过滤。常用的几个方法如下：

 

方法名	方法详细定义	说明
contains	boolean contains(Object o);	判断元素是否存在
add	boolean add(E e);	添加元素
remove	boolean remove(Object o);	删除元素
retainAll	boolean retainAll(Collection<?> c);	过滤元素

    我们知道，集合里面要求保存的元素是不能重复的，所以它里面所有的元素都是唯一的。它的定义就有点不太一样。

HashSet

    HashSet是基于HashMap实现的，在它内部有如下的定义:

private transient HashMap<E,Object> map;

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

    在它里面放置的元素都应到map里面的key部分，而在map中与key对应的value用一个Object()对象保存。因为内部是大量借用HashMap的实现，它本身不过是调用HashMap的一个代理，这些基本方法的实现就显得很简单：

public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

public boolean contains(Object o) {
        return map.containsKey(o);
    }

 

总结

    在前面的参考资料里已经对HashMap做了一个很深入透彻的解析。这里在前人的基础上加入一点自己个人的理解体会。希望对以后使用类似的结构有一个更好的利用，也能够充分利用里面的设计思想。 

 

参考资料

http://www.ibm.com/developerworks/cn/java/j-lo-hash/index.html