HashMap相关知识

HashMap及其相关知识

• 数据结构及扩容原理
• 线程安全性
• 引用

数据结构及扩容原理

JDK8开始，结构变为数组+链表/红黑树，当单项链表元素超过8个，结构变为红黑树，红黑树上节点小于6个时，结构重新变为单项链表。
HashMap是无序的，加入顺序和取出顺序也不一样，初始化容量16，负载因子0.75，当容量达到75%时开始扩容，扩容2倍。原数组中的数据必须重新计算其在新数组中的位置，并放进去，所以效率低。引发思考，如果我们提前知道HashMap中要Put元素的数量，可以创建的时候申请足够容量。

数组

优点：存储区间连续，随机存储效率高，查找速度快O(1)。
缺点：由于存储空间连续所以暂用空间严重，插入、删除效率低，以为插入数据，该位置后的数据要往后移。

链表

优点：内存利用率高，插入、删除效率高。
缺点：不能随机查找，每次都是从第一个开始遍历。

put(k,v)原理

1. 首先将k,v封装到Node对象中；
2. 调用k的hashCode()方法，得出hash值；
3. 通过哈希算法将hash值转换为数组下标；
4. 若下标位置没有元素，将Node添加到该位置，若有链表，就会通过k和链表上每个节点的的k进行equals,如果所有equals都返回false，那么将Node加到链表末尾，如其中某个equals返回true，那么该节点被覆盖。

get(k)原理

1. 先调用k的hashCode()方法得出哈希值，并通过哈希算法转换为数组下标；
2. 如果数组位置什么都没有，则返回null，如果该位置有单项链表，那么会将k和单机链表上每一个节点进行equals；
3. 如果所有equals都返回false，则get方法返回null，如果其中一个节点的k和参数k进行equals后返回true，则该节点的v就是要找的v

hashCode()和equals()

对HashMap的这两个方法需要重写，因为Object默认的这两个方法是如下的：
hashCode():是JDK根据对象的地址或字符串或数字算出来的int数值，叫哈希码。两个相等的对象有同样的哈希码。
equals():默认实现中，比较内存地址值。在String、Interger、Date中都被重写了，变成比较对象的成员变量值是否相同。重写该方法时通常也要重写hashCode(),因为要维护相等对象间拥有相同的哈希码。
“==”：在不重写equals()时，==和equals一样。重写后取决于你是怎么重写的。一般的重写步骤：

1. 使用“==”检查参数是否为这个对象的引用
2. 使用instanceof 检查参数是否为正确的类型
3. 把参数转化为正确的类型
4. 检查类中的每个关键域

举个栗子，String类中的==和equals，==比较两者地址是否相同，equals比较值是否相同。

        String str1 = "1";
        String str2 = "1";
        System.out.println(str1.equals(str2));
        System.out.println(str1 == str2);
        String str3 = new String("2");
        String str4 = new String("2");
        System.out.println(str3.equals(str4));
        System.out.println(str3 == str4);

所以这个结果是什么呢？
true true true false

线程安全性

为啥HashMap线程不安全呢？
JDK1.7中扩容时造成环形链和数据丢失，JDK1.8已解决，
JDK1.8中，还有数据覆盖的情况。
详见链接3.

线程安全的结构：Hashtable和ConcurrentHashMap
两者都是线程安全的，比较如下，可查看链接4：
HashTable:对所有容器状态访问都串行化了，通过synchronized关键字实现，严重降低了并发性，当多个线程竞争容器时，吞吐量严重降低。
ConcurrentHashMap：加锁颗粒度更细，最高允许16个线程同时访问，效率高。JDK1.8后，用 Node 数组+链表+红黑树的数据结构，并发控制使用 synchronized 和 CAS 来操作。

引用

感谢前辈们
[1]: http://baijiahao.baidu.com/s?id=1665667572592680093&wfr=spider&for=pc
[2]: https://blog.csdn.net/hfut_why/article/details/82915167
[3]: https://blog.csdn.net/swpu_ocean/article/details/88917958
[4]: https://www.jianshu.com/p/82e8d173f6e1