Java 7源码分析第10篇 - Map集合的实现 - JAVA

何存储的问题了。HashMap顾名思义就是使用哈希表来存储的，哈希表为解决冲突，采用了开放地址法和链地址法来解决问题。Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被hash后，得到数组下标，把数据放在对应下标元素的链表上。当程序试图将多个 key-value 放入 HashMap 中时，以如下代码片段为例：

HashMap
  
    map = new HashMap
   
    (); map.put("语文" , 80.0); map.put("数学" , 89.0); map.put("英语" , 78.2);

HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。
当程序执行 map.put("语文" , 80.0); 时，系统将调用"语文"的 hashCode() 方法得到其 hashCode 值――每个 Java 对象都有 hashCode() 方法，都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后，系统会根据该 hashCode 值来决定该元素的存储位置。

我们可以看 HashMap 类的 put(K key , V value) 方法的源代码：

// 当向HashMap中添加mapping时，由key的hashCode值决定Entry对象的存储位置，当两个 key的hashCode相同时，
// 通过equals()方法比较，返回false产生Entry链，true时采用覆盖行为
    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
  
    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;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论：我们完全可以把 Map 集合中的 value 当成 key 的附属，当系统决定了 key 的存储位置之后，value 随之保存在那里即可。
上面方法提供了一个根据 hashCode() 返回值来计算 Hash 码的方法：并且会调用 indexFor() 方法来计算该对象应该保存在 table 数组的哪个索引，源代码如下：

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);
    }
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

length是table.length，所以数组的长度总是 2 的 n 次方，通过h&(length-1)计算后，保证计算得到的索引值位于 table 数组的索引之内，计算的函数并不总是这样的，好的计算函数应该还会让索引值尽量平均分布到数组中。

当调用put()方法向 HashMap 中添加 key-value 对，由其 key 的 hashCode() 返回值决定该 key-value 对（就是Entry 对象）的存储位置。当两个 Entry 对象的 key 的 hashCode() 返回值相同时，将由 key 通过 eqauls() 比较值决定是采用覆盖行为（返回 true），还是产生 Entry 链（返回 false），而且新添加的 Entry 位于 Entry 链的头部，这是通过调用addEntry()方法来完成的，源码如下：

void addEntry(int hash, K key, V value, int bucketIndex){ 
    Entry
  
    e = table[bucketIndex]; // 获取指定 bucketIndex 索引处的 Entry 
    table[bucketIndex] = new Entry
   
    (hash, key, value, e); // 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry // 如果 Map 中的 key-value 对的数量超过了极限 if (size++ >= threshold) resize(2 * table.length); // 把 table 对象的长度扩充到 2 倍 }

程序总是将新添加的 Entry 对象放入 table数组的 bucketIndex 索引处――如果 bucketIndex 索引处已经有了一个 Entry 对象，那新添加的 Entry 对象指向原有的 Entry 对象（产生一个 Entry 链），如果 bucketIndex 索引处没有 Entry 对象， e 变量是 null，也就是新放入的 Entry 对象指向 null，也就是没有产生 Entry 链。

接下来看一下HashMap是如何读取的。 get()方法的源代码如下：

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        // 搜索该Entry链的下一个Entry，有多个Entry链时必须顺序遍历，降低了索引的速度
        //  如果Entry链过长，说明发生“Hash”冲突比较频繁，需要采用新的算法或增大空间
        for (Entry
  
    e = table[indexFor(hash, table.length)]; e != null; e = e.next) { 	 
               Object k;
               if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
         }
       　 return null;
    }

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry 时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后循环遍历查找 hash值相同,key值相同的value。

下面来看一下HashMap是如何实现如下的三个方法的，源代码如下：

 public Set
  
    keySet() {
        Set
   
     ks = keySet; return (ks != null   ks : (keySet = new KeySet())); } public Collection
    
      values() { Collect

Java 7源码分析第10篇 - Map集合的实现(二)