HashMap的实现原理

哈希表的主干就是数组。比如我们要新增或查找某个元素，我们通过把当前元素的关键字通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。

存储位置 = f(关键字)

其中，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：

查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。

从上图我们可以发现哈希表是由数组+链表组成的，假设一个长度为16的数组（默认大小）中，每个元素存储的是一个链表的头结点。一般情况是通过类似取模的方法得到（实际使用indexFor(int h, int length)方法和取模的结果一致，但效率更高）。这里我们先假设使用取模的方法则上述哈希表中：
12%16=12,28%16=12,108%16=12,140%16=12。
所以12、28、108以及140都存储在数组下标为12的位置。

为了实现上述数组+链表的功能，HashMap里面实现了一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean。我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里。

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
    int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算

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

HashMap的存取实现：

// 存储时:
int hash = key.hashCode(); // 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int index = hash % Entry[].length;
Entry[index] = value;

// 取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

如果两个key通过hash%Entry[].length得到的index相同，这时HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。
打个比方，：
第一个键值对A，通过计算其key的hash得到的index=0，Entry[0] = A。
第二个键值对B，index也等于0，B.next = A,Entry[0] = B。
第三个键值对C，index也等于0，C.next = B,Entry[0] = C。
这样index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。也就是说数组中存储的是最后插入的元素。
存储：

public V put(K key, V value) {  
    // HashMap允许存放null键和null值。  
    // 当key为null时，调用putForNullKey方法，将value放置在数组第一个位置。  
    if (key == null)  
        return putForNullKey(value);  
    // 根据key的keyCode重新计算hash值。  
    int hash = hash(key.hashCode());  
    // 搜索指定hash值在对应table中的索引。  
    int i = indexFor(hash, table.length);  
    // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素。  
    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;  
        }  
    }  
    // 如果i索引处的Entry为null，表明此处还没有Entry。  
    modCount++;  
    // 将key、value添加到i索引处。  
    addEntry(hash, key, value, i);  
    return null;  
}  

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

/**
 * 返回数组下标
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

hash(int h)方法根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突。
读取：

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)];  
        e != null;  
        e = e.next) {   
        if (e.hash == hash && (e.key == key || key.equals(e.key)))  
            return e.value;  
    }  
    return null;  
}  

HashMap的resize（rehash）:
当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的。所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中。
当HashMap中的元素个数超过数组大小loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过 160.75=12 的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。
这是一个非常消耗性能的操作，原数组中的数据必须重新计算其在新数组中的位置。所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

HashMap(int initialCapacity, float loadFactor)

---

要点：哈希表是由数组+链表组成的。HashMap里实现了一个静态内部类Entry，其重要的属性有 key , value, next。Map里面的内容都保存在Entry[]里。

---

参考：
http://zhangshixi.iteye.com/blog/672697
http://blog.csdn.net/vking_wang/article/details/14166593
http://www.cnblogs.com/chengxiao/p/6059914.html