HashMap就是一个散列表，它是通过“拉链法”解决哈希冲突的。

1. 哈希表-拉链法

2. HashMap的存取实现

既然是线性数组，为什么能随机存取？这里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;
//int index = hash & (tab.length - 1);
return Entry[index];

1）put
疑问：如果两个key通过hash%Entry[].length得到的index相同，会不会有覆盖的危险？
　　这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？
HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。

也就是说数组中存储的是最后插入的元素。插入时，先找到数组索引，取出数组在索引代表的entry值(链表头)，遍历链表的每一个entry节点，当entry的hashcode值与put进来的key的hashcode值相等并且(entry的key与put进来的key是同一对象或者entry.key.equals(put进来的key))，就会执行替换操作，并且返回之前oldValue。到这里为止，HashMap的大致实现，我们应该已经清楚了。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value); //null总是放在数组的第一个链表中
    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;
        //如果key在链表中已存在，则替换为新value
        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;
}

 

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //参数e, 是Entry.next
    //如果size超过threshold，则扩充table大小。再散列
    if (size++ >= threshold)
            resize(2 * table.length);
}

//确定数组index：hashcode % table.length取模
/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

当然HashMap里面也包含一些优化方面的实现，这里也说一下。比如：Entry[]的长度一定后，随着map里面数据的越来越长，这样同一个index的链就会很长，会不会影响性能？HashMap里面设置一个因子，随着map的size越来越大，Entry[]会以一定的规则加长长度。
2）get

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

3）null key的存取
null key总是存放在Entry[]数组的第一个元素。

 private V putForNullKey(V value) {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
    return null;
}

private V getForNullKey() {
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}

4）确定数组index：hashcode % table.length取模
HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，即计算数组下标；算法如下：

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

按位取并，作用上相当于取模mod或者取余%。
这意味着数组下标相同，并不表示hashCode相同。

5）table初始大小

public HashMap(int initialCapacity, float loadFactor) {
    .....
    // Find a power of 2 >= initialCapacity
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    threshold = (int)(capacity * loadFactor);
    table = new Entry[capacity];
    init();
}

注意table初始大小并不是构造函数中的initialCapacity！！
而是 >= initialCapacity的2的n次幂！！！！

3. 解决hash冲突的办法

HashMap实现原理分析

4.再散列rehash过程

HashMap实现原理分析

参考：

1. HashMap实现原理分析

推荐阅读

• HashMap，ArrayMap，SparseArray源码分析及性能对比