java基础之HashMap

HashMap主要用于存储键值对，是最常用的java集合
原理:HashMap.put(key,values),key 调用hash得出一个HashCode ,由于hash碰撞的原因 将values的值存入链表中.HashMap 特性是增删快,ArrayList 底层是集合 所以会查询快 增删需要扩容 增删慢.

HashMap 在Jdk 1.7 和1.8 区别?

jdk1.7 数组+链表 头插法 头插法
jdk 1.8 数组+链表+红黑树 尾插法 +lamda表达式

查询速度:
数组查询速度是O(1) 
链表查询速度是O(n) 
红黑树查询速度是O(log(n))

主要记录数据:

加载因子:0.75
泊松分布:8
扩容阈值: 0.75* 16
初始大小:1<<<4 16
最大个数:1<<<30 几十亿
扩容:必须是2的幂 直接扩容一倍

---

1.Hash碰撞?

hash的值是有限的 数据是无线的,所以会出现多个数据的hash会是同一个hashCode 这就是hash碰撞.

解决方案:

在HashMap中运用链表的形式存储values的数据,将一个HashCode的数据存入链表中.
Jdk 1.7 将数据存储到链表中(链表存储过长,会出现查询慢的问题)
Jdk1.8以后根据泊松分布,链表存储8个以后会变成红黑树存储优化了链表大量查询慢的问题.

注意:泊松分布
* Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million

---

2.HashMap扩容?

HashMap 默认大小是 16 加载因子是 0.75(时间和空间的折中选择),当存储的数据达到16*0.75 这个阈值的时候就会扩容.扩容的时候会将数据的key重新hash 然后存储到新的容器中.多线程使用HashMap 扩容的时候有可能在产生环形链表的情况, 因为HashMap 是线程不安全的 所以多线程使用的时候要调用ConcurrentHashMap 一个线程安全的HashMap.

3.Jdk1.8 HashMap 底层 增加了红黑树为什么.

链表存储数据的查询速度是O(n),所以当HashMap values数据大量数据存储再链表中的时候会出现查询慢的问题,所以Jdk1.8 的时候Hamp做出了优化.将数据根据不同情况存储到了链表和红黑树(二叉树的特殊平衡树)中.根据泊松分布 在链表中存储了8个数据以后会将数据换到红黑树的这种形式存储.