Java HashMap学习笔记

1.HashMap数据结构

在java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

从上图中可以看出，HashMap底层就是一个数组结构，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。

数组的特点是：寻址容易，插入和删除困难。

链表的特点是：寻址困难，插入和删除容易。

数组初始大小为16

当插入一个key,value时

数组下标为 indexFor(hash(key.hashCode()),table.length)

以下代码摘自HashMap.java

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

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

/**
     * Returns index for hash code h.
     */

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

value是一个Entry对象：

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

其中next即链式存储方式，目的为解决hash冲突问题。

下面举例说明：

Map<String,String> m = new HashMap<String,String>();

m.put( "123" , "abc");

m.put( "i9" , "def");

因为"123"和"i9"的hashCode不同，分别为48690和3312，故不会覆盖彼此。但其通过indexFor方法获得数组下标皆为6(默认容量大小时)，此时当插入i9时，就会利用到next。

截图进一步说明：

当执行m.put("123", "abc");后

当执行m.put("i9","def");后

解决hash冲突的办法

1）开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）

2）再哈希法

3）链地址法

4）建立一公共溢出区

java 中hashmap的解决办法就是采用的链地址法

2.HashMap最大存储容量

/**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */

    static final int MAXIMUM_CAPACITY = 1 << 30;
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
...
}

由上述代码可知，hashMap的最大容量为1<<30，即为1073741824，因为hashMap是基于数组的，而数组的下标索引是int类型的，所以数组大小也是不可能大于Integer.MAX_VALUE即2³¹-1 （2147483647）的，由于受分配的内存大小限制，一般达不到这么大就会报java.lang.OutOfMemoryError: Java heap space错误。

参考：

http://linxh83.iteye.com/blog/1403404 Java HashMap深度剖析

http://792881908-qq-com.iteye.com/blog/1447260 HashMap的内部实现机制之篇一

http://beyond99.blog.51cto.com/1469451/429789 Java HashMap实现详解

http://zha-zi.iteye.com/blog/1124484 hash算法 (hashmap 实现原理)

http://blog.csdn.net/kiritor/article/details/8885961 Thinking in Java之HashMap源码分析

http://www.cnblogs.com/I-will-be-different/p/4487868.html 这篇文章解释的也不错 added by 20150510