HashMap

含义

• hash就是把任意的内容（视频、图片、文字等）转换成一个特殊的值，不管原内容多大，转换后的结果都是同一个格式（如果是数字的话，那么它的格式就是长度都一样，不管是图片、视频等都会转换成同一个长度的数字）的值，这个值可以是字符串，可以是数字，具体取决于调用的算法

• 举例：

  • 想要知道同学们的英语水平如何，英语水平这是一个抽象的概念，那么想要了解具体怎样，用考试的方法最方便，通过考试可以得到每个人的分数，分数就是这个人的英语水平的具体体现。那么分数是固定的0~100之间的一个值，也就是含义中所说的那个格式。

  • 英语水平就是我们传进去的变量，而考试的打分规则就是hash算法，这个规则可以不同，常见的有MD5，sha256等，经过打分规则得到的分数就是变量的哈希值

特点

• 任意长度的输入，得到固定长度的输出

  • 每个人的英语水平经过考试都会得到一个固定的0~100的分数

• 不可逆，可以把原文计算成密文（哈希值），但是不能倒推回去

  • 比如“我爱你”计算后为“aaa",但是你无法通过”aaa"推导出“我爱你”

• 算法不固定，只要满足hash的思想就是hash算法

  • 常见的摘要算法有md5、sha256

作用

• 用来快速检索

  • 比如在一万篇文章中找出和我手上的文章一模一样的一篇，一个字一个字读太慢了，将这片文章经过hash算法转换成哈希值，拿哈希值进行比对就会快很多

• 防篡改

  • 密码学的主要途径，只能加密不能解密，由于哈希值不可逆的特点，得到文件经过加密后的哈希值是不能推导出原文件的，所以发送数据时将原文和密文一起发送给对方，对方收到后再次对原文进行加密得到密文，如果密文与收到的一样就代表没有被改过

• 密码保存

  • 保存的密码经过加密保存到数据库，工作人员看不到

• 快速查找

  • 哈希表是比数组查询速度更快的结构，在使用数组进行查找时，需要按顺序一个一个从头开始找，这种查找方式叫做线性查找，但是当数据量非常多的时候，线性查找是非常消耗时间的，所以用数组来存储元素并不合适
  • 哈希表
    • 存储元素时，传进的元素经过哈希算法计算得到哈希值，将得到哈希值除以数组的长度（叫mod运算）后得到索引，将元素存放进该索引的位置，如果该索引的位置已经有了元素（又叫哈希冲突），那么就通过链表的形式，在原有元素的后面进行存储
    • 查询元素时，再次将要查询的元素经过同样的哈希算法得到哈希值，对哈希值进行Mod运算得到索引，直接找到索引的位置，拿到该元素。这样就不用像数组一样按顺序一个一个去比对的寻找，拿到索引直接找到该元素。若该位置存放了链表，再通过equals方法进行比对
    • 哈希表与数组两者查询速度的差值，与数据量成正比。他俩的比值与数据量成反比

hashcode

含义：

• JAVA中的hashCode()方法就是根据一定的规则将与对象相关的信息（如：对象的存储地址）映射成一个数值，这个数值被称作哈希值

作用：

• 假如不使用哈希表在集合中插入不重复的元素

  • 可行的方法为：把插入的元素用equals方法对集合中的每一个元素进行一一比对，如果相同就不插入，如果不同，再将新元素添加进去
  • 显然该方法的效率非常低，hashcode方法的作用就体现出来了

• 当要添加新对象时，先调用这个对象的hashCode方法，得到对应的哈希值，实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的哈希值，如果table中没有该哈希值，他就直接存进去，不再进行任何比较。如果存在该哈希值，就调用它的equals方法与新元素进行比较，相同就不存。

• 两个方法的结合运用，才会使得哈希表查询和插入的效率很高

  • 当要插入元素时，先使用hashCode方法计算哈希值，如果table中没有则直接保存，如果有一样的哈希值，在哈希表中的数组结构部分找到该位置
  • 如果该位置上保存了一个链表，就代表该链表上的所有对象的哈希值都与要插入元素的哈希值一致，这个时候再使用equals方法一个一个比对
  • 如果equals方法比对结果还是相同的话，就代表是一模一样的元素，不插入，如果比对结果不相同，再使用头插法或者尾插法插入

