本文共 4889 字，大约阅读时间需要 16 分钟。

HashMap

JDK7和JDK8中大致变化

1.7中采用数组+链表，1.8采用的是数组+链表/红黑树，1.8中链表长度超过8，元素长度超过64才用红黑树储存

1.7扩容时需要重新计算哈希值和索引位置，1.8并不重新计算哈希值，巧妙地采用和扩容后容量进行&操作来计算新的索引位置。

1.7是采用表头插入法插入链表，1.8采用的是尾部插入法。

在1.7中采用表头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题；在1.8中采用尾部插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

哈希表的主干就是数组

比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。存储位置 = hash(关键字)

哈希冲突 哈希碰撞

当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞

HashMap的整体结构图

简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好

其他几个重要字段

//实际存储的key-value键值对的个数transient int size;//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到int threshold;//负载因子，代表了table的填充度有多少，默认是0.75final float loadFactor;//用于快速失败，由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），需要抛出异常ConcurrentModificationExceptiontransient int modCount;//initialCapacity默认为  16  ，loadFactory默认为  0.75

对代码的简单介绍

在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外）

在执行put操作的时候才真正构建table数组

put操作的实现:

public V put(K key, V value) {
           //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，此时threshold为initialCapacity 默认是1<<4(24=16)        if (table == EMPTY_TABLE) {
               inflateTable(threshold);        }       //如果key为null，存储位置为table[0]或table[0]的冲突链上        if (key == null)            return putForNullKey(value);        int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀        int i = indexFor(hash, table.length);//获取在table中的实际位置        for (Entry
   
     e = table[i]; e != null; e = e.next) {
           //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value            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++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败        addEntry(hash, key, value, i);//新增一个entry        return null;    }
   

inflateTable方法

private void inflateTable(int toSize) {
           int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1        table = new Entry[capacity];        initHashSeedAsNeeded(capacity);    }

inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.

private static int roundUpToPowerOf2(int number) {
           // assert number >= 0 : "number must be non-negative";        return number >= MAXIMUM_CAPACITY                ? MAXIMUM_CAPACITY                : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;    }

roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值.

获取最终存储位置流程图:

数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置

重写equals方法需同时重写hashCode方法

关于HashMap的源码分析就介绍到这儿了，最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题

/** * Created by chengxiao on 2016/11/15. */public class MyTest {    private static class Person{        int idCard;        String name;        public Person(int idCard, String name) {            this.idCard = idCard;            this.name = name;        }        @Override        public boolean equals(Object o) {            if (this == o) {                return true;            }            if (o == null || getClass() != o.getClass()){                return false;            }            Person person = (Person) o;            //两个对象是否等值，通过idCard来确定            return this.idCard == person.idCard;        }    }    public static void main(String []args){        HashMap
   
     map = new HashMap
    
     ();        Person person = new Person(1234,"乔峰");        //put到hashmap中去        map.put(person,"天龙八部");        //get取出，从逻辑上讲应该能输出“天龙八部”        System.out.println("结果:"+map.get(new Person(1234,"萧峰")));    }}
    
   

实际输出结果：

结果：null

如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–>hash–>indexFor–>最终索引位置

而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）

所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。

总结

本文描述了HashMap的实现原理，并结合源码做了进一步的分析，也涉及到一些源码细节设计缘由，最后简单介绍了为什么重写equals的时候需要重写hashCode方法。希望本篇文章能帮助到大家，同时也欢迎讨论指正，谢谢支持！

Gtihub 地址: github.com/liangtengyu

公众号 java宝典

转载地址：http://kgbvi.baihongyu.com/