HashMap探究

HashMap实现原理

HashMap是基于Hash算法实现的，是通过put(key,value)存储，get(key)来获取，当传入key时，会根据key 的HashCode方法计算Hash值，根据Hash值将value保存在bucket里，当计算的Hash值相同时称为Hash冲突，HashMap的做法是用链表和红黑树来存储Hash值相同的value，是当数组大于等于64，链表长度达到8时会转换为红黑树（泊松分布）

用String作为key有什么好处？

HashMap是通过key的HashCode来确定value的存储位置，因为字符串是不可变的，所以在创建的时候，它的Hashcode被缓存下来，不需要计算，所以相比其它对象更快。

Hash的概念

Hash的基本概念就是把任意长度的输入通过一个hash算法之后，映射成固定长度的输出

HashMap初始化容量大小是多少？

通过查看源码可以发现：

初始化数组大小：16 (2的4次方)

加载因子：衡量一个数组是否被填满，等于1，则证明数组已经被填满，等于0证明数组还是空的。

默认是0.75

threshold：阈值，数组到达某一个阈值时开始进行扩容

所以是12

长度为什么必须是2的幂？

HashMap存取时，需要对当前key，计算数组下标

HashMap为了减少碰撞，就要尽量把数据平均分配，(n - 1) & hash 这个操作如果在n为2的N次幂的情况下是等同于 hash % n 取余数的值，而使用与运算效率高于 hash%n 取余数的值。

总结：HashMap这里采用的是用与运算符替换传统的取模方式，从而大大提高效率，但与运算符进行计算的前提是必须2的幂次方

然后通过下面的方法执行操作

HashMap的put过程

• 根据key 的hashCode方法计算hash值
• 根据hash值与数组长度-1进行与运算得到index值
• 如果索引处为空，则直接插入对应数组中，否则，判断是否是红黑树
• 如果是，则红黑树插入，否则遍历链表，若长度大于8，则将链表转换为红黑树，转成功之后再插入。

HashMap的get过程

• 根据key 的hashCode方法计算hash值
• 根据hash值与数组长度-1进行与运算得到index值（数据的存储位置）
• 根据index找到链表的头结点，遍历对应的链表，若key值相等（这里用的equals方法判断），返回对应的value值，否则返回null

HashMap什么时候扩容，扩多少？

• 首次扩容：HashMap初始化后首次插入数据时，先发生resize扩容，再插入数据；因使用默认构造方法初始化HashMap,HashMap一开始会返回一个空数组，且加载因子为0，所以第一次扩容的容量为默认值16，阈值是12.（注意：java7是在存入数据前进行判断是否扩容，而java8是在存入数据后再进行扩容的判断）
• 当前存入数据大于阈值时进行扩容，此时是先插入数据再扩容，容量扩大为原来的2倍。
• 数组长度小于64，链表长度大于8时会进行扩容，如果数组长度大于等于64时才会将链表转换为红黑树。

ConcurrentHashMap

JDK1.7中采用了一种分段锁的机制，底层实现是一个segment数组，每个segment的底层结构和HashMap相似，也是数组加链表

首先将数据分为一段一段的存储，然后给每一段数据配一把锁（ReentrantLock），当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问.

JDK1.8中摒弃了Segment，新的实现也是数组+链表+红黑树，在put方法里使用了CAS + synchronized进行同步。如果插入元素为空则用CAS进行插入，插入元素不为空，则对当前位置对象进行加锁，加锁后再进行后续操作。

好处：synchronized只需要锁住当前链表的头结点，理论上数组长度有多大，并发操作线程数就有多少，效率高。

ConcurrentHashMap和HashTable区别

• HashTable底层采用数组+链表，ConcurrentHashMap在JDK1.8采用数组+链表+红黑树，数组是HashMap的主体，链表是为解决哈希冲突存在的
• 1.8的ConcurrentHashMap可以并发控制使用synchronized和CAS来操作，HashTable使用synchronized来保证线程安全，效率非常低

CAS（比较并交换）

CAS包含3个参数：

• 内存值 V　　
• 旧的预期值 A　　
• 新值 B

　　当且仅当V值等于A值时，将V的值改为B值，如果V值和A值不同，说明已经有其他线程做了更新，则当前线程什么都不做，最后返回当前V的真实值。CAS操作是抱着乐观的态度进行的（乐观锁），它总是认为自己可以成功地完成操作。

ThreadLocal

ThreadLocal使各个线程之间相互隔离，每个线程有自己独立的变量。可以理解为ThreadLocal不是针对程序的全局变量，而是针对线程的全局变量

原理：

ThreadLocal内部维护了一个Map变量ThreadLocalMap，对应的就是每个Thread对象中的属性ThreadLocals，他的key就是当前线程本身，value就是我们set进来的值，调用get时，会将当前线程作为key，然后从ThreadLocalMap中获取