hashCode方法与equals方法

• 不能根据哈希值判断两个对象是否相同，因为不同的对象可能生成相同的哈希值

• 可以根据哈希值判断两个对象是否不同，哈希值不同，对象必定不同

• 判断两个对象是否真正完全相等，还是要通过equals方法

• 以上三点的小结：

  • 两个对象调用equals方法得到的结果为true，则两个对象的哈希值必定相同
  • 如果equals方法结果为false，则两个对象的哈希值不一定不同
  • 如果两个对象的哈希值不同，则equals方法结果必定为false
  • 如果两个对象的哈希值相等，则equals方法得到的结果未知

举例：

• 在设计一个类的时候，重写了equals方法，那么就必须重写hashCode方法

• class People{
      private String name;
      private int age;
       
      public People(String name,int age) {
          this.name = name;
          this.age = age;
      }  
       
      public void setAge(int age){
          this.age = age;
      }
       
      @Override
      public int hashCode() {
          return name.hashCode()*37+age;
      }                        //重写hashCode方法，该对象的哈希值为名字的哈希值乘以37再加上年龄
       
      @Override
      public boolean equals(Object obj) {
          return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;
      }
  }
   
   
   
   =====================================================================================================
   
  public class Main {
   
      public static void main(String[] args) {
           
          People p1 = new People("Jack", 12);
          System.out.println(p1.hashCode());
               
          HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
          hashMap.put(p1, 1);
           
          System.out.println(hashMap.get(new People("Jack", 12)));
          //重新添加一个对象，该对象经过hashCode方法得到的哈希值与p1相同，所以通过get方法应该打印出1
      }
  }
  

  • 假设只重写了equals方法，将重写hashCode方法注释，也就是说如果两个对象的姓名和年龄相同，则认为是同一个对象
    • 而实际打印通过get方法只能得到null，是不会得到1的，代表两个对象并不相同
    • 原因在于没有重写hashCode方法，因为生成的两个对象实际存储地址并不相同，在没有重写hashCode方法的情况下，根据两地址生成的哈希值也是不同的

补充：

• 对同一个对象调用hashCode方法都应该产生同样的值

  • 在用put方法给HashMap添加对象时，根据hashCode给对象产生一个哈希值添加进去，而用get方法取出的时候再次调用hashCode给同样的对象产生哈希值，这个时候发现同样的对象产生的哈希值不同，那么就无法获取该键所对应的值了

  • 发生这种情况的原因是：在hashCode方法中，使用了对象中易变的数据，因为此数据发生了变化，hashCode就会生成不同的哈希值

  • 举例代码中，People类不变，Main改变：

    public class Main {
     
        public static void main(String[] args) {
             
            People p1 = new People("Jack", 12);
            System.out.println(p1.hashCode());
             
            HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
            hashMap.put(p1, 1);
             
            p1.setAge(13);    //在这里对年龄做了修改，而hashCode方法里用到了年龄这个变量，那么p1的哈希值也会随之改变
             
            System.out.println(hashMap.get(p1));
        }
    }
    

    此时输出p1的值仍然为null

• 自定义类为Key：

  • 类添加fianl修饰符，保证类不被继承
    • 如果类可以被继承会破坏类的不可变机制，只要继承类覆盖父类的方法并且继承类可以改变成员变量值，那么一旦子类以父类的形式出现时（多态），不能保证当前类是否可变
  • 保证所有成员变量必须私有，并且加上final修饰
    • 通过这种方式保证成员变量不可改变
    • 这种方法还不够，因为如果是对象成员变量有可能在外部改变其值（如：People类中可以使用set方法对年龄做修改）
  • 不提供改变成员变量的方法，包括setter避免通过其它接口改变成员变量的值，破坏不可变特性

MOD运算（取模运算）

