Thinking in Java之HashMap源码分析

欢迎讨论、交流，转载请注明出处，3Q!

前言
在前面的文章中笔者就Map接口和Map接口的实现原理:内部哈希映射技术做了一个简单的

分析，并且对hashCode方法做了一些阐述。可能有些混乱，不过理解这些是弄懂HashMap

的前提，也能帮助我们更好的解析hashMap的源码。

HashMap类设计
HashMap是基于哈希表的Map接口的非同步实现，它提供所有可选的映射操作，并允许使

用null键和null值。此集合不保证映射的顺序，特别不保证其顺序永久不变。

首先我们先看下HashMap类的头部：

[java]
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable 对于它的分析就不多做解释了，AbstractMap类主要是帮助我们自定义自己的Map实现类。

1、底层实现
接下来我们看看HashMap的底层是如何实现的。在这之前我们先对数据结构略作分析。

在java语言中，最基本的结构分为两种：其一为数组，其二为模拟指针(引用)说白了就是

链表。所有的数据类型都可以使用上述的两种来构造。

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

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

思考下：我们能不能结合两者的优点，折中构造一种寻址容易，插入删除也较为容易的

数据结构呢？答案是肯定的了。我们可以构造一种“链表散列”的数据结构，可以理解为链表

的数组，HashMap就是基于其实现的。

从图中可以看出HashMap的底层就是一个数组结构，数组中的每一项又是一个链表。那么

究竟是不是这样呢？我们看源码吧。

[java]
/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
transient Entry<K,V>[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

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

/**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
transient Entry<K,V>[] table;
static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
    ...........
}
              可以看出的是HashMap里面实现了一个静态内部类Entry(记录)，其重要的属性有key、value、next

而HashMap有一个属性是Entrr的数组table。Entry就是table数组中的元素，Map.Entry就会一个键值对

这个键值对持有指向下一个键值对的引用，如此就构成了链表了。

2、构造方法

[java]
/**根据指定容量和负载因子构造HashMap*/
public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;

补充：软件开发 , Java ,