Java HashMap 代码浅析

   hashMap的实现机制，面试时经常问到 

   一 HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对

 

transient Entry<K,V>[] table;

 Entry 是个内部类，作为一个单链表。

 

 

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

 

 

   二 当需要存储一个 Entry 对象时，会根据hash算法来决定其在数组中的存储位置，再根据equals方法决定其在该数组位置上的链表中的存储位置；

 

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);//说明HashMap允许key为null值，这是与hashTable的不同点之一，另外不同点是，HashMap不能保证同步。
        int hash = hash(key);//获取hash值  
        int i = indexFor(hash, table.length);//通过hash值找到数组中索引  
        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))) {//链表上遍历找到key值相同的，找到了就替换  
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;//快速失败  机制用到的变量。
        addEntry(hash, key, value, i);//找不到key值相同的entry在链表头部追加该元素
        return null;
    }

 

 

我想重点理解下int i = indexFor(hash, table.length);//通过hash值找到数组中索引 这步，我的想法是直接通过hash%length 得到i，实际是以下这样做的：

 

  

  /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 & 的效率比%的效率高，而且 length是2的n次方的情况下，达到了与取余的同样效果。

 

  可以证明在 length = 2的n次方时，

  h & (length  - 1） = h % length ;恒成立

那么hashMap如何保证table.length = 2的n次方的呢，且看以下代码

 

    static final int DEFAULT_INITIAL_CAPACITY = 16;
    public HashMap(int initialCapacity, float loadFactor) {
    ....
          // Find a power of 2 >= initialCapacity
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;
     ...
    }

 

table = new Entry[capacity];

 三当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry

 

 

public V get(Object key) {
        if (key == null)  // 处理null 的key
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

 理解了如何put，get就很好理解了。

 

参考文档 通过分析 JDK 源代码研究 Hash 存储机制

 

                 Java HashMap实现详解