HashMap总结

一、简介

1、HashMap是线程不安全的(HashMap是异步的，HashTable是同步的)
2、HashMap采用了数组和链表的数据结构，能在查询和修改方便继承了数组的线性查找和链表的寻址修改
2、HashMap是一个散列桶(数组和链表)，以键值对方式进行存储的
3、HashMap是通过get()和put()方法来获取和存储对象的。当我们存储值时，将键值对传给put()方法时，他调用键的hashCode()方法来计算hashCode值，然后找到对应的bucket位置来存储对象。当获取对象时，通过调用键的equals()方法找到正确的键值对，来返回值对象
4、HashMap通过链表的方式解决hash碰撞的，当发生碰撞时，对象会存储在链表的下一个节点中。

二、底层原理

hashMap实现了Map接口，继承了AbstractMap类。其中Map接口定义了键映射到值的规则，AbstractMap类提供了Map接口的骨干实现。

数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，为O（N）。链表的特点是：寻址困难，插入和删除容易。
综合这两者的优点，摒弃缺点，哈希表就诞生了，既满足了数据查找方面的特点，占用的空间也不大。

数组链表
哈希表可以说就是数组链表，底层还是数组但是这个数组每一项就是一个链表。

hashMap底层是基于数组链表实现的。Java8之后添加了红黑树的概念

hashMap底层有一个entry数组(entry是hashMap的内部类，它包含了键key、值value、下一个节点next，以及hash值，这是非常重要的，正是由于Entry才构成了table数组的项为链表)，数组上每一项都有一个链表，如果链表长度超过阀值( TREEIFY THRESHOLD==8)，就把链表转成红黑树，链表长度低于6，就把红黑树转回链表

存储结构

三、HashMap提供的三个构造函数：

1、HashMap()：构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。

2、HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。

3、HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空 HashMap。

在这里提到了两个参数：初始容量，加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

HashMap是一种支持快速存取的数据结构，要了解它的性能必须要了解它的数据结构。

四、HashMap与HashTable的区别

二者都实现了Map接口

• HashMap是非同步的，所以线程不安全，但效率高。多线程不能使用一个HashMap
  HashTable是同步的，所以线程安全，但效率低。多线程可以使用一个HashTable
  Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。

• HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行

• HashMap的迭代器(Iterator)是fail-fast迭代器
  Hashtable的enumerator迭代器不是fail-fast的

所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。

Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator，然后其它的线程试图“结构上”更改集合对象，将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的，因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改，再调用set()方法，将会抛出IllegalArgumentException异常。

• HashMap不能保证随着时间的推移Map中的元素次序是不变的。

HashMap可以通过下面的语句进行同步：

Map m = Collections.synchronizeMap(hashMap);

image.png

---

---

---

后期补充总结：
HashMap的实现，简单来说，java的HashMap就是数组加链表实现的，数组中的每一项是一个链表。通过计算存入的hashCode，来计算对象在数组中要存入的位置，用链表来解决散列冲突，链表中的节点存储是键值对；除了实现方式，我们还需要知道填充因子的作用与Map扩容时的rehash机制，需要知道HashMap的容量都是2的幂次方，是因为可以根据按位与操作来计算余数，比求模要快。另外HashMap是线程不安全的，在多线程put的情况下，有可能在容量超过填充因子时进行rehash，因为HashMap为了避免尾部遍历，在链表插入元素时使用头插法，多线程的情况下可能造成死循环。

CurrentHashMap，通过HashMap线程不安全，我们就会联想到线程安全的CurrentHashMap。 CurrentHashMap采用分段锁的思想来降低并发场景下的锁定发生频率，在JDK1.7和JDK1.8中的差距非常大，1.7中使用Segment进行分段加锁，降低并发锁定；1.8中使用自旋锁的乐观锁来提高性能，但是在并发较高时，性能会比较一般。另外1.8中的CurrentHashMap引入了红黑树来解决Hash冲突时链表顺序查找的问题。红黑树的启用条件与链表的长度和Map的总容量有关，默认是链表大于8且容量大于64时转为红黑树。这部分建议详细阅读源码进行学习。。。