HashMap以及其子类关键性总结
HashMap
1.7中的HashMap
负载因子: 给定默认容量为16 负载因子为0.75
- Map在使用过程中不断的往里面存放元素 当数量达到16*0.75=12时 就需要将当前的默认容量扩容 而扩容的过程设计reHash 复制数组等操作,非常损耗性能
- 建议提前预估HashMap的初始大小,尽量减少HashMap的扩容带来的性能损耗
其实真正存放数据的是 Entry<K,V>[] table，Entry 是 HashMap 中的一个静态内部类，它有key、value、next、hash（key的hashcode）成员变量 多个Entry就构成hashMap的数据结构 数组+链表
put()
- 判断当前的数组是否需要初始化
- 如果Key为Null 则put一个空值进去
- 根据key计算出hashCode
- 根据计算出来的HashCode定位出所在的数组位置(头插法)
- 如果数组位置是一个链表则需要遍历判断里面的HashCode key 是否和传入的相等, 如果相同就进行覆盖,并且返回被覆盖的值
- 如果这个数组位置是空的,new 一个Entry对象写入到当前位置,(调用addEnrty 写入Entry时需要判断是否需要扩容,扩容就是2倍 并将当前的key 重新hash并定位, 而在createEntry中将当前位置的数组算元传入到新建的数组位置中 如果当前数组位置有值就会形成链表)
get()
- 根据计算出来的HashCode找倒对应的HashEnrty位置 如果在数组上直接返回
- 判断是否为链表 不是链表就根据Key .key以及HashCode 是否相等来返回
- 为链表的需要遍历到key以及hashcode相等再返回
- 啥都没有取到就返回Null
1.8中的HashMap
当Hash冲突严重时,在桶上形成的链表越来越长,这样在查询时的效率就会越来越低,时间复杂度为o(N)
TREEIFY_THRESHOLD = 8 用于判断是否将链表转为红黑树的阈值
桶中存放的数据结构为Node
put()
- 判断当前桶是否为空 空就需要初始化(resize方法中会判断是否进行初始化)
- 根据当前的key的hashcode定位到具体的桶中并且判断桶是否为空,为空表名没有Hash冲突直接在当前位置新建一个桶即可
- 如果存在Hash冲突 那么就要比较桶中的key.key的hashCode与写入的key是相等,如果相等.就赋值给e,等待循环结束后替换
- 如果当前桶是个红黑树 那就要按照红黑树的范式写入数据
- 如果是一个链表就需要将当前的key value封装成一个新节点Node写入到当前桶的第一个位置 (尾插法)
- 接着判断当前链表大小是否大于预设的链表阈值 大于就转成红黑树
- 如果遍历过程中找到key相同值时直接退出遍历
- 如果e!=null 就相当于存在相同的key 就替换存在的值 返回原值
- 最后判断是否需要进行扩容
get()
- 根据计算出来的HashCode找倒对应桶的位置 如果在数组上直接返回 如果为空返回null
- 如果第一个不匹配则判断它的下一个是红黑树还是链表
- 红黑树就按照树的查找方法返回
- 链表就需要遍历匹配返回值
但是 HashMap 原有的问题也都存在，比如在并发场景下使用时容易出现死循环
- 在 HashMap 扩容的时候会调用 resize() 方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环：在 1.7 中 hash 冲突采用的头插法形成的链表，在并发条件下会形成循环链表，一旦有查询落到了这个链表上，当获取不到值时就会死循环。
HashMap何时扩容
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值(默认12)---即大于当前数组的长度乘以加载因子的值的时候，就要自动扩容。
HashMap扩容算法
扩容(resize) 就是重新计算容量,数组无法自动扩容 方法就是使用一个新数组代替已有的容量小的数组 2倍扩容
Hashmap如何解决散列碰撞
HashMap是利用拉链法 处理hashcode的碰撞问题 在调用HashMap的put或者get方法时,都会调用Hashcode方法区查找相关的key 当有冲突时在调用equals方法
HashMap基于hashing原理 通过put和get方法存取对象,当我们将键值对传递给put方法时,他调用对象的hashCode方法计算Hashcode 知道哦啊哦哈系统位置来存储对象,当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。
HashMap使用链表来解决碰撞问题，当碰撞发生了，对象将会存储在链表的下一个节点中。hashMap在每个链表节点存储键值对对象。当两个不同的键却有相同的hashCode时，他们会存储在同一个bucket位置的链表中。键对象的equals()来找到键值对。
Hashmap底层为什么是线程不安全的？
- 并发场景下使用时容易出现死循环 在 HashMap 扩容的时候会调用 resize() 方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环
- 在 1.7 中 hash 冲突采用的头插法形成的链表，在并发条件下会形成循环链表，一旦有查询落到了这个链表上，当获取不到值时就会死循环。
ConcurrentHashMap
1.7 中ConcurrentHashMap
ConcurrentHashMap在jdk1.7中使用了分段锁,其中segment继承于ReentranLock ,不会像HashTable那样不管是put还是get都去做同步处理,理论上ConcurrentHashMap支持CurrencyLevel(Segment数组数量)的线程并发,当每个线程占用锁访问一个Segment时,不会影响到其他的Segment
数据结构和HashMap一致 数组+链表
分段锁
ConcurrentHashMap里面元素存放在table数组中,分段锁就是把这个table分成多段,每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率,在ConcurrentHashMap中使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16，其中第N个散列桶由第（N mod 16）个锁来保护。假设使用合理的散列算法使关键字能够均匀的分部，那么这大约能使对锁的请求减少到越来的1/16。也正是这项技术使得ConcurrentHashMap支持多达16个并发的写入线程。
put()
首先通过Key定位到Segment,之后再对应的Segment中具体的put元素
- 虽然HashEntry中的Value是用Volatile关键字修饰,但是并不能保证并发的原子性,所以put操作时任然需要加锁处理
- 首先第一步的时候会去尝试获取锁, 如果锁获取失败肯定就存在与其他线程存在竞争,利用scanAdnLockForPut()自选获取锁,如果获取次数达到了Max_SCAN_RETRIES,则改为阻塞锁获取,保证能获取锁成功
- 将当前的Segment中的table通过key的hashCode定位到HashEntry
- 遍历该HashEntry 如果不为空则判断传入的key和当前遍历的Key是否相等,相等则覆盖旧的Key
- 为空则需要新建一个HashEntry并加入到Segment中,同时还会判断是否需要扩容
- 最后会使用unLock解除当前Segment的锁
get()
- 只需要将Key通过 Hash之后定位到具体的Segment 再通过一次Hash定位到元素上
- 由于HashEntry 中的Value属性是用Volitile 关键字修饰,保证了内存的可见性,所以每次都可以实时获取最新值
- ConCurrentHashMap的get方法是相对高效的,因为整个过程不需要加锁
1.8中的ConCurrentHashMap
在1.7中已经解决了HashMap的并发问题 ,并且支持N个Segment这个多次数的并发,但是任然存在1.7中HashMap的问题,查询遍历链表效率低, 和1.8中的HashMap结构类似, 其中抛弃可原有的分段锁,采用了CAS+Synchronized来保证并发的安全
CAS
如果Obj内的Value和Expect相同 就证明没有其他线程改变过这个变量,name就更新它为update 如果这一步的CAS没有成功,那么就采用自选的方式继续进行CAS操作
对CAS的理解，CAS是一种无锁算法，CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做
CAS ABA问题
- 问题描述 现在在对象中存入一Value A 但是另一个线程把Value的值从A改到B 又从B重新变为A 'eg :插进去 取出来等于没插?'
- 解决 目前在JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题,这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。
- 如果CAS不成功 则会原地自旋,时间长会给CPU带来巨大开销
- 其实除了AtomicStampedReference类，还有一个原子类也可以解决，就是AtomicMarkableReference，它不是维护一个版本号，而是维护一个boolean类型的标记，用法没有AtomicStampedReference灵活。因此也只是在特定的场景下使用。
数据结构和HashMap一致 数组+链表+红黑树
put()
- 根据Key计算出HashCode
- 判断当前数组table是否需要初始化
- 如果当前Key定位出的Node为空 表示可以写入数据,利用CAS尝试写入,失败则自旋保证成功
- 如果当前位置的Hashcode==MOVE==-1 则需要扩容
- 如果都不满足 则利用Synchronized锁写入数据
- 最后判断如果数组长度大于TREEIFY_THRESHOLD(8) 则要转化成红黑树
get()
- 根据计算出来的HashCode找倒对应的NodeBin位置 如果在数组上直接返回
- 如果是红黑树就按照数的遍历方式来获取
- 如果都不满足 就按照链表的方式遍历获取值
1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock(可重入锁) 改为了 synchronized(独占锁)，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。
ArrayMap
ArrayMap利用两个数组，mHashes用来保存每一个key的hash值，mArrray大小为mHashes的2倍，依次保存key和value
mHashes[index] = hash;
mArray[index<<1] = key;
mArray[(index<<1)+1] = value;
当插入时，根据key的hashcode()方法得到hash值，计算出在mArrays的index位置，然后利用二分查找找到对应的位置进行插入，当出现哈希冲突时，会在index的相邻位置插入。
SparseArray
SparseArray比HashMap更省内存，在某些条件下性能更好，主要是因为它避免了对key的自动装箱（int转为Integer类型），它内部则是通过两个数组来进行数据存储的，一个存储key，另外一个存储value，为了优化性能，它内部对数据还采取了压缩的方式来表示稀疏数组的数据，从而节约内存空间，我们从源码中可以看到key和value分别是用数组表示：
private int[] mKeys;
private Object[] mValues;
同时，SparseArray在存储和读取数据时候，使用的是二分查找法。也就是在put添加数据的时候，会使用二分查找法和之前的key比较当前我们添加的元素的key的大小，然后按照从小到大的顺序排列好，所以，SparseArray存储的元素都是按元素的key值从小到大排列好的。 而在获取数据的时候，也是使用二分查找法判断元素的位置，所以，在获取数据的时候非常快，比HashMap快的多。
假设数据量都在千级以内的情况下：
-
如果key的类型已经确定为int类型，那么使用SparseArray，因为它避免了自动装箱的过程，
-
如果key为long类型，它还提供了一个LongSparseArray来确保key为long类型时的使用
-
如果key类型为其它的类型，则使用ArrayMap。