作用：

• 通过Hash值计算索引，让每一个元素可以均匀的分布在数组每一个格子内
  • 为了让每一个元素均匀的分布在数组不同的格子里，总不能明明有16个格子，但是每个元素全都挤在一个格子里，然后通过链表结构去一个一个往后面添加，这样的话哈希表毫无作用，直接完全变成了一个链表结构，查询效率降了两个档次

如何”均匀“：

• 想要有几种情况，那么就对数字几取余

  • 对3取余，可能的结果为0、1、2，有三种结果，对4取余，可能的结果为0、1、2、3，有四种结果......诸如此类

  • int i=0;
    while(true){
    	if(i%3==0){
    	
    	}
    	if(i%3==1){
    	
    	}
    	if(i%3==2){
    	
    	}
    	i++;
    }
    

• 对于哈希来说，由于不同元素经过哈希运算得到的哈希值不同，那么用这个哈希值对数组的长度取余后，（假如数组长度为16，得到的哈希值对16取余后，结果可能为0、1、2、3......15，取余的结果就是这个数组中每一个格子的索引）就会得到该元素对应的索引，然后再将其添加进去，这样就可以做到数组每一个索引都可以平均的分到元素

  • 注：

    1.由于根据不同的哈希算法，得到具体的哈希值是不同的，所以哈希值有可能是负数，那么负数对数组长度进行取余（mod运算）的话，得到的索引也是负数，这是不行的

    2.对于计算机来说，二进制的运算效率是最高的，用%进行取余速度很慢

  • 基于以上两点，在进行mod运算时，需要将哈希值和数组长度两个十进制数字转变为二进制，并进行按位与（&）的运算

    • 假设数组长度为17，转变为二进制为10001。传进的三个元素的哈希值分别为0111，0101，0001

      进行按位与运算：

      10001  //数组长度
       0111  //hash1
       0001  //得到索引为1
       
       
      10001  //数组长度
       0101  //hash2
       0001  //得到索引为1
       
      10001  //数组长度
       0001  //hash3
       0001  //得到索引为1
      

      传进来的元素全都被分配到了索引1的位置

    • 假设数组长度为18，转变为二进制为10010。再次传进以上三个元素：0111，0101，0001

      10010  //数组长度
       0111  //hash1
       0010  //得到索引为2
       
      10010  //数组长度
       0101  //hash2
       0000  //？？？？
       
      10010  //数组长度
       0001  //hash3
       0000  //？？？？
      

      可能会得不到索引

    • 每一位与0进行&操作，得到的都是0，这就会发生上面两例的情况，所以为了避免这种情况，要保证数组长度的二进制里，1越多越好

    • 2的幂次方减一转变为二进制，是该字节数量中二进制1的个数最多的

结论：

• mod运算得到索引的公式为：hash&（数组长度-1）= 索引

高位的计算：

• 由于得到的哈希值转变为二进制的时候，可能转变的位数比数组长度位数多，那么哈希值的高位就不会被计算到，而当两个哈希值的高位不同，低位相同时，由于只计算低位部分，又会被分配到同一个索引，这样就又不均匀了

  • 如：

    10010101  //hash1
    00001111  //数组长度为16-1=15
    00000101  //得到索引为5
    
    11110101  //hash2
    00001111  //数组长度为16-1=15
    00000101  //得到索引为5
    

  • 通过对哈希值的右移让高位也参与运算，避免高位相同，低位不同被分到同一个索引

  • JDK8源码计算哈希值部分：

    static final int hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    //通过key的hashCode的高16位与低16位做异或运算，目的是为了更离散哈希值
    

    • 从源码中看到，计算哈希值并不仅仅是使用hashCode()方法，还会经过扰动函数的扰动(h = key . hashCode())^(h > > >16),

    • 这里可以看到，当key为null时，得到的索引为0，即默认放在数组的索引为0的位置，也就是说，如果遍历这个hashMap，key为null会出现在前面

    • 如果第一次加入key为null的元素，直接保存在索引为0的位置

哈希冲突

