1.什么是哈希表

• 数组：采用一段连续的存储单元来存储数据。通过指定下标查找，速度很快；通过给定值查找，需要遍历数组。对于有序数组，可以优化查找方法，比如二分法等；对于插入删除操作，就会设计增容，数组元素平移等操作，效率偏低。
• 链表：对于新增、删除的操作在找到元素位置后只需要处理节点间的引用即可，效率比较高；但是查找需要遍历链表。

• 哈希表：哈希表在添加，删除，查找上的性能十分高，在不考虑哈希冲突的情况下，仅需要通过hash值做一次定位就可以完成。数据结构的物理存储结构只有两种：顺序存储结构跟链式存储结构。哈希表通过hash值定位存储地址，这种特性跟数组是一样的，哈希表的主干就是数组。

  
  1600925026221.jpg
• 哈希冲突：一般情况不同元素计算出的hash值是不同的，所以存储地址也是不同的，每个地址对应着一个元素，但是完事没有完美，如果有元素计算出的hash值相同，那么他们的存储地址也会相同，这就产生了哈希冲突，这也是不可避免的，因为哈希表主干就是数组，一个连续的长度固定的存储空间，那么就不能完全保证存储地址绝对不冲突，那么为了解决哈希冲突就出现了数组+链表的方式，HashMap就是采用这个方式。

2.HashMap的实现原理

HashMap的主干是一个Entry数组，每一个Entry里面包含了key-value键值对，hash值，还有链表的下一个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的结构如下：

1600925782209.jpg

HashMap由数组+链表组成，数组是主体，链表是为了解决哈希冲突。如果HashMap中没有链表，那么查找添加的速度就会非常快；如果存在链表就需要遍历整个链表，如果key存在就会覆盖，如果不存在就会复杂一点，需要判断链表是否是红黑树，如果是红黑树就直接插入，如果不是就会遍历链表准备插入，这时候还要再判断链表长度是不是大于8，如果是的话，链表会转为红黑树，如果不是就会插入链表，当然最后还需要看是否需要扩容。
（HashMap的默认初始长度是16，负载因子是0.75，当超过阈值就会出发扩容，newSize = oldSize*2，size一定是2的n次幂）

3.HashMap的数组长度一定是2的次幂

为什么要设计HashMap的数组长度一定是2的次幂呢，那这个我们就需要看一下HashMap是如何去计算出元素存储位置的了

static int indexFor(int h, int length) {
        return h & (length-1);
    }

h是通过元素的hashCode通过计算得出了的hash值，length是Size容量
举个例子，当前容量是16，h计算结果是11，转二进制计算

01011 & 01111 = 01011 = 11

这个下标就是11了，这就是当前元素存储位置。
然后假设这个HashMap发生了一次扩容，那么当前容量就是32，h还是11，我们再次计算元素存储位置

01011 & 11111 = 01011 = 11

这里是不是发现扩容后没有影响到原来的元素的下标，但是如果不是Size不是2的次幂会怎么样呢，我们也举个例子，Size=30，h =11

01011 & 11101 = 01001 = 9

扩容后存储位置变了，第一个原因就有了，可以减少扩容机制发生时老数组的数据位置变换，而且length-1低位都是1的话也可以让索引更加的均匀，有利于散列良好。

然后我们再来看，举例：

010101 & 111111 = 010101
010111 & 111111 = 010111

010101 $ 111101 = 010101
010111 $ 111101 = 010101

可以看到低位全是1可以保证不同数据计算结果不通，但是第二种却不行，这样一来哈希冲突的几率就会增加，链表数量也会变多，还会让散列不均匀浪费数组位置，查询效率还会降低。

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

到了这里HashMap基本分析结束了，那么也就可以知道为何说重写equals方法需同时重写hashCode方法了，我们可以举个列子：

public class A{
  int id;
  String name;
  public A(int id, String name){
    this.id = id;
    this.name = name;
  }

  @Override
  public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()){
                return false;
            }
            A a = (A) o;
            //如果id相等我们就认为两个对象相等
            return this.idCard == person.idCard;
  }
}

这种情况下会怎样呢，比如A1对象id是1，name是a1；A2对象id是1，name是a2，这两个对象id是相等的，在业务场景上我们就认为两个对象就是相等的，那么我们将他们保存如HashMap，现存入A1再存入A2，那么我们想要的是什么，例如一个人的身份证是1，开始他叫a1，后来改名了叫a2了，我们在存入的时候肯定是希望覆盖掉原来的信息，但是因为没有重写hashCode方法，他们的hashCode值就不一样，得到的hash值就不一样，最后地址下标也就不一样，那么对于HashMap来讲他们就是两个不同的对象，与业务不符合。这就是为什么重写equals方法需同时重写hashCode方法的原因了。