JAVA----＞HashMap的底层实现原理

• HashMap使用的存储结构：jdk8:数组+链表+红黑树 jdk7:数组+链表

  • 加了红黑树以后，提高数据的查找、对比的效率
  • 链表：“七上八下”

• 初始化的问题：new HashMap()

  • jdk 8：没有初始化底层的数组； jdk7实例化时就初始化了底层的数组

  • jdk8：底层的数组Node[] : (class HashMap.Node implements Map.Entry)

    jdk7：底层的数组Entry[] : (class HashMap.Entry implements Map.Entry)

    class Node/Entry<K,V>{

    ​ int hash;

    ​ K key;

    ​ V value;

    Node/Entry next;
    

    }

• 添加数据的过程：

  • 在jdk8中首次调用put()：底层会创建长度为16的数组，然后添加数据
  • 在jdk7中首次调用put()：直接添加数据
  • 具体的添加过程：

   1. 当添加key1-vulue1时，首先通过key1所在类的hashCode()方法，计算key1的哈希值
   *    2. 此哈希值经过某种算法以后，确定其在table数组中的存放位置:i
   *    3. 如果table[i]位置为空，则key1-value1添加成功  --->情况1
   *       如果table[i]位置不为空，则比较key1与table[i]位置现有元素key2-value2进行对比
   *       	4.比较key1和key2的哈希值，如果哈希值不相同，则key1-value1添加成功  --->情况2
   *            比较key1和key2的哈希值，如果哈希值相同，调用key1所在类的equals(),将key2作为参数传入equals()
   *            		5. 如果equals()返回false,则key1-value1添加成功  --->情况3
   *                     如果equals()返回true,则用value1替换原有的value2
   * 
   * 		情况1：将e1直接保存在数组的指定位置
   *      情况2、情况3：此时e1与现有索引位置上的元素，以链表的方式进行保存。
  

• 扩容机制

  • 临界值threshold ，当添加的元素超过临界值时，就考虑扩容，默认扩容为原来的2倍

  • 默认情况下等于 DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY。即为12

  • 加载因子：默认是0.75

    负载因子的大小决定了HashMap的数据密度。
    负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时的比较次数增多，性能会下降。
    负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能，建议初始化预设大一点的空间。
    按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数。
    

• 添加操作之外的，get(key)、remove(key)等操作，也参考put(key,value)