• 由于哈希是不同长度的输入对应固定长度的输出，那么输入的内容可以是无限的，而哈希值是有限的，所以肯定会有某些数据计算出的哈希值是一样的，这个就叫做哈希碰撞或者哈希冲突

• 当发现两个数据的哈希值一样时，那么对应的经过mod运算的索引也肯定是一样的，一个索引只保存一个元素，索引一致的情况下就会采用链表的插入方法

  • 链表的插入方法分为头插法和尾插法：

    • 头插法：新数据插入后，让该位置原来的数据指向新的数据，类似于栈的存储方式

    • jdk7采用头插法，因为开发者认为后加入的元素被用到的可能性更大，所以头插法可以快速查询。

      但是该方法也带来安全隐患，在多线程的情况下可能出现死循环

    • 尾插法：新数据插入后，新数据指向原来位置的数据，按顺序一个一个排列在后面

    • 为解决死循环问题，jdk8采用了尾插法

• 为解决哈希冲突问题，第一种方法：会使用负载因子进行扩容（具体见基本参数中的负载因子）。第二种方法：在计算哈希值时加入了扰动函数也是为了解决哈希冲突，扰动函数综合了哈希值的高位和低位特征，并存放在低位，因此在按位与操作时，相当于高低位一起参与了运算

哈希表的扩容：

• 扩容时，会new一个新的Node数组作为哈希桶（就是存放哈希值的数组）。然后将原哈希表中的所有数据全都移动到哈希桶中，相当于对原哈希表中所有的数据重新做了一个put操作。所以在哈希表每一次的扩容时，如果原哈希表已经非常大了，那么再进行一次扩容，性能消耗十分明显

  • 注：如果我们提前知道要存放非常大的数据，为了不必让哈希表一次一次的扩容影响效率及性能，那么可以在初始化时将初始容量改为我们的理想容量，这样就不需要从默认16的容量开始一次一次的扩容，从而达到代码的优化

• 元素在原链表上存放的下标（low位），在扩容后得到新的下标（high位）

  • 结论：high位 = low位 + 原数组长度（原哈希桶容量）

  • 分析：

    • 得知 1.计算下标是通过mod运算

      ​ 2.数组的每一次扩容都是按照2的幂次方进行扩容，也就说扩大一倍

    • 基于以上两点：

      0 1111  //原数组长度为16
        0101  //哈希值
        0101  //得到下标为5
       
      0001 1111  //扩容后数组长度为32
           0101  //哈希值不变
      0001 0101  //得到下标为 16+5       原下标（low位）加上原数组长度
      
      

红黑树

自平衡的二叉树:

• 任意结点的左右两个子树高度差都小于等于1，这样的好处是遍历起来更均匀，快速

• 

红黑树：

• 二叉树的自平衡是可以自己动态的改变（变色和旋转），不用自己手动平衡

• 

• JDK8在JDK7的基础上增加了红黑树，HashMap的底层数据结构为数组+链表+红黑树

  • 不管扩容的机制有多好，依然会出现大量的链表导致查询效率低下
  • 所以jdk8在插入的时候，依然按照链表插入，不同于jdk7，这里使用尾插法。
  • 当发现链表的节点（也就是链表的元素）达到8，同时满足数组长度达到64，如果数组长度没达到64会先扩容，两个条件都满足时，会将此链表转成红黑树。
  • 如果发现扩容后红黑树的结点减少到了6，那么又会将他转成链表
  • 尽管红黑树的动态自平衡也比较耗时间，但是当链表结点个数为8个以上时，相较于通过链表查询所耗的时间，红黑树的自平衡时间更少，更划算

• 不用红黑树，用二叉树也可以，但是在一些极端情况下，如：添加的元素一个比一个小（大），那么二叉树就会就会退化成线性结构，全都排在根结点的左边（右边）

源码解析：

基本参数

• 默认的初始容量：16

  • static final int DEFAULT_INITIAL_CAPACITY = 1 < < 4;
  • 默认的容量指开辟的哈希表中数组的空间大小为16，索引为0~15
    • 默认容量16是一个经验值，这个数字不大不小，刚好，初始太小了要频繁扩容，太大了又浪费

• 最大容量：

  • static final int MAXIMUM_CAPACITY = 1 < < 30;

• 负载因子（扩容因子）：

  • static final float DEFAULT_LOAD_FACTOR = 0.75f;
  • 作用：
    • 在存储的元素数量达到扩容阈值（数组长度 乘以 0.75 ），并且新加入的元素与原本的元素发生冲突时，就会扩容，每次扩容后数组的长度为原本长度的2倍（因为要使用mod运算，按位与时必须为2的幂次方减一，所以数组长度就为2的幂次方，每次进行扩容就是原长度*2）
  • 默认负载因子为0.75是经过时间空间成本之间的权衡后找到的最折中的数字，较高的值会减少空间开销，但会增加查找成本。这是经过开发者测试得到的，元素个数达到数组长度*0.75这个值后出现哈希碰撞的概率比较大
  • 使用扩容因子扩容的目的：
    • 并不是因为容量不够而扩容，而是为了解决哈希冲突。放入的元素越多，得到的哈希值越有可能一致，哈希值一致后，如果数组的长度不改变，经过mod运算得到的索引也会一致，就会发生哈希冲突，而通过改变数组长度，重新计算哈希值，再经过mod运算得到的索引也会发生改变，从而解决冲突问题
    • 并不是每次扩容都会重新计算哈希值，是否重新计算哈希值，源码里写了和哈希种子还有int最大值有关系，具体怎么计算并不了解。但是一般情况下并不会rehash

• 键值对个数：

  • transient int size;

• 扩容是的阈值：

  • 当前容量*负载因子： int threshold

• 被修改的次数：

  • transient int modCount
  • 在put、get、remove、interator等方法中，都会用到该参数，每次调用这些方法都会进行modCount++操作，这就是出现并发修改异常的原因
    • 因为HashMap是线程不安全的，所以会在迭代的时候将modCount赋值到expectedModCount属性中，然后进行迭代
    • 如果在迭代的过程中HashMap被其他线程修改了，modCount的数值就会++   发生变化，这时expectedModCount和ModCount不相等，迭代器就会抛出ConcurrentModificationException()异常

构造方法：

• HashMap()

  • 构造一个空的HashMap，默认初始容量为16，负载因子为0.75

  • 内部依然使用第三个构造方法

  • public HashMap() {
           this.loadFactor = DEFAULT_LOAD_FACTOR; //所有其他的字段都是默认字段
       }
    

• HashMap(int intitialCapacity)

  • 构造一个空的HashMap具有指定的初始容量（传进的参数），和默认的负载因子（0.75）

  • 内部依然使用第三个构造方法

  • public HashMap(int initialCapacity) {
            this(initialCapacity, DEFAULT_LOAD_FACTOR);
        }
    

• HashMap(int initialCapacity,float loadFactor);

  • 构造一个空的HashMap，具有指定的初始容量和负载因子（两个参数）

  • public HashMap(int initialCapacity, float loadFactor) {
           if (initialCapacity < 0)
               throw new IllegalArgumentException("Illegal initial capacity: " +
                                                  initialCapacity);
            //如果指定的容量小于0的话，报错       
           if (initialCapacity > MAXIMUM_CAPACITY)
               initialCapacity = MAXIMUM_CAPACITY;
            //如果指定的容量大于最大容量的话，将容量定为最大容量   
           if (loadFactor <= 0 || Float.isNaN(loadFactor))
               throw new IllegalArgumentException("Illegal load factor: " +
                                                  loadFactor);
          	 //如果指定的负载因子小于等于0的话（或者负载因子不等于负载因子？？）就报错
           this.loadFactor = loadFactor;
           this.threshold = tableSizeFor(initialCapacity);
       }
    

  • 主要是查看传进来的容量和负载因子是否合规，此时，让扩容阈值等于了初始容量

  • 这个时候只是给了必要的参数，并没有在此时初始化HashMap，没有分配空间

    • 在给HashMap添加元素时才会初始化HashMap

方法：

put方法：

• public V put(K key, V value) {
         if (table == EMPTY_TABLE) {     //判断是否内容为空，这里的table是一个键值对数组，默认是空的。
             inflateTable(threshold);			//如果内容为空，则首先初始化
         }
         if (key == null)							//如果传入的key是null，则调用下面的方法
             return putForNullKey(value);
         int hash = hash(key);				//如果key是存在的，那么计算key的hash
         int i = indexFor(hash, table.length);//计算完哈希后，根据哈希和数组长度去计算对应的索引，也就是这个key应该在数组里哪里存储
         for (Entry<K,V> e = table[i]; e != null; e = e.next) {//数组中的每个元素是一个链表，已经计算除了索引，所以遍历该索引位置上的链表，目的是为了检查传进来的key是否已经存在在表里
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//如果发现链表上的元素和传进来的key各方面都一样（hash，地址，内容）那么就说明表里已经有了，那么就保持key不变，更新value，并返回旧的value
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }
    
         modCount++;  //被修改次数加一，这个值主要是为了线程安全考虑，和本方法的业务无关
         addEntry(hash, key, value, i); //如果是一个新key，则添加元素。
         return null;
     }
  

• 图解：

addEntry(hash,key,value,i)

• void addEntry(int hash, K key, V value, int bucketIndex) {
          if ((size >= threshold) && (null != table[bucketIndex])) {//当当前的元素个数大于等于扩容阈值的时候，并且分配给新元素的这个位置以及有值，则扩容
              resize(2 * table.length);//扩容为原来的数组长度乘2
              hash = (null != key) ? hash(key) : 0;//重新计算key的hash值，如果key=null，则hash为0
              bucketIndex = indexFor(hash, table.length);//根据新数组长度重新计算索引
          }
  
          createEntry(hash, key, value, bucketIndex);//插入该节点
      }
  

get方法：

初始化：

private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);//这里可以看到，初始化时，无论传进来的初始容量是多少，都会向上取整为2的幂。

        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//计算扩容阈值
        table = new Entry[capacity];//初始化
        initHashSeedAsNeeded(capacity);
    }

• 虽然构造方法中可以让用户自定义容量大小，但是进来后也会向上转成2的幂。当然，如果本身就是2的幂，那么就不会转换了，这里看源码，会发现他做了一个-1操作，目的就是为了防止把正确容量也翻一倍。比如你传进来的是15，那么向上取整为16.如果传进来的是16，向上取整就成了32，这是不合理的，所以任何数在取整时都先-1.

面试题：

• HashMap的底层数据结构

  • 在jdk7及之前为数组加链表的数据结构

    • 数组为：内存中的一片连续区域，同类型数据的集合，有索引，查询快，增删慢，不可扩容。
    • 链表为：不连续的区域，每个节点放值和指向下一个节点的指针。查询慢，增删块。
    • 哈希表为：数组加链表。即一个一维数组，但是数组中的每个元素是一个链表

  • jdk8及之后为数组加链表加红黑树的数据结构

    • 所以jdk8在插入的时候，依然按照链表插入，不同于jdk7，这里使用尾插法，为了解决头插法可能出现的死循环问题
    • 当发现链表的节点（也就是链表的元素）达到8，同时满足数组长度达到64，如果数组长度没达到64会先扩容，两个条件都满足时，会将此链表转成红黑树。
    • 如果发现扩容后红黑树的结点减少到了6，那么又会将他转成链表
    • 尽管红黑树的动态自平衡也比较耗时间，但是当链表结点个数为8个以上时，相较于通过链表查询所耗的时间，红黑树的自平衡时间更少，更划算

• 一般用什么作为key？

  • 一般用Integer、String这种不可变类当HashMap的键，而且String最常用
  • 因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
  • 因为获取对象的时候要用到equals()和hashCode()方法，那么键对象正确的重写这两个方法是非常重要的,这些类已经很规范的覆写了hashCode()以及equals()方法。